An Elementary Construction of Constant-Degree Expanders
Noga Alon and Oded Schwartz and Asaf Shapira
Games of fixed rank: A hierarchy of bimatrix games
Ravi Kannan and Thorsten Theobald
Approximation Algorithms via Contraction Decomposition
Erik D. Demaine and MohammadTaghi Hajiaghayi and Bojan Mohar
A simple storage scheme for strings achieving entropy bounds
Paolo Ferragina and Rossano Venturini
Squarepants in a Tree: Sum of Subtree Clustering and Hyperbolic Pants Decomposition
David Eppstein
Embedding into $l^2_{\infty}$ is Easy, Embedding into $l^3_{\infty}$ is NP-Complete
Jeff Edmonds
Approximation Algorithms for Node-Weighted Buy-at-Bulk Network Design
Chandra Chekuri and MohammadTaghi Hajiaghayi and Guy Kortsarz and Mohammad R. Salavatipour
Approximation algorithms for stochastic and risk-averse optimization
Aravind Srinivasan
Minimizing Movement
Erik D. Demaine and MohammadTaghi Hajiaghayi and Hamid Mahini and Amin Sayedi and Shayan Oveisgharan and Morteza Zadimoghaddam
Multiple Choice Tries and Distributed Hash Tables
Luc Devroye and Gabor Lugosi and Gahyun Park and Wojciech Szpankowski
Reconstruction Using Witness Complexes
Leonidas J. Guibas and Steve Y. Oudot
Model-driven Optimization using Adaptive Probes
Sudipto Guha and Kamesh Munagala
Noisy binary search and its applications
Richard M. Karp and Robert Kleinberg
Maximum $s$-$t$-flow with $k$ crossings in $O(k^3 n \log n)$~time
Jan M. Hochstein and Karsten Weihe
Improved bounds for the symmetric rendezvous value on the line
Q. Han and D. Du and J.C. Vera and L.F. Zuluaga
On the number of tetrahedra with minimum, unit, and distinct volumes in three-space
Adrian Dumitrescu and Csaba D. T\'oth
Ultra-succinct Representation of Ordered Trees
Jesper Jansson and Kunihiko Sadakane and Wing-Kin Sung
Approximate Shortest Paths in Anisotropic Regions
Siu-Wing Cheng and Hyeon-Suk Na and Antoine Vigneron and Yajun Wang
Estimating the Sortedness of a Data Stream
Parikshit Gopalan and T.S. Jayram and Robert Krauthgamer and Ravi Kumar
Quantum algorithm for a generalized hidden shift problem
Andrew M. Childs and Wim van Dam
A 1.875--Approximation Algorithm for the Stable Marriage Problem
Kazuo Iwama and Shuichi Miyazaki and Naoya Yamauchi
Optimization problems in multiple-interval graphs
Ayelet Butman and Danny Hermelin and Moshe Lewenstein and Dror Rawitz
A Near-Optimal Algorithm for Computing the Entropy of a Stream
Amit Chakrabarti and Graham Cormode and Andrew McGregor
Equilibria in Online Games
Roee Engelberg and Josefh (Seffi) Naor
Layered Multicast Scheduling for the L_infinity objective
Qingbo Cai and Vincenzo Liberatore
Deterministic pivoting algorithms for constrained ranking and clustering problems
Anke van Zuylen and Rajneesh Hegde and Kamal Jain and David P. Williamson
On the Separation and Equivalence of Paging Strategies
Spyros Angelopoulos and Reza Dorrigiv and Alejandro Lopez-Ortiz
Strong Price of Anarchy
Michal Feldman and Nir Andelman and Yishay Mansour
Compacting cuts: a new linear formulation for minimum cut
Robert D. Carr and Goran Konjevod and Greg Little and Venkatesh Natarajan and Ojas Parekh
Maximum matching in graphs with an excluded minor
Raphael Yuster and Uri Zwick
Speed Scaling for Weighted Flow Time
Nikhil Bansal and Kirk Pruhs and Cliff Stein
Compressing Rectilinear Pictures and Minimizing Access Control Lists
David A. Applegate and Gruia Calinescu and David S. Johnson and Howard Karloff and Katrina Ligett and Jia Wang
Matrix Scaling by Network Flow
G\"unter Rote and Martin Zachariasen
Single Source Multiroute Flows and Cuts on Uniform Capacity Networks
Henning Bruhn and Jakub Cerny and Alexander Hall and Petr Kolman
k-means++: The Advantages of Careful Seeding
David Arthur and Sergei Vassilvitskii
A 3-approximation algorithm for prize collecting forest problems with submodular penalty functions
Yogeshwer Sharma and David P. Williamson
Island Hopping and Path Colouring with applications to WDM Network Design
Andrew McGregor and Bruce Shepherd
Convergence to approximate Nash equilibria in congestion games
Steve Chien and Alistair Sinclair
A PTAS for TSP with Neighborhoods Among Fat Regions in the Plane
Joseph S. B. Mitchell
Zone Diagrams, Existence, Uniqueness, and Algorithmic Challenge
Tetsuo Asano and Jiri Matousek and Takeshi Tokuyama
Line-of-Sight Networks
Alan Frieze and Jon Kleinberg and R. Ravi and Warren Debany
Approximating the Spanning Star Forest Problem and Its Applications to Genomic Sequence Alignment
C. Thach Nguyen and Jian Shen and Minmei Hou and Li Sheng and Webb Miller and Louxin Zhang
Fast computation of power series solutions of systems of differential equations
Alin Bostan and Frédéric Chyzak and François Ollivier and Bruno Salvy and Éric Schost and Alexandre Sedoglavic
A Faster Cache-Oblivious Shortest-Path Algorithm for Undirected Graphs with Bounded Edge Lengths
Luca Allulli and Peter Lichodzijewski and Norbert Zeh
All-Pairs Bottleneck Paths in Vertex Weighted Graphs
Asaf Shapira, Raphael Yuster and Uri Zwick
Efficient Algorithms for computing all low s-t connectivities and Related Problems
Ramesh Hariharan and Telikepalli Kavitha and Debmalya Panigrahi
Setting Lower Bounds on Truthfulness
Ahuva Mu'alem and Michael Schapira
Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing
Patrick Briest and Piotr Krysta
Semi-oblivious Routing: Lower Bounds
MohammadTaghi Hajiaghayi and Robert Kleinberg and Tom Leighton
Improved Bounds for the Online Steiner Tree Problem in Graphs of Bounded Edge-Asymmetry
Spyros Angelopoulos
Spectral Clustering with Limited Independence
Anirban Dasgupta and John Hopcroft and Ravi Kannan and Pradipta Mitra
The Bandwidth Conjecture for 3-colourable Graphs
Julia Boettcher and Mathias Schacht and Anusch Taraz
Making Deterministic Signatures Quickly
Milan Ruzic
Lower bounds on average-case delay for video-on-demand broadcast protocols
Wei-Lung Dustin Tseng and David Kirkpatrick
Distributed Algorithms for Multicommodity Flow Problems via Approximate Steepest Descent Framework
Baruch Awerbuch and Rohit Khandekar and Satish Rao
Correlation decay and deterministic FPTAS for counting list-colorings of a graph
David Gamarnik and Dmitriy Katz
On Bregman Voronoi Diagrams
Frank Nielsen, Jean-Daniel Boissonnat and Richard Nock
The Communication and Streaming Complexity of Computing the Longest Common and Increasing Subsequences
Xiaoming Sun and David P. Woodruff
Improved Algorithms for Path, Matching, and Packing Problems
Jianer Chen and Songjian Lu and Sing-Hoi Sze and Fenghui Zhang
Cheap Labor Can Be Expensive
Ning Chen and Anna R. Karlin
New Upper Bounds on The Approximability of 3D Strip Packing
Xin Han and Kazuo Iwama and Guochuan Zhang
Optimal dynamic vertical ray shooting in rectilinear planar subdivisions
Yoav Giora and Haim Kaplan
Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lov\'asz extension and non-smooth convex optimization
Fabi\'an A. Chudak and Kiyohito Nagano
Energy Efficient Online Deadline Scheduling
HL Chan and WT Chan and TW Lam and LK Lee and KS Mak and P Wong
Probabilistic analysis of linear programming decoding
Konstantinos Daskalakis and Alex Dimakis and Richard Karp and Martin Wainwright
Succinct Indexes for Strings, Binary Relations and Multi-labeled Trees
J\'er\'emy Barbay and Meng He and J. Ian Munro and S. Srinivasa Rao
Counting Colors in Boxes
Haim Kaplan and Natan Rubin and Micha Sharir and Elad Verbin
Algorithms and Incentives for Robust Ranking
Rajat Bhattacharjee and Ashish Goel
The Independent Even Factor Problem
Satoru IWATA and Kenjiro TAKAZAWA
Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP
Matthias Englert and Heiko Roeglin and Berthold Voecking
Optimal Scale-free Compact Routing Schemes in Doubling Networks
Goran Konjevod and Andrea W. Richa and Donglin Xia
On bounded leg shortest paths problems
Liam Roditty and Michael Segal
A matroid secretary problem
Moshe Babaioff and Nicole Immorlica and Robert Kleinberg
Resilient Search Trees
Irene Finocchi and Fabrizio Grandoni and Giuseppe F. Italiano
Online Vertex Colorings of Random Graphs Without Monochromatic Subgraphs
Martin Marciniszyn and Reto Spöhel
Fast Elimination of Redundant Linear Equations and Reconstruction of Recombination-Free Mendelian Inheritance on a Pedigree
Jing Xiao and Lan Liu and Lirong Xia and Tao Jiang
Linear Programming Relaxations of Maxcut
Wenceslas Fernandez de la Vega and Claire Kenyon-Mathieu
Pull-Based Data Broadcast with Dependencies: Be Fair to Users,not to Items
Julien Robert and Nicolas Schabanel
Approximating Entrpoy from sublinear samples
Mickey Brautbar and Alex Samorodnitsky
Efficient Contention Resolution Protocols for Selfish Agents
Amos Fiat and Yishay Mansour and Uri Nadav
Region-Fault Tolerant Geometric Spanners
Mohammad Ali Abam and Mark de Berg and Mohammad Farshi and Joachim Gudmundsson
Obnoxious Centers in Graphs
Sergio Cabello and G\"unter Rote
Dynamic Pricing for Impatient Bidders
Nikhil Bansal and Ning Chen and Neva Cherniavsky and Atri Rudra and Baruch Schieber and Maxim Sviridenko
Counting good truth assignments of random $k$-SAT formulae
Andrea Montanari and Devavrat Shah
On the k-simple shortest paths problem in weighted directed graphs
Liam Roditty
A lower bound for scheduling mechanisms
George Christodoulou and Elias Koutsoupias and Angelina Vidali
Restricted Strip Covering and the Sensor Cover Problem
Adam L. Buchsbaum and Alon Efrat and Shaili Jain and Suresh Venkatasubramanian and Ke Yi
On Extremal Subgraphs of Random Graphs
Graham Brightwell and Konstantinos Panagiotou and Angelika Steger
Scrambling Adversarial Errors Using Few Random Bits
Adam Smith
Torpid Mixing of Local Markov Chains on 3-Colorings of the Discrete Torus
David Galvin and Dana Randall
Designing And Learning Optimal Finite Support Auctions
Edith Elkind
Harmonic Algorithm for 3-Dimensional Strip packing problem
Nikhil Bansal and Maxim Sviridenko
Efficient Subspace Approximation Algorithms
N. D. Shyamalkumar and K. Varadarajan
Aggregation of Partial Rankings, p-Ratings and Top-m Lists
Nir Ailon
A Polynomial-Time Approximation Scheme for Steiner Tree in Planar Graphs
Glencora Borradaile and Claire Kenyon-Mathieu and Philip Klein
Multiple Source Shortest Paths in a Genus $g$ Graph
Sergio Cabello and Erin W. Chambers
Dynamic Weighted Ancestors
Tsvi Kopelowitz and Moshe Lewenstein
Instability of FIFO in the Permanent Sessions Model at Arbitrarily Small Network Loads
Matthew Andrews
Network Sketching or: "How Much Geometry Hides in Connectivity? -- Part II"
Stefan Funke and Nikola Milosavljevic
Half integral packing, Erd\H{o}s-Pos\'a-Property and Graph Minors
Ken-ichi Kawarabayashi
Deterministic rendezvous, treasure hunts and strongly universal exploration sequences
Amnon Ta-Shma and Uri Zwick
Digraph Measures: Kelly Decompositions, Games, and Orderings
Paul Hunter and Stephan Kreutzer
Better Online Buffer Management
Fei Li and Jay Sethuraman and Clifford Stein
Delaunay refinement for piecewise smooth complexes
Siu-Wing Cheng and Tamal K. Dey and Edgar A. Ramos
Planar graphs are in 1-STRING
J. Chalopin and D. Gonçalves and P. Ochem
A Network Formation Game for Bipartite Exchange Economies
Eyal Even-Dar and Michael Kearns and Siddharth Suri
Considering Suppressed Packets Improves Buffer Management in QoS Switches
Matthias Englert and Matthias Westermann
Multi-Break Rearrangements and Chromosomal Evolution
Max A. Alekseyev and Pavel A. Pevzner
A Divide and Conquer Algorithm for d-Dimensional Arrangement
Moses Charikar and Konstantin Makarychev and Yury Makarychev
Maximum Independent Sets in Graphs of Low Degree
Vadim Lozin and Martin Milanic
Near-Optimal Algorithms for Maximum Constraint Satisfaction Problems
Moses Charikar and Konstantin Makarychev and Yury Makarychev
Finding a Heaviest Triangle is not Harder than Matrix Multiplication
Artur Czumaj and Andrzej Lingas
Efficient Aggregation Algorithms for Probabilistic Data
T.S. Jayram and Satyen Kale and Erik Vee
The k-orientability thresholds for G_{n,p}
Daniel Fernholz and Vijaya Ramachandran
The Quantum Schur and Clebsch-Gordan Transforms:I. Efficient Qudit Circuits
Dave Bacon and Isaac L. Chuang and Aram W. Harrow
Faster dynamic matchings and vertex connectivity
Piotr Sankowski
A linear work, $O(n^{1/6})$ time, parallel algorithm for solving planar Laplacians
Ioannis Koutis and Gary Miller
The Approximation Complexity of Win-Lose Games
Xi Chen and Shang-Hua Teng and Paul Valiant
The Random Graph Threshold for k-orientiability and a Fast Algorithm for Optimal Multiple-Choice Allocation
Julie Cain and Peter Sanders and Nick Wormald
Polynomial Approximation Schemes for Smoothed And Random Instances of Multidimensional Bin Packing
David Karger and Krzysztof Onak
An unbiased pointing operator for unlabeled structures, with applications to counting and sampling
Manuel Bodirsky and Eric Fusy and Mihyun Kang and Stefan Vigerske
Whole Genome Duplications and Genome Halving Theorem
Max A. Alekseyev and Pavel A. Pevzner
An Algebraic Algorithm for Weighted Linear Matroid Intersection
Nicholas J. A. Harvey
Matrix-Vector Multiplication in Sub-Quadratic Time (Some Preprocessing Required)
Ryan Williams
Randomization Does Not Help Searching Predecessors
Mihai Patrascu and Mikkel Thorup
An Efficient Cost-Sharing Mechanism for the Prize-Collecting Steiner Forest Problem
A. Gupta and J. Konemann and S. Leonardi and R. Ravi and G. Schaefer
Path-Independent Load Balancing With Unreliable Machines
James Aspnes and Yang Richard Yang and Yitong Yin
Quantum Algorithms for Simon's Problem over General Groups
Gorjan Alagic and Cristopher Moore and Alexander Russell
Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion
Ittai Abraham and Yair Bartal and Ofer Neiman
Approximation Algorithms for Embedding General Metrics Into Trees
Mihai Badoiu and Piotr Indyk and Anastasios Sidiropoulos
A Near-Linear Time Constant Factor Approximation for Euclidean Bi-chromatic Matching (Cost)
Piotr Indyk
The Effectiveness of Stackelberg Strategies and Tolls for Network Congestion Games
Chaitanya Swamy
Separating Populations with Small Data
Kamalika Chaudhuri and Eran Halperin and Satish Rao and Shuheng Zhou
Fractional Packing in Ideal Clutters
Yuji Matsuoka
On Testable Properties in Bounded Degree Graphs
Artur Czumaj and Christian Sohler
Tree Exploration with Logarithmic Memory
Gasieniec and Pelc and Radzik and Zhang
Sandpile transience on the grid is polynomially bounded
Laszlo Babai and Igor Gorodezky
Geometric and Topological Guarantees for the Wrap Reconstruction Algorithm
Edgar A. Ramos and Bardia Sadri
Complexity of Delaunay triangulation for points on lower-dimensional polyhedra
Nina Amenta and Dominique Attali and Olivier Devillers