The paper title/and or authors listed here appear as originally received. All paper titles and authors will be listed correctly in the final printed program distributed on-site.
FPTAS for Mixed-integer Polynomial Optimization with a Fixed Number of Variables
J. A. De Loera, R. Hemmecke, 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, Jurek Czyzowicz, Zhicheng Gao, 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, Luca de Alfaro and Thomas A. Henzinger
Distributed Selfish Load Balancing
Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul Goldberg, 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, Mordecai Golin, 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, Thomas Hackl, Clemens Huemer, Ferran Hurtado, 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, Uriel Feige, MohammadTaghi Hajiaghayi and Mohammad R. Salavatipour
Randomized Online Algorithms for Minimum Metric Bipartite Matching
Adam Meyerson, Akash Nanavati and Laura Poplawski
Cache-Oblivious String Dictionaries
Gerth Střlting Brodal and Rolf Fagerberg
Superiority and Complexity of the Spaced Seeds
Ming Li, Bin Ma and Zhang Louxin
Bottleneck Links, Variable Demand, and the Tragedy of the Commons
Richard Cole, Yevgeniy Dodis and Tim Roughgarden
Morphing Orthogonal Planar Graph Drawings
Anna Lubiw, 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, Mike Paterson and Uri Zwick
Analyzing BitTorrent and Related Peer-to-Peer Networks
David Arthur and Rina Panigrahy
Finding Nucleolus of Flow Game
Xiaotie Deng, Qizhi Fang and Xiaoxun Sun
Trading Off Space for Passes in Graph Streaming Problems
Camil Demetrescu, 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, Kevin Chen, Radu Mihaescu and Satish Rao
Non-Cooperative Multicast and Facility Location Games
Chandra Chekuri, Julia Chuzhoy, Liane Lewin-Eytan, Joseph (Seffi) Naor and Ariel Orda
The Price of Being Near-Sighted
Fabian Kuhn, 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, 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, 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
Antar Bandyopadhyay and David Gamarnik
Improved Embeddings of Graph Metrics into Random Trees
Kedar Dhamdhere, Anupam Gupta and Harald Raecke
Directed Metrics and Directed Graph Partitioning Problems
Moses Charikar, Konstantin Makarychev and Yury Makarychev
Approximating Unique Games
Anupam Gupta and Kunal Talwar
On the Capacity of Information Networks
Micah Adler, Nicholas J. A. Harvey, Kamal Jain, 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, S.P. Fekete, 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, Rorbert D. Kleinberg, Tom Leighton and Harald Raecke
Single-Value Combinatorial Auctions and Implementation in Undominated Strategies
Moshe Babaioff, 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, Luis Rademacher, Santosh Vempala and Grant Wang
Upper Degree-Constrained Partial Orientations
Harold N. Gabow
Local versus Global Properties of Metric Spaces
Sanjeev Arora, Laszlo Lovasz, Ilan Newman, Yuval Rabani and Santosh Vempala
A Computational Study of External-Memory BFS Algorithms
Deepak Ajwani, 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, 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, Tali Kaufman, 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, Don Coppersmith and Maxim Sviridenko
Weighted Isotonic Regression under $L_1$ Norm
Stanislav Angelov, Boulos Harb, 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, Stefan Eilts, Eyal Even-Dar, Yishay Mansour and Liam Roditty
Streaming and Sublinear Approximation of Entropy and Information Distances
Sudipto Guha, Andrew McGregor and Suresh Venkatasubramanian
Leontief Economies Encode NonZero Sum Two-Player Games
B. Codenotti, A. Saberi, 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, 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, Bernard Chazelle, Seshadhri Comandur and Ding Liu
Approximating the k-Multicut Problem
Daniel Golovin, 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, Yonatan Aumann, Gary Benson, Avivit Levy, Ohad Lipsky, Ely Porat, 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 and K.S. Liu
Oblivious String Embeddings and Edit Distance Approximations
Tugkan Batu, Funda Ergun and Cenk Sahinalp
Anisotropic Surface Meshing
Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos and Rephael Wenger
Max-Tolerance Graphs as Intersection Graphs: Cliques, Cycles, and Recognition
Michael Kaufmann, Jan Kratochvil, 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, Daniel Stefankovic, 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, Michael J. Nelson and Jonathan Z. Sun
Lower Bounds for Asymmetric Communication Channels and Distributed Source Coding
Micah Adler, Erik D. Demaine, Nicholas J. A. Harvey and Mihai Patrascu
Scalable Leader Election
Valerie King, Jared Saia, 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, Ryan Williams and Shan Leung Maverick Woo
Oblivious Network Design
Anupam Gupta, 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, Robert Kleinberg and Tom Leighton
Sampling Binary Contingency Tables with a Greedy Start
Ivona Bezakova, Nayantara Bhatnagar and Eric Vigoda
Sampling Algorithms for $\ell_2$ Regression and Applications to Matrix Approximation
Petros Drineas, Michael W. Mahoney and S. Muthukrishnan
The Hunting of the Bump: On Maximizing Statistical Discrepancy
Deepak Agarwal, Jeff Phillips and Suresh Venkatasubramanian
Analysis of Incomplete Data and an Inner-Dimension Helly Theorem
Jie Gao, Michael Langberg and Leonard J. Schulman
Dynamic Competitive Binary Search Trees
Chengwen Chris Wang, Jonathan Derryberry and Daniel Sleator
Trees, Markov convexity, and Finding Near-optimal Embeddings
James R. Lee, Assaf Naor and Yuval Peres
An Algorithmic Friedman-Pippenger Theorem on Tree Embeddings and Applications to Routing
Domingos Dellamonica Jr. and Yoshiharu Kohayakawa
Finding Large Sticks and Potatoes in Polygons
Olaf Hall-Holt, Matthew Katz, Piyush Kumar, 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, 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, Lisa Fleischer and Atri Rudra
8/7-Approximation Algorithm for 1,2-TSP
Piotr Berman and 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, 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