List of accepted papers for SODA 2003: Competitive Queueing Policies for QoS Switches Nir Andelman, Yishay Mansour, An Zhu Data Migration to Minimize the Average Completion Time Yoo-Ah Kim Improved Results for Directed Multicut Anupam Gupta Counting Inversions in Lists Anupam Gupta, Francis Zane Algorithms for k-Colouring and Finding Maximal Independent Sets Jesper Makholm Nielsen An improved approximation algorithm for the partial latin square extension problem Carla Gomes, Rommel Regis, David Shmoys Multidimensional Matching and Fast Search in Suffix Trees Richard Cole, Moshe Lewenstein Unconditional Proof of Tightness of Johnson Bound Venkatesan Guruswami, Igor Shparlinski Non-independent Randomized Rounding Benjamin Doerr Embeddings and Non-approximability of Geometric Problems Venkatesan Guruswami, Piotr Indyk Wavelength Assignment and Generalized Interval Graph Coloring Peter Winkler, Lisa Zhang Equitable Colorings with Constant Number of Colors Sriram Pemmaraju, Alexandr Kostochka, Kittikorn Nakprasit Fault-Tolerant Facility Location Chaitanya Swamy, David Shmoys Improved Bounds on the Average Length of Longest Common Subsequences Lueker George On the Performance of User Equilibria in Traffic Networks Andreas Schulz, Nicolas Stier Moses Smaller Core-Sets for Balls Mihai Badoiu, Kenneth L Clarkson A note on the set systems used for broadcast encryption Alexander Russell, Ravi Kumar Certifying and Repairing Solutions to Large LPs -- How Good are LP-Solvers ? Stefan Funke, Marcel Dhiflaoui, Carsten Kwappik, Kurt Mehlhorn, Michael Seel, Elmar Schoemer, Ralph Schulte, Dennis Weber Mobius-Invariant Natural Neighbor Interpolation Marshall Bern, David Eppstein Inferring Tree Topologies Using Flow Tests Muthukrishnan S, Torsten Suel, Radek Vingralek Online Learning in Online Auctions Avrim Blum, Vijay Kumar, Atri Rudra, Felix Wu An approximation algorithm for cutting out convex polygons Adrian Dumitrescu Better Performance Bounds for Finding the Smallest $k$-Edge Connected Spanning Subgraph of a Multigraph Harold Gabow Inplace 2D Matching in Compressed Images Amihood Amir, Gad Landau, Dina Sokol A spectral technique for random satisfiable 3CNF formulas Abraham Flaxman The cover time of sparse random graphs Alan Frieze, Colin Cooper Faster Approximation Algorithms for the Minimum Latency Problem Aaron Archer, David Williamson Chain decompositions and independent trees in 4-connected graphs Xingxing Yu, Sean Curran, Orlando Lee Dynamic Generators of Topologically Embedded Graphs David Eppstein On the combinatorial complexity of Euclidean Voronoi cells and convex hulls of $d$-dimensional spheres Jean-Daniel Boissonnat, Menelaos Karavelas Algorithms for the predicates of the planar additively weighted Voronoi diagram Menelaos Karavelas, Ioannis Z. Emiris Sublogarithmic Approximation for Telephone Multicast: Path out of Jungle Michael Elkin, Guy Kortsarz Perfect matchings in random graphs with prescribed minimal degree Alan Frieze, Boris Pittel Between O(nm) and O(n^\alpha) Dieter Kratsch, Jerry Spinrad Fully-dynamic two dimensional orthogonal range and line segment intersection reporting in logarithmic time Christian Worm Mortensen Optimal Parallel Selection Yijie Han Pass efficient algorithms for approximating large matrices Petros Drineas, Ravi Kannan Competitiveness via Consensus Andrew Goldberg, Jason Hartline Sparse Distance Preservers and Additive Spanners B\'ela Bollob\'as, Don Coppersmith, Michael Elkin The similarity metric Ming Li, Xin Chen, Xin Li, Bin Ma, Paul Vitanyi On AC0 Implementations of Fusion Trees and Atomic Heaps Mikkel Thorup Embedding $k$-Outerplanar Graphs into $\ell_1$ Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair Quick and good facility location Mikkel Thorup A $(1+\epsilon)$-Approximation Algorithm for Partitioning Hypergraphs Using a New AlgorithmicVersion of the Lov\'asz Local Lemma Mohammad R. Salavatipour Smaller Explicit Superconcentrators Noga Alon, Michael Capalbo Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-up Fedor Fomin, Dimitrios Thilikos A New Approximation Algorithm for the Asymmetric TSP with Triangle Inequality Markus Blaeser Simultaneous Optimization for Concave Costs: Single Sink Aggregation or Single Source Buy-at-Bulk Ashish Goel, Deborah Estrin Allocating Vertex $\pi$-guards in Simple Polygons via Pseudo-Triangulations Bettina Speckmann, Csaba D. TC3th Better Algorithms for High-dimensional Proximity Problems via Asymmetric Embeddings Piotr Indyk Lower Bounds for Embedding of Edit Distance into Normed Spaces Alexandr Andoni, Michel Deza, Anupam Gupta, Piotr Indyk, Sofya Raskhodnikova Approximately Optimal Control of Fluid Networks Lisa Fleischer, Jay Sethuraman A faster and simpler fully dynamic transitive closure Liam Roditty An approximate truthful mechanism for combinatorial auctions with single parameter agents Aaron Archer, Christos Papadimitriou, Kunal Talwar, Eva Tardos Certifying algorithms for recognizing interval graphs and permutation graphs Dieter Kratsch, Ross M. McConnell, Kurt Mehlhorn, Jerry Spinrad Multirate Rearrangeable Clos Networks and a Generalized Bipartite Graph Edge Coloring Problem Hung Ngo, Van Vu Dynamic Routing on Networks with Fixed-Size Buffers William Aiello, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen Random Walks on the Vertices of Transportation Polytopes with Constant Number of Sources Mary Cryan, Martin Dyer, Haiko Muller, Leen Stougie Multi-Embedding and Path Approximation of Metric Spaces Yair Bartal, Manor Mendel Comparing top k lists Ronald Fagin, Ravi Kumar, D. Sivakumar A 5/4-approximation algorithm for minimum 2-edge-connectivity Raja Jothi, Balaji Raghavachari, Subramanian Varadarajan Approximation Algorithm for Embedding Metrics into a Two-dimensional Space Mihai Badoiu Integrality ratio for Group Steiner Trees and Directed Steiner Trees Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang Selection with Monotone Comparison Costs Sampath Kannan, Sanjeev Khanna Binary Space Partitions for 3D Subdivisions John Hershberger, Subhash Suri Matching Planar Maps Helmut Alt, Alon Efrat, GC