11. ESA 2003: Budapest, Hungary

Invited Lectures

• Bernard Chazelle:
  Sublinear Computing. 1
  
• Roberto Tamassia:
  Authenticated Data Structures. 2-5
  
• Éva Tardos:
  Approximation Algorithms and Network Games. 6
  

Contributed Papers: Design and Analysis Track

• Pankaj K. Agarwal, Lars Arge, Jun Yang, Ke Yi:
  I/O-Efficient Structures for Orthogonal Range-Max and Stabbing-Max Queries. 7-18
  
• Mansoor Alicherry, Randeep Bhatia:
  Line System Design and a Generalized Coloring Problem. 19-30
  
• Aaron Archer, Ranjithkumar Rajagopalan, David B. Shmoys:
  Lagrangian Relaxation for the k-Median Problem: New Insights and Continuity Properties. 31-42
  
• Nikhil Bansal, Avrim Blum, Shuchi Chawla, Kedar Dhamdhere:
  Scheduling for Flow-Time with Admission Control. 43-54
  
• Reuven Bar-Yehuda, Guy Even, Shimon Shahar:
  On Approximating a Geometric Prize-Collecting Traveling Salesman Problem with Time Windows: Extended Abstract. 55-66
  
• Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Kirk Pruhs:
  Semi-clairvoyant Scheduling. 67-77
  
• Alex R. Berg, Tibor Jordán:
  Algorithms for Graph Rigidity and Scene Analysis. 78-89
  
• Therese C. Biedl, Erik D. Demaine, Alexander Golynski, Joseph Douglas Horton, Alejandro López-Ortiz, Guillaume Poirier, Claude-Guy Quimper:
  Optimal Dynamic Video-on-Demand Using Adaptive Broadcasting. 90-101
  
• Liad Blumrosen, Noam Nisan, Ilya Segal:
  Multi-player and Multi-round Auctions with Severely Bounded Communication. 102-113
  
• Gruia Calinescu, Sanjiv Kapoor, Alexander Olshevsky, Alexander Zelikovsky:
  Network Lifetime and Power Assignment in ad hoc Wireless Networks. 114-126
  
• Otfried Cheong, Xavier Goaoc, Hyeon-Suk Na:
  Disjoint Unit Spheres admit at Most Two Line Transversals. 127-135
  
• Kai-Min Chung, Hsueh-I Lu:
  An Optimal Algorithm for the Maximum-Density Segment Problem. 136-147
  
• Graham Cormode, S. Muthukrishnan:
  Estimating Dominance Norms of Multiple Data Streams. 148-160
  
• Valentina Damerow, Friedhelm Meyer auf der Heide, Harald Räcke, Christian Scheideler, Christian Sohler:
  Smoothed Motion Complexity. 161-171
  
• Mark de Berg:
  Kinetic Dictionaries: How to Shoot a Moving Target. 172-183
  
• Anders Dessmark, Pierre Fraigniaud, Andrzej Pelc:
  Deterministic Rendezvous in Graphs. 184-195
  
• Friedrich Eisenbrand:
  Fast Integer Programming in Fixed Dimension. 196-207
  
• Dotan Emanuel, Amos Fiat:
  Correlation Clustering - Minimizing Disagreements on Arbitrary Weighted Graphs. 208-220
  
• Fedor V. Fomin, Dimitrios M. Thilikos:
  Dominating Sets and Local Treewidth. 221-229
  
• Stefan Funke, Domagoj Matijevic, Peter Sanders:
  Approximating Energy Efficient Paths in Wireless Multi-hop Networks. 230-241
  
• Naveen Garg, Rohit Khandekar, Keshav Kunal, Vinayaka Pandit:
  Bandwidth Maximization in Multicasting. 242-253
  
• Cyril Gavoille, Christophe Paul:
  Optimal Distance Labeling for Interval and Circular-Arc Graphs. 254-265
  
• Magnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki, Hiroki Yanagisawa:
  Improved Approximation of the Stable Marriage Problem. 266-277
  
• Sariel Har-Peled, Soham Mazumdar:
  Fast Algorithms for Computing the Smallest k-Enclosing Disc. 278-288
  
• Refael Hassin, Asaf Levin:
  The Minimum Generalized Vertex Cover Problem. 289-300
  
• Thomas Hofmeister:
  An Approximation Algorithm for MAX-2-SAT with Cardinality Constraint. 301-312
  
• Bala Kalyanasundaram, Mahendran Velauthapillai:
  On-Demand Broadcasting Under Deadline. 313-324
  
• Alexis C. Kaporis, Christos Makris, Spyros Sioutas, Athanasios K. Tsakalidis, Kostas Tsichlas, Christos D. Zaroliagis:
  Improved Bounds for Finger Search on a RAM. 325-336
  
• Menelaos I. Karavelas, Mariette Yvinec:
  The Voronoi Diagram of Planar Convex Objects. 337-348
  
• Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-Shamir:
  Buffer Overflows of Merging Streams. 349-360
  
• Alexander Kesselman, Yishay Mansour, Rob van Stee:
  Improved Competitive Guarantees for QoS Buffering. 361-372
  
• Samir Khuller, Yoo Ah Kim, Yung-Chun (Justin) Wan:
  On Generalized Gossiping and Broadcasting (Extended Abstract). 373-384
  
• Guy Kortsarz, Sunil M. Shende:
  Approximating the Achromatic Number Problem on Bipartite Graphs. 385-396
  
• Miroslaw Kutylowski, Wojciech Rutkowski:
  Adversary Immune Leader Election in ad hoc Radio Networks. 397-408
  
• Mohammad Mahdian, Martin Pál:
  Universal Facility Location. 409-421
  
• Grzegorz Malewicz:
  A Method for Creating Near-Optimal Instances of a Certified Write-All Algorithm (Extended Abstract). 422-433
  
• Ulrich Meyer, Norbert Zeh:
  I/O-Efficient Undirected Shortest Paths. 434-445
  
• Shmuel Safra, Oded Schwartz:
  On the Complexity of Approximating TSP with Neighborhoods and Related Problems. 446-458
  
• Jiri Sgall, Gerhard J. Woeginger:
  A Lower Bound for Cake Cutting. 459-469
  
• Micha Sharir, Hayim Shaul:
  Ray Shooting and Stone Throwing. 470-481
  
• Aleksandrs Slivkins:
  Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs. 482-493
  
• Csaba D. Tóth:
  Binary Space Partition for Orthogonal Fat Rectangles. 494-505
  
• Dekel Tsur:
  Sequencing by Hybridization in Few Rounds. 506-516
  
• Biing-Feng Wang, Yong-Hsian Hsieh, Li-Pu Yeh:
  Efficient Algorithms for the Ring Loading Problem with Demand Splitting. 517-526
  
• Gerhard J. Woeginger:
  Seventeen Lines and One-Hundred-and-One Points. 527-531
  
• Nicola Wolpert:
  Jacobi Curves: Computing the Exact Topology of Arrangements of Non-singular Algebraic Curves. 532-543
  

Contributed Papers: Engineering and Application Track

• Pankaj K. Agarwal, Shankar Krishnan, Nabil H. Mustafa, Suresh Venkatasubramanian:
  Streaming Geometric Optimization Using Graphics Hardware. 544-555
  
• Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Leonid Khachiyan:
  An Efficient Implementation of a Quasi-polynomial Algorithm for Generating Hypergraph Transversals. 556-567
  
• Ulrik Brandes, Marco Gaertler, Dorothea Wagner:
  Experiments on Graph Clustering Algorithms. 568-579
  
• Zhi-Zhong Chen, Tao Jiang, Guohui Lin, Romeo Rizzi, Jianjun Wen, Dong Xu, Ying Xu:
  More Reliable Protein NMR Peak Assignment via Improved 2-Interval Scheduling. 580-592
  
• Luca Di Gaspero, Johannes Gärtner, Guy Kortsarz, Nysret Musliu, Andrea Schaerf, Wolfgang Slany:
  The Minimum Shift Design Problem: Theory and Practice. 593-604
  
• Marianne Durand, Philippe Flajolet:
  Loglog Counting of Large Cardinalities (Extended Abstract). 605-617
  
• Friedrich Eisenbrand, Stefan Funke, Joachim Reichel, Elmar Schömer:
  Packing a Trunk. 618-629
  
• Kaspar Fischer, Bernd Gärtner, Martin Kutz:
  Fast Smallest-Enclosing-Ball Computation in High Dimensions. 630-641
  
• Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier:
  Automated Generation of Search Tree Algorithms for Graph Modification Problems. 642-653
  
• Miguel Granados, Peter Hachenberger, Susan Hert, Lutz Kettner, Kurt Mehlhorn, Michael Seel:
  Boolean Operations on 3D Selective Nef Complexes: Data Structure, Algorithms, and Implementation. 654-666
  
• Sven Grothklags:
  Fleet Assignment with Connection Dependent Ground Times. 667-678
  
• Irit Katriel, Peter Sanders, Jesper Larsson Träff:
  A Practical Minimum Spanning Tree Algorithm Using the Cycle Property. 679-690
  
• Gunnar W. Klau, Ivana Ljubic, Petra Mutzel, Ulrich Pferschy, René Weiskircher:
  The Fractional Prize-Collecting Steiner Tree Problem on Trees: Extended Abstract. 691-702
  
• Luigi Laura, Stefano Leonardi, Stefano Millozzi, Ulrich Meyer, Jop F. Sibeyn:
  Algorithms and Experiments for the Webgraph. 703-714
  
• Christian Liebchen:
  Finding Short Integral Cycle Bases for Cyclic Timetabling. 715-726
  
• Matthias Müller-Hannemann, Ute Zimmermann:
  Slack Optimization of Timing-Critical Nets. 727-739
  
• Piotr Sankowski:
  Multisampling: A New Approach to Uniform Sampling and Approximate Counting. 740-751
  
• Meinolf Sellmann, Norbert Sensen, Larissa Timajev:
  Multicommodity Flow Approximation Used for Exact Graph Partitioning. 752-764
  
• Hisao Tamaki:
  A Linear Time Heuristic for the Branch-Decomposition of Planar Graphs. 765-775
  
• Dorothea Wagner, Thomas Willhalm:
  Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs. 776-787
  

Last update Sat May 18 18:27:30 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page