Papers Accepted to SODA 2006
----------------------------
FPTAS for mixed-integer polynomial optimization with a fixed number of variables
J. A. De Loera and R. Hemmecke and M. Koeppe and R. Weismantel
Critical chromatic number and the complexity of perfect packings in graphs
Daniela Kuehn and Deryk Osthus
Simultaneous Diagonal Flips in Plane Triangulations
Prosenjit Bose and Jurek Czyzowicz and Zhicheng Gao and Pat Morin and David R. Wood
Quantum Verification of Matrix Products
Harry Buhrman and Robert Spalek
Efficient Construction of Unit Circular-Arc Models
Min Chih Lin and Jayme L. Szwarcfiter
The Complexity of Quantitative Concurrent Parity Games
Krishnendu Chatterjee and Luca de Alfaro and Thomas A. Henzinger
Distributed Selfish Load Balancing
Petra Berenbrink and Tom Friedetzky and Leslie Ann Goldberg and Paul Goldberg and Zengjian Hu and Russell Martin
Finding the Depth Order of Fat Objects
Mark de Berg and Chris Gray
The Knuth-Yao Quadrangle-Inequality Speedup is a Consequence of Total-Monotonicity
Wolfgang Bein and Mordecai Golin and Larry Larmore and Yan Zhang
Cake Cutting Really is Not a Piece of Cake
Jeff Edmonds and Kirk Pruhs
On The Chromatic Number of Some Geometric Hypergraphs
Shakhar Smorodinsky
A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
Vadim V. Lozin and Martin Milanic
On the Number of Plane Graphs
Oswin Aichholzer and Thomas Hackl and Clemens Huemer and Ferran Hurtado and Hannes Krasser and Birgit Vogtenhuber
An Improved Approximation Algorithm for Combinatorial Auctions with Submodular Bidders
Shahar Dobzinski and Michael Schapira
Balanced Allocation on Graphs
Krishnaram Kenthapadi and Rina Panigrahy
Entropy based Nearest Neighbor Search in High Dimensions
Rina Panigrahy
Correlation Clustering with a Fixed Number of Clusters
Ioannis Giotis and Venkatesan Guruswami
Spanners for Doubling Metrics with Small Hop Diameter
T-H. Hubert Chan and Anupam Gupta
Combination Can Be Hard: Approximability of the Unique Coverage Problem
Erik D. Demaine and Uriel Feige and MohammadTaghi Hajiaghayi and Mohammad R. Salavatipour
Randomized Online Algorithms for Minimum Metric Bipartite Matching
Adam Meyerson, Akash Nanavati, Laura Poplawski
Cache-Oblivious String Dictionaries
Gerth Střlting Brodal and Rolf Fagerberg
Superiority and complexity of the spaced seeds
Ming Li, Bin Ma andZhang Louxin
Bottleneck Links, Variable Demand, and the Tragedy of the Commons
Richard Cole and Yevgeniy Dodis and Tim Roughgarden
Morphing Orthogonal Planar Graph Drawings
Anna Lubiw and Mark Petrick and Michael J. Spriggs
Metric Cotype
Manor Mendel and Assaf Naor
Tight Bounds on Probabilistic Embedding of Series-Parallel Graphs
Yuval Emek and David Peleg
Overhang
Mike Paterson and Uri Zwick
A Deterministic Subexponential Algorithm for Solving Parity Games
Marcin Jurdzi\'{n}ski and Mike Paterson and Uri Zwick
Analyzing BitTorrent and Related Peer-to-Peer Networks
David Arthur and Rina Panigraphy
Finding Nucleolus of Flow Game
Xiaotie Deng and Qizhi Fang and Xiaoxun Sun
Trading off space for passes in graph streaming problems
Camil Demetrescu and Irene Finocchi and Andrea Ribichini
An O(n log n) algorithm for maximum st-flow in a directed planar graph
Glencora Borradaile and Philip Klein
Four point conditions and exponential neighborhoods for the symmetric TSP
V.Deineko and B.Klinz and G.Woeginger
On the Number of Crossing-Free Matchings, (Cycles, and Partitions)
Micha Sharir and Emo Welzl
On the tandem duplication-random loss model of genome rearrangement
Kamalika Chaudhuri and Kevin Chen and Radu Mihaescu and Satish Rao
Non-Cooperative Multicast and Facility Location Games
Chandra Chekuri and Julia Chuzhoy and Liane Lewin-Eytan and Joseph (Seffi) Naor and Ariel Orda
The Price of Being Near-Sighted
Fabian Kuhn and Thomas Moscibroda and Roger Wattenhofer
Searching in dynamic three-dimensional convex hulls and planar Voronoi diagrams, and approximate range counting
Haim Kaplan and Micha Sharir
Measure and Conquer: A Simple $O (2^{0.288\,n})$ Independent Set Algorithm
Fedor Fomin and Fabrizio Grandoni and Dieter Kratsch
Spanners and emulators with sublinear distance errors
Mikkel Thorup and Uri Zwick
A New Approach to Proving Upper Bounds for MAX-2-SAT
Arist Kojevnikov and Alexander S. Kulikov
Subgraph characterization of Red/Blue-Split Graphs and Konig Egervary Graphs.
Ephraim Korach, Thanh Nguyen and Britta Wienand
Design of Data Structures for Mergeable Trees
Loukas Georgiadis and Robert E. Tarjan and Renato F. Werneck
A Robust Maximum Completion Time Measure for Scheduling
Moses Charikar and Samir Khuller
Squeezing Succinct Data Structures into Entropy Bounds
Kunihiko Sadakane and Roberto Grossi
The Prize-Collecting Generalized Steiner Tree Problem Via A New Approach Of Primal-Dual Schema
Kamal Jain and MohammadTaghi Hajiaghayi
Solving Random Satisfiable 3CNF Formulas in Expected Polynomial Time
Michael Krivelevich and Dan Vilenchik
Revenue Maximization When Bidders Have Budgets
Zoe Abrams
DAG-width - Connectivity Measure for Directed Graphs
Jan Obdrzalek
Testing graph isomorphism
Eldar Fischer and Arie Matsliah
Counting without sampling. New algorithms for enumeration problems using statistical physics
David Gamarnik
Improved Embeddings of Graph Metrics into Random Trees
Kedar Dhamdhere and Anupam Gupta and Harald Raecke
Directed Metrics and Directed Graph Partitioning Problems
Moses Charikar and Konstantin Makarychev and Yury Makarychev
Approximating Unique Games
Anupam Gupta and Kunal Talwar
On the Capacity of Information Networks
Micah Adler and Nicholas J. A. Harvey and Kamal Jain and Robert D. Kleinberg and April Rasala Lehman
Computing sequential equilibria for two-player games
Peter Bro Miltersen and Troels Bjerre Sorensen
Deterministic boundary recognition and topology extraction for large sensor networks
A. Kroeller and S.P. Fekete and D. Pfisterer and S. Fischer
A simple GAP-canceling algorithm for the generalized maximum flow problem
Mateo Restrepo and David P. Williamson
Linear programming and unique sink orientations
Bernd Gaertner and Ingo Schurr
Implicit Dictionaries with O(1) Modifications per Update and Fast Search
Gianni Franceschini and J. Ian Munro
Certifying Large Branch-width
Sang-il Oum and Paul Seymour
New Lower Bounds for Oblivious Routing in Undirected Graphs
Mohammad Taghi Hajiaghayi and Rorbert D. Kleinberg and Tom Leighton and Harald Raecke.
Single-Value Combinatorial Auctions and Implementation in Undominated Strategies
Moshe Babaioff and Ron Lavi and Elan Pavlov
Facility Location with Hierarchical Facility Costs
Zoya Svitkina and Eva Tardos
Relating singular values and discrepancy of weighted directed graphs
Steven Butler
Matrix Approximation and Projective Clustering via Volume Sampling
Amit Deshpande and Luis Rademacher and Santosh Vempala and Grant Wang
Upper Degree-Constrained Partial Orientations
Harold N. Gabow
Local versus Global Properties of Metric Spaces
Sanjeev Arora and Laszlo Lovasz and Ilan Newman and Yuval Rabani and Santosh Vempala
A Computational Study of External-Memory BFS Algorithms
Deepak Ajwani and Roman Dementiev and Ulrich Meyer
A Semidefinite Programming Approach to Tensegrity Theory and Realizability of Graphs
Anthony Man-Cho So and Yinyu Ye
Scheduling Unit Tasks to Minimize the Number of Idle Periods: A Polynomial Time Algorithm for Offline Dynamic Power Management
Philippe Baptiste
Reducing Tile Complexity for Self-Assembly Through Temperature Programming
Ming-Yang Kao and Robert Schweller
Coresets for Approximating the Extent of Shallow Levels
Pankaj K. Agarwal and Sariel Har-Peled and Hai Yu
Efficient Algorithms for Substring Near Neighbor Problem
Alexandr Andoni and Piotr Indyk
Robbing the bandit blind: Less regret in online geometric optimization against an adaptive adversary.
Varsha Dani and Thomas P. Hayes
Testing Triangle-Freeness in General Graphs
Noga Alon and Tali Kaufman and Michael Krivelevich and Dana Ron
Constraint Solving via Fractional Edge Covers
Martin Grohe and Dániel Marx
Maintaining Significant Stream Statistics over Sliding Windows
L.K. Lee and H.F. Ting
Improved approximation algorithms for broadcast scheduling
Nikhil Bansal and Don Coppersmith and Maxim Sviridenko
Weighted Isotonic Regression under $L_1$ Norm
Stanislav Angelov and Boulos Harb and Sampath Kannan and Li-San Wang
Approximation Algorithms for Wavelet Transform Coding of Data Streams
Sudipto Guha and Boulos Harb
On Nash Equilibria for a Network Creation Game
Susanne Albers and Stefan Eilts and Eyal Even-Dar and Yishay Mansour and Liam Roditty
Streaming and Sublinear Approximation of Entropy and Information Distances
Sudipto Guha and Andrew McGregor and Suresh Venkatasubramanian
Leontief Economies Encode NonZero Sum Two-Player Games
B. Codenotti and A. Saberi and K. Varadarajan and Y. Ye
Equilibria for Economies with Production: Constant-Returns Technologies and Production Planning Constraints
K. Jain and K. Varadarajan
Asymmetric Balanced Allocation with Simple Hash Functions
Philipp Woelfel
On the Competitive Ratio of Evaluating Priced Functions
Ferdinando Cicalese and Eduardo Sany Laber
Improved space-optimal algorithm for estimating frequency moments of data streams
Sumit Ganguly and Deepanjan Kesh and Chandan Saha
An asymptotic approximation algorithm for 3D-strip packing
Klaus Jansen and Roberto Solis-Oba
Many distances in planar graphs
Sergio Cabello
Self-Improving Algorithms
Nir Ailon AND Bernard Chazelle AND Seshadhri Comandur AND Ding Liu
Approximating the k-Multicut Problem
Daniel Golovin and Viswanath Nagarajan and Mohit Singh
Computing Steiner Minimum Trees in Hamming Metric
Ernst Althaus and Rouven Naujoks
Pattern Matching with Address Errors: Rearrangement Distances
Amihood Amir and Yonatan Aumann and Gary Benson and Avivit Levy and Ohad Lipsky and Ely Porat and S. Skiena and U. Vishne
On $k$-Median Clustering in High Dimensions
Ke Chen
Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling
Ho-Leung Chan, T.W. Lam, K.S. Liu
Oblivious String Embeddings and Edit Distance Approximations
Tugkan Batu and Funda Ergun and Cenk Sahinalp
Anisotropic Surface Meshing
Siu-Wing Cheng and Tamal K. Dey and Edgar A. Ramos and Rephael Wenger
Max-Tolerance Graphs as Intersecton Graphs: Cliques, Cycles, and Recognition
Michael Kaufmann and Jan Kratochvil and Katharina Lehmann and Amarendran Subramanian
The Space Complexity of Pass-Efficient Algorithms for Clustering Census Data
Kevin L. Chang and Ravi Kannan
Accelerating Simulated Annealing for Combinatorial Counting
Ivona Bezakova and Daniel Stefankovic and Eric Vigoda and Vijay Vazirani
Generating all vertices of a polyhedron is hard.
Khachiyan, Boros, Borys, Elbassioni, Gurvich
Cache-Oblivious Dynamic Programming
Rezaul Alam Chowdhury and Vijaya Ramachandran
The Rainbow Skip Graph: A Fault-Tolerant Constant-Degree Distributed Data Structure
Michael T. Goodrich and Michael J. Nelson and Jonathan Z. Sun
Lower Bounds for Asymmetric Communication Channels and Distributed Source Coding
Micah Adler and Erik D. Demaine and Nicholas J. A. Harvey and Mihai Patrascu
Scalable Leader Election
Valerie King and Jared Saia and Vishal Sanwalani and Erik Vee
On the diameter of Eulerian orientations of graphs
Laszlo Babai
Single-Minded Unlimited Supply Pricing on Sparse Instances
Patrick Briest and Piotr Krysta
Confronting Hardness Using A Hybrid Approach
Virginia Vassilevska and Ryan Williams and Shan Leung Maverick Woo
Oblivious Network Design
Anupam Gupta and MohammadTaghi Hajiaghayi and Harald Raecke
(Almost) Tight Approximation Algorithms for Maximizing General Assignment Problems
Lisa K. Fleischer, Michel X. Goemans, Vahab S. Mirrokni and Maxim Sviridenko
Improved Lower and Upper Bounds for Universal TSP in Planar Metrics
Mohammad T. Hajiaghayi and Robert Kleinberg and Tom Leighton
Sampling Binary Contingency Tables with a Greedy Start
Ivona Bezakova and Nayantara Bhatnagar and Eric Vigoda
Sampling Algorithms for $\ell_2$ Regression and Applications to Matrix Approximation
Petros Drineas and Michael W. Mahoney and S. Muthukrishnan
The Hunting of the Bump: On Maximizing Statistical Discrepancy
Deepak Agarwal and Jeff Phillips and Suresh Venkatasubramanian
Analysis of Incomplete Data and an Inner-Dimension Helly Theorem
Jie Gao and Michael Langberg and Leonard J. Schulman
Dynamic Competitive Binary Search Trees
Chengwen Chris Wang and Jonathan Derryberry and Daniel Sleator
Trees, Markov convexity, and finding near-optimal embeddings
James R. Lee and Assaf Naor and Yuval Peres
An algorithmic Friedman-Pippenger theorem on tree embeddings and applications to routing (Extended Abstract)
Domingos Dellamonica Jr. and Yoshiharu Kohayakawa
Finding Large Sticks and Potatoes in Polygons
Olaf Hall-Holt and Matthew Katz and Piyush Kumar and Joseph S. B. Mitchell and Arik Sityon
Slow mixing of Glauber dynamics via topological obstructions
Dana Randall
A Near-Tight Approximation Lower Bound and Algorithm for the Kidnapped Robot Problem
Sven Koenig and Apurva Mudgal and Craig Tovey
Knapsack Auctions
Gagan Aggarwal and Jason Hartline
Ordering by weighted number of wins gives a good ranking for weighted tournaments
Don Coppersmith and Lisa Fleischer and Atri Rudra
8/7-Approximation Algorithm for 1,2-TSP
Piotr Berman, Marek Karpinski
A Dynamic Data Structure for 3-d Convex Hulls and 2-d Nearest Neighbor Queries
Timothy M. Chan
Tightening Non-simple Paths and Cycles on Surfaces
\'Eric Colin de Verdi\`ere and Jeff Erickson
All-Pairs Shortest Paths for Unweighted Undirected Graphs in o(mn) Time
Timothy M. Chan
The Complexity of Matrix Completion
Nicholas J. A. Harvey and David R. Karger
Query-Efficient Algorithms for Polynomial Interpoltion over Composites
Parikshit Gopalan
Anytime Algorithms for Multi-Armed Bandit Problems
Robert Kleinberg
Rank/Select Operations on Large Alphabets: a Tool for Text Indexing
Alexander Golynski and Ian Munro and Srinivasa S. Rao
Improved lower bounds for embeddings into L_1
Robert Krautghamer and Yuval Rabani
A general approach for incremental approximation and hierarchical clustering
Guolong Lin and Chandrashekhar Nagarajan and Rajmohan Rajaraman and David P. Williamson
l_2^2 spreading metrics for vertex ordering problems
Moses Charikar and MohammadTaghi Hajiaghayi and Howard Karloff and Satish Rao