Algorithms - ESA 2002. 10th annual European symposium, Rome, Italy, September 17--21, 2002. Proceedings (Q1848550)

The articles of mathematical interest will be reviewed individually. The preceding symposium (9th, 2001) has been reviewed (see Zbl 0971.00046). Indexed articles: \textit{Cook, William}, Solving traveling salesman problems, 1 [Zbl 1019.90520] \textit{Dey, Tamal K.}, Computing shapes from point cloud data, 2 [Zbl 1019.65504] \textit{Karlin, Anna R.}, Mechanism design for fun and profit, 3 [Zbl 1019.68824] \textit{Thorup, Mikkel}, On distance oracles and routing in graphs, 4 [Zbl 1019.68596] \textit{Agarwal, Pankaj K.; Gao, Jie; Guibas, Leonidas J.}, Kinetic medians and kd-trees, 5-16 [Zbl 1019.68815] \textit{Agarwal, Pankaj K.; Govindarajan, Sathish; Muthukrishnan, S.}, Range searching in categorical data: Colored range searching on grid, 17-28 [Zbl 1019.68529] \textit{Agarwal, Pankaj K.; Har-Peled, Sariel; Mustafa, Nabil H.; Wang, Yusu}, Near-linear time approximation algorithms for curve simplification, 29-41 [Zbl 1019.68133] \textit{Agarwal, Pankaj K.; Hagerup, Torben; Ray, Rahul; Sharir, Micha; Smid, Michiel; Welzl, Emo}, Translating a planar object to maximize point containment, 42-53 [Zbl 1019.68134] \textit{Agarwal, Pankaj K.; Procopiuc, Cecilia M.; Varadarajan, Kasturi R.}, Approximation algorithms for \(k\)-line center, 54-63 [Zbl 1019.68132] \textit{Ahr, Dino; Reinelt, Gerhard}, New heuristics and lower bounds for the min-max \(k\)-Chinese postman problem, 64-74 [Zbl 1019.90521] \textit{Althaus, Ernst; Bockmayr, Alexander; Elf, Matthias; Jünger, Michael; Kasper, Thomas; Mehlhorn, Kurt}, SCIL -- symbolic constraints in integer linear programming, 75-87 [Zbl 1019.90515] \textit{Arge, Lars; Procopiuc, Octavian; Vitter, Jeffrey Scott}, Implementing I/O-efficient data structures using TPIE, 88-100 [Zbl 1019.68823] \textit{Baier, Georg; Köhler, Ekkehard; Skutella, Martin}, On the \(k\)-splittable flow problem, 101-113 [Zbl 1040.90044] \textit{Barkan, Arye; Kaplan, Haim}, Partial alphabetic trees, 114-125 [Zbl 1019.68524] \textit{Barrett, Chris; Bisset, Keith; Jacob, Riko; Konjevod, Goran; Marathe, Madhav}, Classical and contemporary shortest path problems in road networks: Implementation and experimental analysis of the TRANSIMS router, 126-138 [Zbl 1019.68801] \textit{Bender, Michael A.; Cole, Richard; Demaine, Erik D.; Farach-Colton, Martin}, Scanning and traversing: Maintaining data for traversals in a memory hierarchy, 139-151 [Zbl 1019.68526] \textit{Bender, Michael A.; Cole, Richard; Demaine, Erik D.; Farach-Colton, Martin; Zito, Jack}, Two simplified algorithms for maintaining order in a list, 152-164 [Zbl 1019.68527] \textit{Bender, Michael A.; Demaine, Erik D.; Farach-Colton, Martin}, Efficient tree layout in a multilevel memory hierarchy, 165-173 [Zbl 1019.68525] \textit{Berberich, Eric; Eigenwillig, Arno; Hemmer, Michael; Hert, Susan; Mehlhorn, Kurt; Schömer, Elmar}, A computational basis for conic arcs and boolean operations on conic polygons, 174-186 [Zbl 1019.68601] \textit{de Berg, Mark; Gudmundsson, Joachim; Katz, Matthew J.; Levcopoulos, Christos; Overmars, Mark H.; van der Stappen, A. Frank}, TSP with neighborhoods of varying size, 187-199 [Zbl 1019.90516] \textit{Berman, Piotr; Hannenhalli, Sridhar; Karpinski, Marek}, 1. 375-approximation algorithm for sorting by reversals, 200-210 [Zbl 1019.68817] \textit{Bodlaender, Hans L.; Broersma, Hajo; Fomin, Fedor V.; Pyatkin, Artem V.; Woeginger, Gerhard J.}, Radio labeling with pre-assigned frequencies, 211-222 [Zbl 1020.05062] \textit{De Bontridder, Koen M. J.; Lageweg, B. J.; Lenstra, Jan K.; Orlin, James B.; Stougie, Leen}, Branch-and-bound algorithms for the test cover problem, 223-233 [Zbl 1019.68807] \textit{Bose, Prosenjit; Gudmundsson, Joachim; Smid, Michiel}, Constructing plane spanners of bounded degree and low weight, 234-246 [Zbl 1019.68802] \textit{Brandes, Ulrik}, Eager \(st\)-ordering, 247-256 [Zbl 1019.68803] \textit{Buchsbaum, Adam L.; Goodrich, Michael T.}, Three-dimensional layers of maxima, 257-269 [Zbl 1019.68804] \textit{Chen, Danny Z.; Hu, Xiaobo S.; Luan, Shuang; Wu, Xiaodong; Yu, Cedric X.}, Optimal terrain construction problems and applications in intensity-modulated radiation therapy, 270-283 [Zbl 1019.68603] \textit{Chen, Danny Z.; Smid, Michiel; Xu, Bin}, Geometric algorithms for density-based data clustering, 284-296 [Zbl 1019.68602] \textit{Cohen, Edith; Kaplan, Haim}, Balanced-replication algorithms for distribution trees, 297-309 [Zbl 1019.68806] \textit{Datar, Mayur}, Butterflies and peer-to-peer networks, 310-322 [Zbl 1019.68504] \textit{Datar, Mayur; Muthukrishnan, S.}, Estimating rarity and similarity over data stream windows, 323-334 [Zbl 1019.68533] \textit{De Bonis, Annalisa; Vaccaro, Ugo}, Efficient constructions of generalized superimposed codes with applications to group testing and conflict resolution in multiple access channels, 335-347 [Zbl 1019.68589] \textit{Demaine, Erik D.; López-Ortiz, Alejandro; Munro, J. Ian}, Frequency estimation of internet packet streams with limited space, 348-360 [Zbl 1019.68502] \textit{Deshmukh, Kaustubh; Goldberg, Andrew V.; Hartline, Jason D.; Karlin, Anna R.}, Truthful and competitive double auctions, 361-373 [Zbl 1046.91046] \textit{Dessmark, Anders; Pelc, Andrzej}, Optimal graph exploration without good maps, 374-386 [Zbl 1019.68599] \textit{Dey, Tamal K.; Zhao, Wulue}, Approximating the medial axis from the Voronoi diagram with a convergence guarantee, 387-398 [Zbl 1019.68605] \textit{Doerr, Benjamin; Schnieder, Henning}, Non-independent randomized rounding and an application to digital halftoning, 399-410 [Zbl 1019.68812] \textit{Efrat, Alon; Kobourov, Stephen G.; Lubiw, Anna}, Computing homotopic shortest paths efficiently, 411-423 [Zbl 1019.68606] \textit{Elbassioni, Khaled M.}, An algorithm for dualization in products of lattices and its applications, 424-435 [Zbl 1019.68130] \textit{Enosh, Angela; Kedem, Klara; Bernstein, Joel}, Determining similarity of conformational polymorphs, 436-448 [Zbl 1019.92038] \textit{Epstein, Leah; van Stee, Rob}, Minimizing the maximum starting time on-line, 449-460 [Zbl 1019.68505] \textit{Epstein, Leah; Tassa, Tamir}, Vector assignment problems: A general framework, 461-472 [Zbl 1019.68506] \textit{Ezra, Eti; Halperin, Dan; Sharir, Micha}, Speeding up the incremental construction of the union of geometric objects in practice, 473-484 [Zbl 1019.68607] \textit{Fahle, Torsten}, Simple and fast: Improving a branch-and-bound algorithm for maximum clique, 485-498 [Zbl 1019.90517] \textit{Fiat, Amos; Mendel, Manor; Seiden, Steven S.}, Online companion caching, 499-511 [Zbl 1019.68507] \textit{Gasieniec, Leszek; Pagourtzis, Aris; Potapov, Igor}, Deterministic communication in radio networks with large labels, 512-524 [Zbl 1019.90503] \textit{Gentile, Claudio; Haus, Utz-Uwe; Köppe, Matthias; Rinaldi, Giovanni; Weismantel, Robert}, A primal approach to the stable set problem, 525-537 [Zbl 1019.90518] \textit{Haxell, Penny; Rasala, April; Wilfong, Gordon; Winkler, Peter}, Wide-sense nonblocking WDM cross-connects, 538-549 [Zbl 1019.90504] \textit{Heggernes, Pinar; Villanger, Yngve}, Efficient implementation of a minimal triangulation algorithm, 550-561 [Zbl 1019.68809] \textit{Jansen, Klaus}, Scheduling malleable parallel tasks: An asymptotic fully polynomial-time approximation scheme, 562-573 [Zbl 1019.68818] \textit{Kaporis, Alexis C.; Kirousis, Lefteris M.; Lalas, Efthimios G.}, The probabilistic analysis of a greedy satisfiability algorithm, 574-585 [Zbl 1019.68814] \textit{Karavelas, Menelaos I.; Yvinec, Mariette}, Dynamic additively weighted Voronoi diagrams in 2D, 586-598 [Zbl 1019.68608] \textit{Köhler, Ekkehard; Langkau, Katharina; Skutella, Martin}, Time-expanded graphs for flow-dependent transit times, 599-611 [Zbl 1019.90501] \textit{Kolliopoulos, Stavros G.; Steiner, George}, Partially-ordered knapsack and applications to scheduling, 612-624 [Zbl 1040.90033] \textit{Konstantinou, Elisavet; Stamatiou, Yiannis; Zaroliagis, Christos}, A software library for elliptic curve cryptography, 625-636 [Zbl 1019.94500] \textit{Krumke, Sven O.; Rambau, Jörg; Torres, Luis M.}, Real-time dispatching of guided and unguided automobile service units with soft time windows, 637-648 [Zbl 1019.90500] \textit{Laber, Eduardo; Parekh, Ojas; Ravi, R.}, Randomized approximation algorithms for query optimization problems on two processors, 649-661 [Zbl 1019.68820] \textit{Langerman, Stefan; Morin, Pat}, Covering things with things, 662-673 [Zbl 1019.68609] \textit{Lipmann, Maarten; Lu, X.; de Paepe, Willem E.; Sitters, Rene A.; Stougie, Leen}, On-line dial-a-ride problems under a restricted information model, 674-685 [Zbl 1019.90519] \textit{Lorys, Krzysztof; Zwozniak, Grazyna}, Approximation algorithm for the maximum leaf spanning tree problem for cubic graphs, 686-697 [Zbl 1019.68821] \textit{Manzini, Giovanni; Ferragina, Paolo}, Engineering a lightweight suffix array construction algorithm (Extended abstract), 698-710 [Zbl 1019.68633] \textit{Maxová, Jana; Nežetril, Jaroslav}, Complexity of compatible decompositions of Eulerian graphs and their transformations, 711-722 [Zbl 1020.05064] \textit{Mehlhorn, Kurt; Meyer, Ulrich}, External-memory breadth-first search with sublinear I/O, 723-735 [Zbl 1019.68595] \textit{Molloy, Michael; Salavatipour, Mohammad R.}, Frequency channel assignment on planar networks, 736-747 [Zbl 1040.90034] \textit{Näher, Stefan; Zlotowski, Oliver}, Design and implementation of efficient data types for static graphs, 748-759 [Zbl 1019.68528] \textit{Nielsen, Benny K.; Winter, Pawel; Zachariasen, Martin}, An exact algorithm for the uniformly-oriented Steiner tree problem, 760-771 [Zbl 1019.68610] \textit{Ohta, Kenichiro; Sadakane, Kunihiko; Shioura, Akiyoshi; Tokuyama, Takeshi}, A fast, accurate and simple method for pricing European-Asian and Saving-Asian options, 772-784 [Zbl 1046.91062] \textit{Peczarski, Marcin}, Sorting 13 elements requires 34 comparisons, 785-794 [Zbl 1019.68033] \textit{Polzin, Tobias; Daneshmand, Siavash Vahdati}, Extending reduction techniques for the Steiner tree problem, 795-807 [Zbl 1019.68613] \textit{Pruhs, Kirk; Uthaisombut, Patchrawat}, A comparison of multicast pull models, 808-819 [Zbl 1019.68508] \textit{Räcke, Harald; Sohler, Christian; Westermann, Matthias}, Online scheduling for sorting buffers, 820-832 [Zbl 1019.68509] \textit{Schurr, Ingo; Szabó, Tibor}, Finding the sink takes some time. An almost quadratic lower bound for finding the sink of unique sink oriented cubes., 833-844 [Zbl 1040.90035] \textit{Sellmann, Meinolf; Kliewer, Georg; Koberstein, Achim}, Lagrangian cardinality cuts and variable fixing for capacitated network design, 845-858 [Zbl 1040.90004] \textit{Shachnai, Hadas; Tamir, Tami; Woeginger, Gerhard J.}, Minimizing makespan and preemption costs on a system of uniform machines, 859-871 [Zbl 1040.90019] \textit{van Stee, Rob; La Poutré, Han}, Minimizing the total completion time on-line on a single machine, using restarts, 872-883 [Zbl 1019.68510] \textit{Wein, Ron}, High-level filtering for arrangements of conic arcs (Extended abstract), 884-895 [Zbl 1019.68614] \textit{Woeginger, Gerhard J.}, An approximation scheme for cake division with a linear number of cuts, 896-901 [Zbl 1046.91023] \textit{Zhang, Huaming; He, Xin}, A simple linear time algorithm for finding even triangulations of 2-connected bipartite plane graphs, 902-913 [Zbl 1020.05065]