## SODA 2009 Invited speakers

• Michael I. Jordan, University of California at Berkeley
• Yuval Peres, Microsoft Research
• Volker Strassen, University of Konstanz, Germany

## SODA 2009 Accepted papers, without abstracts

• Jeff Edmonds and Kirk Pruhs. Scalably Scheduling Processes with Arbitrary Speedup Curves
• Zdenek Dvorak, Ken-ichi Kawarabayashi and Robin Thomas. Three-coloring triangle-free planar graphs in linear time
• Amin Coja-Oghlan, Colin Cooper and Alan Frieze. An Efficient Sparse Regularity Concept
• Toniann Pitassi and Nathan Segerlind. Exponential Lower Bounds and Integrality Gaps for Lovasz-Schrijver Procedures
• Uriel Feige and Noga Alon. On the power of two, three and four probes
• Siu-Wing Cheng and Man-Kwun Chiu. Dimension detection via slivers
• Ioannis Caragiannis, Jason Covey, Michal Feldman, Christopher Homan, Christos Kaklamanis, Nikos Karanikolas, Ariel Procaccia and Jeffrey Rosenschein. On the Approximability of Dodgson and Young Elections
• David Eppstein and Elena Mumford. Self-overlapping Curves Revisited
• Jiri Matousek, Martin Tancer and Uli Wagner. Hardness of embedding simplicial complexes in R^d
• MohammadTaghi Hajiaghayi and Mohammad H. Bateni. The Assignment Problem in Content Distribution Networks: Unsplittable Hard-Capacitated Facility Location
• Sudipto Guha, Kamesh Munagala and Peng Shi. Approximation Algorithms for Restless Bandit Problems
• Vida Dujmovic, John Howat and Pat Morin. Biased Range Trees
• Zeev Nutov. An almost O(log k)-approximation for k-connected subgraphs
• David Eppstein, Michael Goodrich and Darren Strash. Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Crossings
• Moran Feldman, Guy Kortsarz and Zeev Nutov. Improved Approximating Algorithms for Directed Steiner Forest
• Haim Kaplan, Natan Rubin and Micha Sharir. Line Transversals of Convex Polyhedra in S^3
• Mikkel Thorup. String Hashing for Linear Probing
• Anthony Man-Cho So. Improved Approximation Bound for Quadratic Optimization Problems with Orthogonality Constraints
• Ken-ichi Kawarabayashi and Yusuke Kobayashi. Algorithms for Finding an Induced Cycle in Planar Graphs
• Stephan Thomasse. A quadratic kernel for feedback vertex set
• Martin Dietzfelbinger and Ulf Schellbach. On risks of using cuckoo hashing with simple universal hash classes
• Michael Molloy and Bruce Reed. Asymptotically optimal frugal colouring
• Omid Amini, Louis Esperet and Jan van den Heuvel. A Unified Approach to Distance-Two Colouring of Planar Graphs
• Nikhil Bansal and Ho-Leung Chan. Weighted flow time does not admit O(1)-competitive algorithms
• Paolo Ferragina, Igor Nitto and Rossano Venturini. On the bit-complexity of Lempel-Ziv compression
• Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld and Rocco Servedio. Testing Halfspaces
• Ke Yi and Qin Zhang. Multi-Dimensional Online Tracking
• Krishnendu Chatterjee, Luca de Alfaro and Thomas Henzinger. Termination Criteria for Solving Concurrent Safety and Reachability Games
• Philip Klein, Shay Mozes and Oren Weimann. Shortest Paths in Directed Planar Graphs with Negative Lengths: a linear-space O(n log^2 n)-time algorithm
• Ioannis Caragiannis. Efficient coordination mechanisms for unrelated machine scheduling
• Daniel Marx. Approximating fractional hypertree width
• Bodo Manthey and Heiko Roeglin. Improved Smoothed Analysis of the k-Means Method
• Christos Boutsidis, Michael Mahoney and Petros Drineas. An Improved Approximation Algorithm for the Column Subset Selection Problem
• Michael Drmota and Wojciech Szpankowski. (Un)Expected Behavior of Digital Search Tree Profile
• Nikhil Bansal, Zachary Friggstad, Rohit Khandekar and Mohammad Salavatipour. A logarithmic approximation for the unsplittable flow on line graphs
• Edith Cohen, Nick Duffield, Haim Kaplan, Carsten Lund and Mikkel Thorup. Variance-optimal sampling-based estimation of subset sums
• Sergio Cabello. Finding shortest contractible cycles in embedded graphs
• Khaled Elbassioni, Rajiv Raman, Saurabh Ray and Rene Sitters. On the approximability of the maximum feasible subsystem problem with 0/1-coefficients
• S. Charles Brubaker. Clustering on Noisy Mixtures
• Ashish Goel, Michael Kapralov and Sanjeev Khanna. Perfect matchings via uniform sampling in regular bipartite graphs
• David Karger and Debmalya Panigrahi. An tilde{O}(m) algorithm for constructing a cactus of an undirected graph
• Joel Tropp. Efficient Algorithms for Column Subset Selection
• Gabriel Nivasch. Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
• Raphael Yuster. Efficient algorithms on sets of permutations, dominance, and real-weighted APSP
• Gabor Tardos and Ehsan Amiri. High rate fingerprinting codes and the fi ngerprinting capacity
• Yury Person and Mathias Schacht. Almost all hypergraphs without Fano planes are bipartite
• Amr Elmasry. Pairing Heaps with O(loglog n}) decrease Cost
• Haim Kaplan and Uri Zwick. A simpler implementation and analysis of Chazelle's Soft Heaps
• Mikkel Thorup, Uri Zwick and Omid Madani. Discounted Deterministic Markov Decision Processes and Discounted All-Pairs Shortest Paths
• Alon Shalita and Uri Zwick. Efficient algorithms for the 2-gathering problem
• david cohen-steiner, Herbert Edelsbrunner, John Harer and Dmitriy Morozov. Persistent Homology for Kernels, Images, and Cokernels
• Fedor Fomin, Petr Golovach, Daniel Lokshtanov and Saket Saurabh. Clique-width: On the Price of Generality
• Parinya Chalermsook and Julia Chuzhoy. Maximum Independent Set of Rectangles
• Brendan Nagle, Annika Poerschke, Vojtech Rödl and Mathias Schacht. On Algorithmic Hypergraph Regularity
• Robi Krauthgamer, Seffi Naor and Roy Schwartz. Partitioning Graphs into Balanced Components
• Nikhil Bansal, Ho-Leung Chan and Kirk Pruhs. Speed Scaling with an Arbitrary Power Function
• Zdenek Dvorak, Daniel Kral and Robin Thomas. Coloring triangle-free graphs on surfaces
• Amitabh Basu, Pierre Bonami, gerard cornuejols and Francois Margot. On the Relative Strength of Split, Triangle and Quadrilateral Cuts (Extended Abstract)
• Raphael Clifford, Klim Efremenko, Ely Porat and Amir Rothschild. From coding theory to efficient pattern matching
• Ramesh Hariharan and Anand Bhalgat. Fast Edge Orientation for Unweighted Graphs
• Viswanath Nagarajan and Maxim Sviridenko. On the Maximum Quadratic Assignment Problem
• Bernard Chazelle. Natural Algorithms
• Timothy M. Chan. Comparison-Based, Time-Space Lower Bounds for Selection
• Peyman Afshani and Timothy M. Chan. Optimal Halfspace Range Reporting in Three Dimensions
• Justin Salez and Devavrat Shah. Optimality of Belief Propagation for Random Assignment Problem
• Ping Li. Compressed Counting
• Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane and Mihai Patrascu. The Geometry of Binary Search Trees
• Satoru Iwata and James Orlin. A Simple Combinatorial Algorithm for Submodular Function Minimization
• Prasad Raghavendra and David Steurer. Towards Computing the Grothendieck Constant
• Mordecai J. Golin, Xiaoming Xu and Jiajin Yu. A Generic Top-Down Dynamic-Programming Approach to Prefix-Free Coding
• Ken-ichi Kawarabayashi, Erik Demaine and Mohammad Taghi Haijaghayi. Additive Approximation Algorithms for List-Coloring Minor-Closed Class of Graphs
• Ken-ichi Kawarabayashi and Bruce Reed. A Nearly Linear Time Algorithm For The Half Integral Parity Disjoint Paths Packing Problem
• Michel Goemans, Nicholas J.A. Harvey, Satoru Iwata and Vahab Mirrokni. Approximating Submodular Functions Everywhere
• Baharak Rastegari, Anne Condon and Kevin Leyton-Brown. Stepwise Randomized Combinatorial Auctions Achieve Revenue Monotonicity
• Ilia Binder and Mark Braverman. The complexity of simulating Brownian Motion
• Prosenjit Bose, Eric Chen, Meng He, Anil Maheshwari and Pat Morin. Succinct Geometric Indexes Supporting Point Location Queries
• Djamal Belazzougui, Paolo Boldi, Rasmus Pagh and Sebastiano Vigna. Monotone Minimal Perfect Hashing: Searching a Sorted Table with O(1) Accesses
• Alexandr Andoni, Piotr Indyk, Robi Krauthgamer and Huy Nguyen. Approximate Nearest Neighbors for Affine Subspaces Queries
• Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jez, ?ukasz Je? and Grzegorz Stachowiak. Collecting Weighted Items from a Dynamic Queue
• Boaz Barak, Moritz Hardt and Satyen Kale. The Uniform Hardcore Lemma via Approximate Bregman Projections
• Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova and David Woodruff. Transitive-Closure Spanners
• Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant and Paul Valiant. On the Complexity of Nash Equilibria of Action-Graph Games
• Alexandr Andoni, Piotr Indyk and Robi Krauthgamer. Overcoming the L_1 Non-Embeddability Barrier: Algorithms for Product Metrics
• Parikshit Gopalan and Jaikumar Radhakrishnan. Finding repeats in a data-stream
• James Aspnes and Keren Censor. Approximate Shared-Memory Counting Despite a Strong Adversary
• Ittai Abraham, Yair Bartal and Ofer Neiman. On Low Dimensional Local Embeddings
• Michael Bender, Jeremy Fineman and Seth Gilbert. Online Topological Ordering
• William Johnson and Assaf Naor. The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite
• Klaus Jansen. Parameterized approximation scheme for the multiple knapsack problem
• Markus Chimani, Carsten Gutwenger, Petra Mutzel and Christian Wolf. Inserting a Vertex into a Planar Graph
• Spyros Angelopoulos and Pascal Schweitzer. Paging and List Update under Bijective Analysis
• Adrian Dumitrescu, Csaba Toth and G Xu. On stars and Steiner stars. II
• Benjamin Aminof, Orna Kupferman and Robby Lampert. Reasoning about Online Algorithms with Weighted Automata
• Amin Coja-Oghlan, Uriel Feige, Alan Frieze, Michael Krivelevich and Dan Vilenchik. On smoothed k-CNF formulas and the Walksat algorithm
• Elad Hazan and Robi Krauthgamer. How hard is it to approximate the best Nash equilibrium?
• Ashish Goel, Sanjeev Khanna and Brad Null. The Ratio Index for Budgeted Learning, with Applications
• Serge Gaspers and Gregory Sorkin. A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between
• Greg Aloupis, Jean Cardinal, Sebastien Collette, Stefan Langerman, David Orden and Pedro Ramos. Decomposition of Multiple Coverings into More Parts
• Edith Elkind and Dmitrii Pasechnik. Computing the nucleolus of weighted voting games
• Konstantinos Panagiotou and Angelika Steger. Maximum Biconnected Subgraphs of Random Planar Graphs
• Ken-ichi Kawarabayashi and Bojan Mohar. List-Color-Critical Graphs on a Fixed Surface
• Ariel Kulik, Hadas Shachnai and Tami Tamir. Maximizing Submodular Set Functions Subject to Multiple Linear Constraints
• Marcel R. Ackermann and Johannes Blömer. Coresets and Approximate Clustering for Bregman Divergences
• Benjamin Moseley and Chandra Chekuri. Online Scheduling to Minimize the Maximum Delay Factor
• Maria-Florina Balcan, Avrim Blum and Anupam Gupta. Approximate Clustering without the Approximation
• Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica and Kunal Talwar. Secretary Problems: Weights and Discounts
• Maria-Florina Balcan, Avrim Blum and Yishay Mansour. Improved Equilibria via Public Service Advertising
• Yusu Wang, Kevin Buchin and Maike Buchin. Exact Algorithm for Partial Curve Matching via the Frechet Distance
• Pankaj K Agarwal, R Sharathkumar and Hai Yu. Approximate Euclidean Shortest Path amid convex obstacles
• Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld and Elad Verbin. Sorting and Selection in Posets
• Sergi Elizalde and Peter Winkler. Sorting by Placement and Shift
• Ryan O'Donnell and Yi Wu. 3-Bit Dictator Testing: 1 vs. 5/8
• Siddharth Barman and Shuchi Chawla. Packing multiway cuts in graphs
• Frederic Chazal, Leonidas Guibas, Steve Oudot and Primoz Skraba. Analysis of Scalar Fields over Point Cloud Data
• Frederic Magniez, Ashwin Nayak, Peter Richter and Miklos Santha. On the hitting times of quantum versus random walks
• Elad Hazan and Satyen Kale. Better Algorithms for Benign Bandits
• Florin Constantin, Jon Feldman, S Muthukrishnan and Martin Pal. An Online Mechanism for Ad Slot Reservations with Cancellations
• Colin Cooper and Alan Frieze. The cover time of random geometric graphs
• Lorenz Minder and Alistair Sinclair. The extended k-tree algorithm
• Misha Belkin, jian sun and Yusu Wang. Constructing Laplace operators from Point Clouds
• Anirban Dasgupta, Arpita Ghosh, Hamid Nazerzadeh and Prabhakar Raghavan. Online story scheduling for web advertising
• Mohsen Bayati, Andrea Montanari and Amin Saberi. Generating Random Graphs with Large Girth
• Florian Diedrich and Klaus Jansen. Improved Approximation Algorithms for Scheduling with Fixed Jobs
• Aurore Amaudruz and Christina Fragouli. Combinatorial Algorithms for Wireless Information Flow
• Ran Duan and Seth Pettie. Fast Algorithms for (Max,Min)-Matrix Multiplication and Bottleneck Shortest Paths
• Mehmet Begen and Maurice Queyranne. Appointment Scheduling with Discrete Random Durations
• Navin Goyal, Luis Rademacher and Santosh Vempala. Expanders via Random Spanning Trees
• Aaron Williams. Loopless Generation of Multiset Permutations using a Constant Number of Variables by Prefix Shifts
• Ran Duan and Seth Pettie. Dual-Failure Distance and Connectivity Oracles
• david gamarnik and Dimitry Katz. Sequential cavity method for computing limits of the log-partition function for
• Alexander Golynski. Lower Bounds for Succinct Data Structures
• Umang Bhaskar, Lisa Fleischer, Darrell Hoy and Chien-Chung Huang. Equilibria of Collusive Flow Games are not Unique
• Sam Greenberg, Amanda Pascoe and Dana Randall. Sampling Biased Lattice Configurations using Exponential Metrics
• Benoît Hudson, Gary Miller, Todd Phillips and Don Sheehy. Size Complexity of Volume Meshes vs. Surface Meshes
• Yury Lifshits and Shengyu Zhang. Combinatorial Algorithms for Nearest Neighbors, Near-Duplicates and Small-World Design.

## SODA 2009 Accepted papers, with abstracts

### Jeff Edmonds and Kirk Pruhs. Scalably Scheduling Processes with Arbitrary Speedup Curves

Abstract: We give a scalable ($(1+\epsilon)$-speed $O(1)$-competitive) nonclairvoyant algorithm for scheduling jobs with sublinear nondecreasing speed-up curves on multiple processors with the objective of average response time.

### Zdenek Dvorak, Ken-ichi Kawarabayashi and Robin Thomas. Three-coloring triangle-free planar graphs in linear time

Abstract: Grötzsch's theorem states that every triangle-free planar graph is $3$-colorable, and several relatively simple proofs of this fact were provided by Thomassen and other authors. It is easy to convert these proofs into quadratic-time algorithms to find a $3$-coloring, but it is not clear how to find such a coloring in linear time (Kowalik used a nontrivial data structure to construct an $O(n \log n)$ algorithm). We design a linear-time algorithm to find a $3$-coloring of a given triangle-free planar graph. The algorithm avoids using any complex data structures, which makes it easy to implement. As a by-product we give another simple proof of Grötzsch's theorem.

### Amin Coja-Oghlan, Colin Cooper and Alan Frieze. An Efficient Sparse Regularity Concept

Abstract: Let $\A$ be a $0/1$ matrix of size $m\times n$, and let $p$ be the density of $\A$ (i.e., the number of ones divided by $m\cdot n$). We show that $\A$ can be approximated in the cut norm within $\eps\cdot mnp$ by a sum of cut matrices (of rank $1$), where the number of summands is independent of the size $m\cdot n$ of $\A$, provided that $\A$ satisfies a certain boundedness condition. This decomposition can be computed in polynomial time. This result extends the work of Frieze and Kannan~\cite{FK} to \emph{sparse} matrices. As an application, we obtain efficient $1-\eps$ approximation algorithms for bounded'' instances of MAX CSP problems.

### Toniann Pitassi and Nathan Segerlind. Exponential Lower Bounds and Integrality Gaps for Lovasz-Schrijver Procedures

Abstract: The matrix cuts of Lovasz and Shrijver are methods for tightening linear relaxations of zero-one programs by the addition of new linear inequalities. We address the question of how many new inequalities are necessary to approximate certain combinatorial problems and to solve certain instances of Boolean satisfiability. Our first result is a size/rank tradeoff for tree-like LS+ refutations, showing that any refutation that has small size also has small rank. This allows us to immediately derive exponential size lower bounds for tree-like LS+ derivations of many unsatisfiable systems of inequalities where prior to our work, only rank lower bounds were known. Unfortunately we show that this tradeoff does not hold more generally for derivations of arbitrary inequalities. We give a simple example showing that derivations can be very small but nonetheless require maximal rank. This rules out a generic argument for obtaining size-based integrality gaps from rank-based gaps. Our second contribution is to show that a modified argument can often be used to prove size-based gaps from rank-based gaps. We illustrate this method by proving size-based integrality gaps for several prominent problems, where again prior to our work only rank-based integrality gaps were known. Our third contribution is to prove new separation results between proof systems. Using our machinery for converting rank-based lower bounds and integrality gaps into size-based lower bounds, we show that tree-like LS+ cannot polynomially simulate tree-like Cutting Planes. We also show that tree-like LS+ cannot simulate Resolution, and in particular, low rank LS+ cannot simulate Resolution. We conclude by examining size/rank tradeoffs behond the LS systems. We show that for Sherali-Adams and Lassere systems, size/rank tradeoffs continue to hold, even in the general (non-tree) case.

### Uriel Feige and Noga Alon. On the power of two, three and four probes

Abstract: An adaptive $(n,m,s,t)$-scheme is a deterministic scheme for encoding a vector $X$ of $m$ bits with at most $n$ ones by a vector $Y$ of $s$ bits, so that any bit of $X$ can be determined by $t$ adaptive probes to $Y$. A non-adaptive $(n,m,s,t)$-scheme is defined analogously. The study of such schemes arises in the investigation of the static membership problem in the bitprobe model. Answering a question of Buhrman, Miltersen, Radhakrishnan and Venkatesh [SICOMP 2002] we present adaptive $(n,m,s,2)$ schemes with $s<m$ for all $n$ satisfying $4n^2+4n <m$ and adaptive $(n,m,s,2)$ schemes with $s=o(m)$ for all $n =o(\log m)$. We further show that there are adaptive $(n,m,s,3)$-schemes with $s=o(m)$ for all $n=o(m)$, settling a problem of Radhakrishnan, Raman and Rao [ESA 2001], and prove that there are non-adaptive $(n,m,s,4)$-schemes with $s=o(m)$ for all $n=o(m)$. Therefore, three adaptive probes or four non-adaptive probes already suffice to obtain a significant saving in space compared to the total length of the input vector. Lower bounds are discussed as well.

### Siu-Wing Cheng and Man-Kwun Chiu. Dimension detection via slivers

Abstract: We present a method to estimate the manifold dimension by analyzing the shape of simplices formed by point samples in some small neighborhoods. Approximate tangent spaces at these neighborhoods can also be reported. Let $P$ be a set of point samples drawn from a manifold $\mani \subset \real^d$ with dimension $m$ according to a Poisson distribution with parameter $\lambda$. Both $\mani$ and $\lambda$ are unknown to our algorithm. For sufficiently large $\lambda$, given any integer $k \geq 1$, our algorithm correctly outputs $m$ in $O(kdm^3|P|\log |P|)$ time with probability $1 - O\left(\lambda^{-k\beta}\right)$ for some constant $\beta \in (0,1)$. It holds with the same probability that the angular error of each approximate tangent space reported is $O(\eps)$, where $\eps$ is a value depending on $\mani$, $\lambda$ and $m$ and $\lim_{\lambda \rightarrow \infty} \eps = 0$. We experimented with a practical variant of our algorithm and demonstrated that it does not require very high sampling density and it is competitive with several previous methods.

### Ioannis Caragiannis, Jason Covey, Michal Feldman, Christopher Homan, Christos Kaklamanis, Nikos Karanikolas, Ariel Procaccia and Jeffrey Rosenschein. On the Approximability of Dodgson and Young Elections

Abstract: The voting rules proposed by Dodgson and Young are both designed to find the alternative closest to being a Condorcet winner, according to two different notions of proximity; the score of a given alternative is known to be hard to compute under both rules. In this paper, we put forward two algorithms for approximating the Dodgson score, an LP-based randomized rounding algorithm and a deterministic greedy algorithm, both of which yield an O(logm) approximation ratio, where m is the number of alternatives; we observe that this result is asymptotically optimal, and further prove that our greedy algorithm is optimal up to a factor of 2, unless problems in NP have quasi-polynomial time algorithms. Although the greedy algorithm is computationally superior, we argue that the randomized rounding algorithm has an advantage from a social choice point of view. Further, we demonstrate that computing any reasonable approximation of the ranking produced by Dodgson?s rule is NP-hard. This result provides a complexity-theoretic explanation of sharp discrepancies that have been observed in the Social Choice Theory literature when comparing Dodgson elections with simpler voting rules. Finally, we show that the problem of calculating the Young score is NP-hard to approximate by any factor. This leads to an inapproximability result for the Young ranking.

### David Eppstein and Elena Mumford. Self-overlapping Curves Revisited

Abstract: A surface embedded in space in such a way that each point has a neighborhood within which the surface is a terrain projects to an immersed surface in the plane, the boundary of which is a self-intersecting curve. Under what circumstances can we reverse these mappings algorithmically? Shor and van Wyk considered one such problem, determining whether a curve is the boundary of an immersed disk; they showed that the self-overlapping curves defined in this way can be recognized in polynomial time. We show that several related problems are more difficult: it is NP-complete to determine whether an immersed disk is the projection of a surface embedded in space, or whether a curve is the boundary of an immersed surface in the plane that is not constrained to be a disk. However, when a casing is supplied with a self-intersecting curve, describing which component of the curve lies above and which below at each crossing, we may determine in time linear in the number of crossings whether the cased curve forms the projected boundary of a surface in space. As a related result, we show that an immersed surface with a single boundary curve that crosses itself n times has at most 2^{n/2} combinatorially distinct spatial embeddings, and we discuss the existence of fixed-parameter tractable algorithms for related problems.

### Jiri Matousek, Martin Tancer and Uli Wagner. Hardness of embedding simplicial complexes in R^d

Abstract: Let EMBED(k,d) be the following algorithmic problem: Given a finite k-dimensional simplicial complex K, does there exist a (piecewise linear) embedding of K into R^d? Known results easily imply polynomiality of EMBED(k,2) (k=1,2; the case k=1, d=2 is graph planarity) and of EMBED(k,2k) for all k>2 (even if k is not considered fixed). We observe that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that EMBED(d,d) and EMBED(d-1,d) are undecidable for any d>4. Our main result is NP-hardness of EMBED(2,4) and, more generally, of EMBED(k,d) for all k and d with d>3 and d\geq k \geq (2d-2)/3. These dimensions fall outside the so-called metastable range of a theorem of Haefliger and Weber, which characterizes embeddability using the deleted product obstruction. Our reductions are based on examples, due to Segal, Spiez, Freedman, Krushkal, Teichner, and Skopenkov, showing that outside the metastable range the deleted product obstruction is not sufficient to characterize embeddability.

### MohammadTaghi Hajiaghayi and Mohammad H. Bateni. The Assignment Problem in Content Distribution Networks: Unsplittable Hard-Capacitated Facility Location

Abstract: In a Content Distribution Network (CDN), there are $m$ servers storing the data; each of them has a specific bandwidth. All the requests from a particular client should be assigned to one server, because of the routing protocols used. The goal is to minimize the total cost of these assignments --- which is proportional to the distance as well as the request size --- while the load on each server is kept below its bandwidth constraint. When each server also has a setup cost, this is an \emph{unsplittable hard-capacitated facility location problem}. As much attention as facility location problems have received, there has been no nontrivial approximation algorithm when we have hard capacities (i.e., there can only be one copy of each facility whose capacity cannot be violated) and demands are unsplittable (i.e., all the demand from a client has to be assigned to a single facility). We observe it is NP-hard to approximate the cost to within any bounded factor. Thus, we relax the capacities to a $1+\epsilon$ factor. For the case where capacities are almost uniform, we give a bicriteria $O(\log n, 1+\epsilon)$-approximation algorithm for general metrics and a $(1+\epsilon, 1+\epsilon)$-approximation algorithm for tree metrics. We can get the same guarantee for non-uniform capacities if we allow quasipolynomial running time. A bicriteria (\alpha, \beta)-approximation algorithm produces a solution of cost at most \alpha times the optimum, while violating the capacities by no more than a \beta factor. In our algorithm, some clients guess the facility they are assigned to, and facilities decide the size of clients they serve. A straight-forward approach results in exponential running time. Handling this in (quasi-)polynomial time is also of independent interest. When costs do not satisfy metricity, we show that a $1.5$ violation of capacities is necessary to obtain any approximation. It is worth noting that our results generalizes bin packing (zero cost matrix and facility costs equal to one), knapsack (single facility with all costs being zero), minimum makespan scheduling for related machines (all costs being zero) and facility location problems.

### Sudipto Guha, Kamesh Munagala and Peng Shi. Approximation Algorithms for Restless Bandit Problems

Abstract: In this paper, we consider the restless bandit problem, which is one of the most well-studied generalizations of the celebrated stochastic multi-armed bandit problem in decision theory. In its ultimate generality, the restless bandit problem is known to be PSPACE-Hard to approximate to any non-trivial factor, and little progress has been made on this problem despite its significance in modeling activity allocation under uncertainty. We make progress on this problem by showing that for an interesting and general subclass that we term Monotone bandits, a surprisingly simple and intuitive greedy policy yields a factor 2 approximation. Such greedy policies are termed index policies, and are popular due to their simplicity and their optimality for the stochastic multi-armed bandit problem. The Monotone bandit problem strictly generalizes the stochastic multi-armed bandit problem, and naturally models multi-project scheduling where the state of a project becomes increasingly uncertain when the project is not scheduled. As a consequence we are able to significantly improve previous results on special cases, as well as provide algorithms for generalizations. It is worth noting that the previous algorithm(s) do not apply to Monotone bandits and a new analysis was essential to this progess. The notion of Monotone bandits is similar to (but not quite the same as) the notion of a Partially Observable Markov Decision Process (POMDP). This and related restless bandit problems serve as models for wireless scheduling, unmanned aerial vehicle (UAV) routing, and machine replenishment, among others. We develop several novel techniques in the design and analysis of the index policy. Our algorithm proceeds by introducing a novel "balance" constraint to the dual of a well-known LP relaxation to the restless bandit problem. This is followed by a structural characterization of the optimal solution by using both the exact primal as well as dual complementary slackness conditions. This yields an interpretation of the dual variables as potential functions from which we derive the index policy and the associated analysis. In addition, our techniques are general are of independent interest in other stochastic optimization contexts, and we provide one such example.

### Vida Dujmovic, John Howat and Pat Morin. Biased Range Trees

Abstract: A data structure, called a \emph{biased range tree}, is presented that preprocesses a set S of n points in R^2 and a query distribution D for 2-sided orthogonal range counting queries. The expected query time for this data structure, when queries are drawn according to D, matches, to within a constant factor, that of the optimal comparison tree for S and D. The memory and preprocessing requirements of the data structure are O(n\log n).

### Zeev Nutov. An almost $O(\log k)$-approximation for $k$-connected subgraphs

Abstract: We give an $O(\log k \cdot \log \frac{n}{n-k})$-approximation algorithm for the $k$-Connected Subgraph problem, that seeks to find a directed/undirected $k$-connected spanning subgraph of minimum cost. Our ratio is $O(\log k)$, unless $k=n-o(n)$. Previously, the best known approximation guarantees for this problem were $O(\log^2 k)$ for directed/undirected graphs [Fakcharoenphol and Laekhanukit, STOC 2008], and $O(\log k)$ for undirected graphs with $k \leq \sqrt{n/2}$ [Cheriyan, Vempala, and Vetta, STOC 2002]. As in previous work, we consider the augmentation problem of increasing at minimum cost the connectivity of a given graph $J$ by $1$ (a $\rho$-approximation for it is used to derive an $O(\rho \cdot \log k)$-approximation for $k$-Connected Subgraph). Fakcharoenphol and Laekhanukit showed that this augmentation problem admits an $O(\log t)$-approximation algorithm, where $t$ is the number of minimal ''violated'' sets in $J$. However, we may have $t=\Theta(n)$, so this gives only an $O(\log n)$-approximation. We show that a modification of the primal-dual algorithm of Ravi and Williamson can be used to add an edge set of cost $\leq {\opt}$ to get $t \leq \frac{2n}{n-k}$. Combined with the algorithm of Fakcharoenphol and Laekhanukit, this gives the ratio $O(\log \frac{n}{n-k})$ for the augmentation problem, which is $O(1)$, unless $k=n-o(n)$.

### David Eppstein, Michael Goodrich and Darren Strash. Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Crossings

Abstract: We provide linear-time algorithms for geometric graphs with sublinearly many crossings. That is, we provide algorithms running in $O(n)$ time on connected geometric graphs having $n$ vertices and $k$ crossings, where $k$ is smaller than $n$ by an iterated logarithmic factor. Specific problems we study include Voronoi diagrams and single-source shortest paths. Our algorithms all run in linear time in the standard comparison-based computational model; hence, we make no assumptions about the distribution or bit complexities of edge weights, nor do we utilize unusual bit-level operations on memory words. Instead, our algorithms are based on a \emph{planarization} method that zeroes in'' on edge crossings, together with methods for extending planar separator decompositions to geometric graphs with sublinearly many crossings. Incidentally, our planarization algorithm also solves an open computational geometry problem of Chazelle for triangulating a self-intersecting polygonal chain having $n$ segments and $k$ crossings in linear time, for the case when $k$ is sublinear in $n$ by an iterated logarithmic factor.

### Moran Feldman, Guy Kortsarz and Zeev Nutov. Improved Approximating Algorithms for Directed Steiner Forest

Abstract: We consider the $k$-Directed Steiner Forest ($k$-DSF) problem: given a directed graph $G=(V,E)$ with edge costs, a collection $D \subseteq V \times V$ of ordered node pairs, and an integer $k \leq |D|$, find a minimum cost subgraph $H$ of $G$ that contains an $st$-path for (at least) $k$ pairs $(s,t) \in D$. When $k=|D|$, we get the Directed Steiner Forest (DSF) problem. The best known approximation ratios for these problems are: $\tilde{O}(k^{2/3})$ for $k$-DSF by Charikar et~al. \cite{CCC}, and $O(k^{1/2 + \ee})$ for DSF by Chekuri et~al. \cite{CEGS}. We improve these approximation ratios as follows.

For DSF we give an $O(n^\ee \cdot \min\{n^{4/5},m^{2/3}\})$-approximation scheme using a novel LP-relaxation that seeks to connect pairs with ''cheap'' paths. This is the first sub-linear (in terms of $n=|V|$) approximation ratio for the problem; all previous algorithm had ratio $\Omega(n^{1+\ee})$.

For $k$-DSF we give a simple greedy $O(k^{1/2 + \ee})$-approximation algorithm. This improves the best known ratio $\tilde{O}(k^{2/3})$ by Charikar et~al. \cite{CCC}, and (almost) matches in terms of $k$ the best ratio known for the undirected variant \cite{GHNR}. Even when used for the particular case of DSF, our algorithm favorably compares to the one of \cite{CEGS}, which repeatedly solves linear programs and uses complex space and time consuming transformations. Our algorithm is much simpler and faster, since it essentially reduces $k$-DSF to a variant of the Directed Steiner Tree problem. The simplification is due to a new notion of junction star-tree'' -- a union of an in-star and an out-branching having the same root, which is of independent interest.

### Haim Kaplan, Natan Rubin and Micha Sharir. Line Transversals of Convex Polyhedra in \reals^3

Abstract: We establish a bound of $O(n^2k^{1+\eps})$, for any $\eps>0$, on the combinatorial complexity of the set $\T$ of line transversals of a collection $\P$ of $k$ convex polyhedra in $\reals^3$ with a total of $n$ facets, and present a randomized algorithm which computes the boundary of $\T$ in comparable expected time. Thus, when $k\ll n$, the new bounds on the complexity (and construction cost) of $\T$ improve upon the previously best known bounds, which are nearly cubic in $n$.

To obtain the above result, we study the set $\TL$ of line transversals which emanate from a fixed line $\ell_0$, establish an almost tight bound of $O(nk^{1+\eps})$ on the complexity of $\TL$, and provide a randomized algorithm which computes $\TL$ in comparable expected time. Slightly improved combinatorial bounds for the complexity of $\TL$, and comparable improvements in the cost of constructing this set, are established for two special cases, both assuming that the polyhedra of $\P$ are pairwise disjoint: the case where $\ell_0$ is disjoint from the polyhedra of $\P$, and the case where the polyhedra of $\P$ are unbounded in a direction parallel to $\ell_0$.

### Mikkel Thorup. String Hashing for Linear Probing

Abstract: Hash tables for strings and other complex objects are central to the analysis of data, and they are directly built into high level programming languages such as python, and perl.

Linear probing is one of the most popular implementations of hash tables in practice. We store all keys in a single array. A new key is hashed. If a different key is in the position hashed to, we scan next positions sequentially until either the key is found, or we hit an empty spot concluding that the key is new. This is compact and it is fast because we typically get all positions considered in single cache-line, and that also holds for deletions. However, linear probing has been known to be a bit unreliable in practice. Analyzing the performance of linear probing with universal hash functions was raised as an open problem by Carter and Wegman in 1979.

At STOC'07, Pagh et al.~studied the expected number of linear probes with worst-case data sets. They showed that with the standard implementation of 2-universal hashing, the expected number of probes could be $\Omega(\log n)$. A worst-case is one or two intervals --- something that could very well appear in practice, possibly explaining the experienced unreliability. On the positive side, they showed that with 5-universal hashing, the expected number of probes is constant.

Unfortunately, we do not have 5-universal hashing for, say, variable length strings. When we want to do such complicated hashing on a complicated domain, the generic standard solution is that we first do collision free hashing (w.h.p.) into a simpler intermediate domain, and second do the complicted hash function on this intermediate domain.

Our contribution is that for an expected constant number of linear probes, it is suffices that each key has $O(1)$ expected collisions with the first hash function, as long as the second hash function is 5-universal. This means that the intermediate domain can be $n$ times smaller. Such a smaller intermediate domain typically means that the both the first and the second hash function run at least twice as fast. This doubling of hashing speed follows not just for variable length strings, but for most domains bigger than 32-bit integers, e.g., fixed length strings and even 64-bit integers.

### Anthony Man-Cho So. Improved Approximation Bound for Quadratic Optimization Problems with Orthogonality Constraints

Abstract: In this paper we consider approximation algorithms for a class of quadratic optimization problems that contain orthogonality constraints, i.e. constraints of the form $X^TX=I$, where $X\in\R^{m\times n}$ is the optimization variable. This class of problems, which we denote by (QP-OC), is quite general and captures several well-studied problems in the literature as special cases. In a recent work, Nemirovski [Math. Prog. 109:283--317, 2007] gave the first non-trivial approximation algorithm for (QP-OC). His algorithm is based on semidefinite programming and has an approximation guarantee of $O\left((m+n)^{1/3}\right)$. We improve upon this result by providing the first logarithmic approximation guarantee for (QP-OC). Specifically, we show that (QP-OC) can be approximated to within a factor of $O\left(\ln\left(\max\{m,n\}\right)\right)$. The main technical tool used in the analysis is a concentration inequality for the spectral norm of a Rademacher sum of matrices, which we develop using tools from functional analysis. As a by-product, we resolve in the affirmative a conjecture of Nemirovski concerning the typical spectral norm of a sum of certain random matrices. The aforementioned concentration inequality also has ramifications in the design of so-called safe tractable approximations of chance constrained optimization problems. In particular, we use it to simplify and improve a recent result of Ben-Tal and Nemirovski [Manuscript, 2007] concerning certain chance constrained linear matrix inequality systems.

### Ken-ichi Kawarabayashi and Yusuke KOBAYASHI. Algorithms for Finding an Induced Cycle in Planar Graphs

Abstract: In this paper, we consider the problem for finding an induced cycle passing through $k$ given vertices, which we call the induced cycle problem. The significance of finding induced cycles stems from the fact that precise characterization of perfect graphs would require structures of graphs without an odd induced cycle, and its complement. There has been huge progress in the recent years, especially, the Strong Perfect Graph Conjecture was solved by Chudnovsky, Robertson, Seymour and Thomas. Concerning recognition of perfect graphs, there had been a long-standing open problem for detecting an odd hole and its complement, and finally this was solved by Chudnovsky, Cornu\'ejols, Liu, Seymour and Vuskovic.

Unfortunately, the problem of finding an induced cycle passing through two given vertices is NP-complete in a general graph. However, if the input graph is constrained to be planar and $k$ is fixed, then the induced cycle problem can be solved in polynomial time.

In particular, an $O(n^2)$ time algorithm is given for the case $k=2$ by McDiarmid, Reed, Schrijver and Shepherd, where $n$ is the number of vertices of the input graph.

Our main results in this paper are to improve their result in the following sense.

(1) The number of vertices $k$ is allowed to be non-trivially super constant number, up to $k = o((\frac{\log n}{\log \log n})^{\frac{2}{3}})$. More precisely, when $k = o((\frac{\log n}{\log \log n})^{\frac{2}{3}})$, then the ICP in planar graphs can be solved in $O (n^{2 + \varepsilon})$ time for any $\varepsilon > 0$. (2) The time complexity is linear if the given graph is planar and $k$ is fixed. (3) The above results are extended to graphs embedded in a fixed surface.

We note that the linear time algorithm (the second result) is independent from the first result. Let us observe that if $k$ is as a part of the input, then the problem is still NP-complete. So we need to impose some condition on $k$.

Our proofs of the above results basically follow the same line of the proof of the disjoint paths problem by Robertson and Seymour, together with Reed, Robertson, Schrijver, Seymour's result, which improves the time complexity of the algorithm of the disjoint paths by Robertson and Seymour ($O(n^3)$ time algorithm) to linear time when an input graph is planar. However, our cycle must be induced, so some of arguments must be extended to induced paths, which needs much more involved arguments. In addition, we are also interested in the case when $k$ is as a part of the input. Therefore, we need to sharpen the function of $k$. This needs nontrivial amount of work, since both Robertson-Seymour's proof and Reed, Robertson, Schrijver, Seymour's proof do not care much about sharpening the hidden constant of $k$. These proofs just guarantee the existence of the function of $k$, therefore, it is highly expensive, and nonpractical. Our proofs, though, give fairly small function of $k$. Therefore, we believe that this result may be viewed as a much more practical result. Price to pay is to need to analyze the structure of planar graphs and graphs embedded in a fixed surface more closely.

### Stephan Thomasse. A quadratic kernel for feedback vertex set

Abstract: We prove that given an undirected graph $G$ on $n$ vertices and an integer $k$, one can compute in polynomial time in $n$ a graph $G'$ with at most $5k^2+k$ vertices and an integer $k'$ such that $G$ has a feedback vertex set of size at most $k$ iff $G'$ has a feedback vertex set of size at most $k'$. This result improves a previous $O(k^{11})$ kernel of Burrage et al.~\cite{MF}, and a more recent cubic kernel of Bodlaender~\cite{HL2}. This problem was communicated by Fellows in~\cite{MF}.

### Martin Dietzfelbinger and Ulf Schellbach. On risks of using cuckoo hashing with simple universal hash classes

Abstract: Background:

Cuckoo hashing, introduced by Pagh and Rodler (Cuckoo hashing'', ESA 2001 and J. Algorithms 51, 2004), is a strategy for maintaining hash tables for keys from $U$, $|U|=N$, so that lookups take constant time in the worst case. The data structure consists of two tables of size $m$ each, and it uses two hash functions $h_1, h_2\colon U\to [m]$. For the scheme to work it is necessary and sufficient that $m \ge (1+\eps)n$ for an arbitrary constant $\eps>0$, where $n$ is the number of keys stored.

Pagh and Rodler's analysis establishes expected amortized constant time for insertion; for the analysis to work it is required that the hash functions are $c \log n$-wise independent. In experiments, cuckoo hashing works very well with weaker hash function classes. However, Pagh and Rodler report on experimental results that indicate that cuckoo hashing might not work well in combination with the multiplicative class'' (which consists of functions $h_a: [2^k]\to[2^l]$ of the form $h_a(x)=((a x)\bmod 2^k)\div 2^{k-l}$, for $0<a<2^k$ odd, and is close to 2-universal''). They state that they do not have an explanation for this phenomenon.

In 2008, Mitzenmacher and Vadhan (Why simple hash functions work: exploiting the entropy in a data stream'', SODA 2008) proved that if a 2-universal hash class $H$ is used and the key set exhibits a certain degree of randomness, and further technical conditions are fulfilled, then the combination of the key set and a hash function chosen at random from $H$ will behave very close to full randomness, in a technical sense.

Our results:

1) We show that if cuckoo hashing with $2^l=m=2n$ is employed (this table size is way above the threshold sufficient for the standard analysis), then all function pairs from the multiplicative hash class will work badly with high probability for fully random key sets of size $n$, if $n/N > N^{1-\gamma}$ for some constant $\gamma>0$. On the one hand, this explains the experimental results obtained by Pagh and Rodler and justifies a warning against using this simple class, on the other hand, it shows that one of the further technical conditions'' of the Mitzenmacher/Vadhan result, namely the requirement that key sets must be relatively sparse in $U$, is really necessary for their result to be true.

2) We show that cuckoo hashing with a standard almost 2-wise independent class of hash functions (functions of the form $h_{a,b}=((ax+b)\bmod p)\bmod m$, $p \ge |U|$ a prime number) exhibits a similar behavior as the class in 1), again in the case where the key set is relatively dense in $U$. This is true even in the case when the two hash functions use different prime moduli.

Further related work:

Cohen and Kane (Bounds on the independence required for cuckoo hashing'', unpublished manuscript, 2005, http://web.mit.edu/dankane/www/Independence%20Bounds.pdf) construct $2$-, $3$-, and even $5$-wise independent hash families, for which cuckoo hashing has high failure probability. However, these families are quite contrived and far from being common.

### Michael Molloy and Bruce Reed. Asymptotically optimal frugal colouring

Abstract: We prove that every graph with maximum degree D can be properly (D+1)-coloured so that no colour appears more than O(log D/log log D) times in the neighbourhood of any vertex. This is best possible up to the constant factor in the O(-) term. We also provide an efficient algorithm to produce such a colouring.

### Omid Amini, Louis Esperet and Jan van den Heuvel. A Unified Approach to Distance-Two Colouring of Planar Graphs

Abstract: In this paper we introduce the notion of $(A,B)$-colouring of a graph: For given vertex sets $A,B$, this is a colouring of the vertices in $B$ so that both adjacent vertices and vertices with a common neighbour in $A$ receive different colours. This concept generalises the notion of colouring the square of graphs and of cyclic colouring of plane graphs. We prove a general result which implies asymptotic versions of Wegner's and Borodin's Conjecture on these two colourings. Using a recent approach of Havet \emph{et al.}, we reduce the problem to edge-colouring of multigraphs and then use Kahn's result that the list chromatic index is close from the fractional chromatic index.

Our results are based on a strong structural lemma for planar graphs which also implies that the size of a clique in the square of a planar graph of maximum degree~$\Delta$ is at most $\frac32\,\Delta$ plus a constant.

### Nikhil Bansal and Ho-Leung Chan. Weighted flow time does not admit O(1)-competitive algorithms

Abstract: We consider the classic online scheduling problem of minimizing the total weighted flow time on a single machine with preemptions. Here, each job $j$ has an arbitrary arrival time $r_j$, weight $w_j$ and size $p_j$, and given a schedule its flow time is defined as the duration of time since its arrival until it completes its service requirement. The first non-trivial algorithms with poly-logarithmic competitive ratio for this problem were obtained relatively recently, and it was widely believed that the problem admits a constant factor competitive algorithm. In this paper, we show an $\omega(1)$ lower bound on the competitive ratio of any deterministic online algorithm. Our result is based on a novel gap amplification technique for online algorithms. Starting with a trivial lower bound of 1, we give a procedure to improve the lower bound sequentially, while ensuring at each step that the size of the instance increases relatively modestly.

### Paolo Ferragina, Igor Nitto and Rossano Venturini. On the bit-complexity of Lempel-Ziv compression

Abstract: One of the most famous and investigated lossless data-compression schemes is the one introduced by Lempel and Ziv about 30 years ago. This compression scheme is known as dictionary-based compressor'' and consists of squeezing an input string by replacing some of its substrings with (shorter) codewords which are actually pointers to a dictionary of phrases built as the string is processed. Surprisingly enough, although many fundamental results are nowadays known about the speed and effectiveness of this compression process, we are not aware of any parsing scheme that achieves optimality when the LZ-dictionary is in use under any constraint on the codewords other than being of equal length'' [N. Rajpoot and C. Sahinalp. Handbook of Lossless Data Compression, chapter Dictionary-based data compression. Academic Press, 2002. pag. 159]. Here optimality means to achieve the minimum number of bits in compressing each individual input string, without any assumption on its generating source.

In this paper we investigate three issues pertaining to the bit-complexity of LZ-based compressors, and we design algorithms which achieve bit-optimality in the compressed output size by taking efficient/optimal time and optimal space. These theoretical results will be sustained by some experiments that will compare our novel LZ-based compressors against the most popular compression tools (like Gzip, Bzip) and state-of-the-art compressors (like the Compression Booster [Ferragina-Giancarlo-Manzini-Sciortino, J.ACM 52(4), 2005]).

### Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld and Rocco Servedio. Testing Halfspaces

Abstract: This paper addresses the problem of testing whether a Boolean-valued function $f$ is a halfspace, i.e. a function of the form $f(x)=\sgn(w \cdot x - \theta).$ We consider halfspaces over the continuous domain $\R^n$ (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube $\{-1,1\}^n$ (endowed with the uniform distribution). In both cases we give an algorithm that distinguishes halfspaces from functions that are $\epsilon$-far from any halfspace using only $\poly(\frac{1}{\epsilon})$ queries, independent of the dimension $n$.

Two simple structural results about halfspaces are at the heart of our approach for the Gaussian distribution: the first gives an exact relationship between the expected value of a halfspace $f$ and the sum of the squares of $f$'s degree-1 Hermite coefficients, and the second shows that any function that approximately satisfies this relationship is close to a halfspace. We prove analogous results for the Boolean cube $\{-1,1\}^n$ (with Fourier coefficients in place of Hermite coefficients) for balanced halfspaces in which all degree-1 Fourier coefficients are small. Dealing with general halfspaces over $\bits^n$ poses significant additional complications and requires other ingredients. These include cross-consistency'' versions of the results mentioned above for pairs of halfspaces with the same weights but different thresholds; new structural results relating the largest degree-1 Fourier coefficient and the largest weight in unbalanced halfspaces; and algorithmic techniques from recent work on testing juntas \cite{FKR+:02}.

### Ke Yi and Qin Zhang. Multi-Dimensional Online Tracking

Abstract: We propose and study a new class of online problems, which we call {\em online tracking}. Suppose an {\em observer}, say Alice, observes a multi-valued function $f : \mathbb{Z}^+ \rightarrow \mathbb{Z}^d$ over time in an online fashion, i.e., she only sees $f(t)$ for $t\le\tnow$ where $\tnow$ is the current time. She would like to keep a {\em tracker}, say Bob, informed of the current value of $f$ at all times. Under this setting, Alice could send new values of $f$ to Bob from time to time, so that the current value of $f$ is always within a distance of $\Delta$ to the last value received by Bob. We give competitive online algorithms whose communication costs are compared with the optimal offline algorithm that knows the entire $f$ in advance. We also consider variations of the problem where Alice is allowed to send predictions'' to Bob, to further reduce communication for well-behaved functions. These online tracking problems have a variety of application ranging from sensor monitoring, location-based services, to publish/subscribe systems.

### Krishnendu Chatterjee, Luca de Alfaro and Thomas Henzinger. Termination Criteria for Solving Concurrent Safety and Reachability Games

Abstract: We consider concurrent games played on graphs. At every round of a game, each player simultaneously and independently selects a move; the moves jointly determine the transition to a successor state. Two basic objectives are the safety objective to stay forever in a given set of states, and its dual, the reachability objective to reach a given set of states. We present in this paper a strategy improvement algorithm for computing the value of a concurrent safety game, that is, the maximal probability with which player 1 can enforce the safety objective. The algorithm yields a sequence of player-1 strategies which ensure probabilities of winning that converge monotonically to the value of the safety game.

Our result is significant because the strategy improvement algorithm provides, for the first time, a way to approximate the value of a concurrent safety game from below. Since a value iteration algorithm, or a strategy improvement algorithm for reachability games, can be used to approximate the same value from above, the combination of both algorithms yields a method for computing a converging sequence of upper and lower bounds for the values of concurrent reachability and safety games. Previous methods could approximate the values of these games only from one direction, and as no rates of convergence are known, they did not provide a practical way to solve these games.

### Philip Klein, Shay Mozes and Oren Weimann. Shortest Paths in Directed Planar Graphs with Negative Lengths: a linear-space O(n log^2 n)-time algorithm

Abstract: We give an $O(n \log^2 n)$-time, linear-space algorithm that, given a directed planar graph with positive and negative arc-lengths and no negative-length cycles, and given a node s, finds the distances from s to all nodes. The best previously known algorithm requires $O(n \log^3 n)$ time and $O(n \log n)$ space.

### Ioannis Caragiannis. Efficient coordination mechanisms for unrelated machine scheduling

Abstract: We present three new coordination mechanisms for scheduling $n$ selfish jobs on $m$ unrelated machines. A coordination mechanisms aims to mitigate the impact of selfishness of jobs on the efficiency of schedules by defining a local scheduling policy on each machine. The scheduling policies induce a game among the jobs and each job prefers to be scheduled on a machine so that its completion time is minimum given the assignments of the other jobs. We consider the maximum completion time among all jobs as the measure of the efficiency of schedules. The approximation ratio of a coordination mechanism quantifies the efficiency of pure Nash equilibria (price of anarchy) of the induced game.

Our mechanisms are deterministic, local, and preemptive in the sense that the scheduling policy does not necessarily process the jobs in an uninterrupted way and may introduce some idle time. Our first coordination mechanism has approximation ratio $O(\log m)$ and always guarantees that the induced game has pure Nash equilibria to which the system converges in at most $n$ rounds. This result improves a recent bound of $O(\log^2 m)$ due to Azar, Jain, and Mirrokni and, similarly to their mechanism, our mechanism uses a global ordering of the jobs according to their distinct IDs. Next we study the intriguing scenario where jobs are anonymous, i.e., they have no IDs. In this case, coordination mechanisms can only distinguish between jobs that have different load characteristics. Our second mechanism handles anonymous jobs and has approximation ratio $O\left(\frac{\log m}{\log \log m}\right)$ although the game induced is not a potential game and, hence, the existence of pure Nash equilibria is not guaranteed by potential function arguments. However, it provides evidence that the known lower bounds for non-preemptive coordination mechanisms could be beaten using preemptive scheduling policies. Our third coordination mechanism also handles anonymous jobs and has a nice cost-revealing'' potential function. Besides in proving the existence of equilibria, we use this potential function in order to upper-bound the price of stability of the induced game by $O(\log m)$, the price of anarchy by $O(\log^2m)$, and the convergence time to $O(\log^2m)$-approximate assignments by a polynomial number of best-response moves. Our third coordination mechanism is the first that handles anonymous jobs and simultaneously guarantees that the induced game is a potential game and has bounded price of anarchy.

### Daniel Marx. Approximating fractional hypertree width

Abstract: Fractional hypertree width is a hypergraph measure similar to tree width and hypertree width. Its algorithmic importance comes from the fact that, as shown in previous work \cite{grohe-marx}, constraint satisfaction problems (CSP) and various problems in database theory are polynomial-time solvable if the input contains a bounded-width fractional hypertree decomposition of the hypergraph of the constraints. In this paper, we show that for every $w\ge 0$, there is a polynomial-time algorithm that, given a hypergraph $H$ with fractional hypertree width at most $w$, computes a fractional hypertree decomposition of width $O(w^3)$ for $H$. This means that polynomial-time algorithms relying on bounded-width fractional hypertree decompositions no longer need to be given a decomposition explicitly in the input, since an appropriate decomposition can be computed in polynomial time. Therefore, if ${\mathcal H}$ is a class of hypergraphs with bounded fractional hypertree width, then constraint satisfaction restricted to instances whose structure is in ${\mathcal H}$ is polynomial-time solvable. This makes bounded fractional hypertree width the most general known hypergraph property that makes CSP polynomial-time solvable.

### Bodo Manthey and Heiko Roeglin. Improved Smoothed Analysis of the k-Means Method

Abstract: The k-means method is a widely used clustering algorithm. One of its distinguished features is its speed in practice. Its worst-case running-time, however, is exponential, leaving a gap between practical and theoretical performance. Arthur and Vassilvitskii (FOCS 2006) aimed at closing this gap, and they proved a bound of $poly(n^k, 1/\sigma)$ on the smoothed running-time of the k-means method, where n is the number of data points and \sigma is the standard deviation of the Gaussian perturbation. This bound, though better than the worst-case bound, is still much larger than the running-time observed in practice.

We improve the smoothed analysis of the k-means method by showing two upper bounds on the expected running-time of k-means. First, we prove that the expected running-time is bounded by a polynomial in $n^{\sqrt k}$ and $1/\sigma$. Second, we prove an upper bound of $k^{kd} \poly(n, 1/\sigma)$, where d is the dimension of the data space. The polynomial is independent of k and d, and we obtain a polynomial bound for the expected running-time for $k, d \in O(\sqrt{\log n/\log \log n})$.

Finally, we show that k-means runs in smoothed polynomial time for one-dimensional instances.

### Christos Boutsidis, Michael Mahoney and Petros Drineas. An Improved Approximation Algorithm for the Column Subset Selection Problem

Abstract: We consider the problem of selecting the best'' subset of \emph{exactly $k$ columns} from an $m \times n$ matrix $A$. In particular, we present and analyze a novel two-stage algorithm that runs in $O(\min\{mn^2,m^2n\})$ time and returns as output an $m \times k$ matrix $C$ consisting of exactly $k$ columns of $A$. In the first stage (the \textit{randomized} stage), the algorithm randomly selects $O(k \log k)$ columns according to a judiciously-chosen probability distribution that depends on information in the top-$k$ right singular subspace of $A$. In the second stage (the \textit{deterministic} stage), the algorithm applies a deterministic column-selection procedure to select and return exactly $k$ columns from the set of columns selected in the first stage. Let $C$ be the $m \times k$ matrix containing those $k$ columns, let $P_C$ denote the projection matrix onto the span of those columns, and let $A_k$ denote the best'' rank-$k$ approximation to the matrix $A$ as computed with the singular value decomposition. Then, we prove that $$\TNorm{A - P_CA} \leq O\left(k^{\frac 3 4}\log^{\frac 1 2}(k)\left(n-k\right)^{\frac 1 4}\right)\TNorm{A-A_k},$$ with probability at least $0.7$. This spectral norm bound improves upon the best previously-existing result (of Gu and Eisenstat~\cite{GE96}) for the spectral norm version of this Column Subset Selection Problem. We also prove that $$\FNorm{A - P_CA} \leq O\left(k \sqrt{\log k}\right) \FNorm{A-A_k},$$ with the same probability. This Frobenius norm bound is only a factor of $\sqrt{k \log k}$ worse than the best previously existing existential result and is roughly $O(\sqrt{k!})$ better than the best previous algorithmic result (both of Deshpande et al.~\cite{DRVW06}) for the Frobenius norm version of this Column Subset Selection Problem.

### Michael Drmota and Wojciech Szpankowski. (Un)Expected Behavior of Digital Search Tree Profile

Abstract: A digital search tree (DST) -- one of the most fundamental data structure on words -- is a digital tree in which keys (strings, words) are stored directly in (internal) nodes. Such trees find myriad of applications from the popular Lemepl-Ziv'78 data compression scheme to distributed hash tables. The profile of a DST measures the number of nodes at the same distance from the root; it is a function of the number of stored strings and the distance from the root. Most parameters of DST (e.g., height, fill-up, shortest path) can be expressed in terms of the profile. However, from the inception of DST analysis of the profile has been elusive and it has become a prominent open problem in the area of analysis of algorithms. We make here the first, but decisive step, towards solving this problem. We present a precise analysis of the average profile when stored strings are generated by a biased memoryless source. The main technical difficulty of analyzing the profile lies in solving a sophisticated recurrence equation. We present such a solution for the Poissonized version of the problem (i.e., when the number of stored strings is generated by a Poisson distribution) in the Mellin transform domain. To accomplish it, we introduce a novel functional operator that allows us to express the solution in an explicit form, and then using analytic algorithmics tools we extract asymptotic behavior of the profile as a function of the number of stored strings and the distance from the root. This analysis is surprisingly demanding but once it is carried out it reveals unusually intriguing and interesting behavior. The average profile undergoes several phase transitions when moving from the root to the longest path. It first resembles a full tree until it abruptly starts growing polynomially. Furthermore, the expected profile is oscillating in a range where profile grows polynomially. Such a behavior is quite unexpected for most shape parameters of random trees, except recently analyzed profiles of tries which are another incarnations of digital trees. Our results are derived by methods of analytic algorithmics such as generating functions, Mellin transform, Poissonization and de-Poissonization, the saddle-point method, singularity analysis and uniform asymptotic analysis.

### Nikhil Bansal, Zachary Friggstad, Rohit Khandekar and Mohammad Salavatipour. A logarithmic approximation for the unsplittable flow on line graphs

Abstract: We consider the unsplittable flow problem on a line. In this problem, we are given a set of $n$ tasks, each specified by a start time $s_i$, and end time $t_i$, a demand $d_i>0$, and a profit $p_i>0$. A task, if accepted, requires $d_i$ units of bandwidth'' from time $s_i$ to $t_i$ and accrues a profit of $p_i$. For every time $t$, we are also specified the available bandwidth $c_t$, and the goal is to find a subset of tasks with maximum profit subject to the bandwidth constraints.

We present the first polynomial-time $O(\log n)$-approximation algorithm for this problem. This significantly advances the state-of-the-art, as no polynomial-time $o(n)$-approximation was known previously. Previous results for this problem were known only in more restrictive settings. In particular, either if instance satisfies the so-called no-bottleneck'' assumption: $\max_i d_i \leq \min_t c_t$, or else if the ratio of both the maximum to the minimum demands and the maximum to minimum capacities are polynomially (or quasi-polynomially) bounded in $n$. Our result, on the other hand, does not require any of these assumptions.

Our algorithm is based on a combination of dynamic programming and rounding a natural linear programming relaxation for the problem. While there is an $\Omega(n)$ integrality gap known for this LP relaxation, our key idea is to exploit certain structural properties of the problem to show that instances that are bad for the LP can in fact be handled using dynamic programming.

### Edith Cohen, Nick Duffield, Haim Kaplan, Carsten Lund and Mikkel Thorup. Variance-optimal sampling-based estimation of subset sums

Abstract: From a high volume stream of weighted items, we want to maintain a generic sample of a certain limited size k that we can later use to estimate the total weight of arbitrary subsets. This is the classic context of on-line reservoir sampling, thinking of the generic sample as a reservoir. We present an efficient reservoir sampling scheme, VarOpt_k, that dominates all previous schemes in terms of estimation quality.

VarOpt_k provides variance optimal unbiased estimation of subset sums. More precisely, if we have seen n items of the stream, then for any subset size m, our scheme based on k samples minimizes the average variance over all subsets of size m. In fact, it is the first online scheme with this property and the optimality is against any off-line sampling scheme tailored for the concrete set of items seen: no off-line scheme based on k samples can perform better than our on-line scheme when it comes to average variance over any subset size. In addition to optimal average variance, our scheme provides tighter worst-case bounds on the variance of particular subsets than previously possible, even by an offline scheme. It is efficient, handling each new item of the stream in O(log k) time, which is optimal even on the word RAM. Finally, it is particularly well suited for combination of samples from different streams in a distributed setting.

### Sergio Cabello. Finding shortest contractible cycles in embedded graphs

Abstract: We give a polynomial-time algorithm to find a shortest contractible cycle (i.e. a closed walk without repeated vertices) in a graph embedded in a surface. This answers a question posed by Mohar and Thomassen. In contrast, we show that finding a shortest contractible cycle through a given vertex is NP-hard. We also show that finding a shortest separating cycle in an embedded graph is NP-hard.

### Khaled Elbassioni, Rajiv Raman, Saurabh Ray and Rene Sitters. On the approximability of the maximum feasible subsystem problem with 0/1-coefficients

Abstract: Given a system of inequalities $\ell_i\leq a_i^Tx\le u_i$, where $a_i\in\{0,1\}^n$, and $\ell_i,u_i\in \RR_+$, for $i=1,\ldots, m$, we consider the problem of finding the largest subsystem for which there exists a feasible solution $x\geq 0$. We give several approximability and inapproximability results, parameterized by the value of $L=\max\{\ell_1,\ldots,\ell_m\}$. In particular, we show that, under reasonable complexity assumptions, the problem cannot be approximated within a factor of $O(\log ^{\mu} n)$, for some positive $\mu$, even when $\ell_i=u_i=1$ for all $i$, and within a factor of $O(n^{1/3-\epsilon})$, for an arbitrarily small $\epsilon>0$, if $L$ is arbitrarily large. On the way, we also obtain an $\Omega(n^{1/3-\epsilon})$-inapproximability threshold for the {\it maximum induced matching problem} on bipartite graphs. On the positive side, we consider $(\alpha,\beta)$-approximations, i.e., of finding a subsystem with size at least $|\OPT|/\alpha$, which has a feasible solution violating the right-hand side by a factor of at most $\beta$. For general $0/1$-coefficient matrices, we give a polynomial-time $(O(\log(nm)),1+\epsilon)$-approximation for the case when $L=\poly(n,m)$. For interval matrices, we give a quasi-polynomial time $(1,1+\epsilon)$-approximation when $L=\poly(n,m)$ and a polynomial time $(O(\log^2n\log\log (nL)),1+\epsilon)$- approximation in the general case, and complement the first result by showing that, when no violation is allowed, the problem is APX-hard. Clearly all the above results apply to systems of equations ($l_i=u_i$) with $0/1$-coefficients. As further applications, we show how these results apply to a recently-studied profit-maximizing pricing problem, and to the problem of drawing interval graphs given length constraints on the intervals.

### S. Charles Brubaker. Clustering on Noisy Mixtures

Abstract: This paper presents a polynomial algorithm for learning mixtures of log-concave distributions in R^n in the presence of malicious noise points. That is, each sample is corrupted with some small probability and replaced by a point about which we can make no assumptions. A key element of the algorithm is Robust Principle Components Analysis (PCA), which is less susceptible to corruption by noisy points. Where noise may cause standard PCA to collapse well-separated mixture components so that they are indistinguishable, Robust PCA preserves the distance between the some of the components, making a partition possible. It then recurses on each half of the mixture until every component is isolated. The success of this algorithm requires only a O(log n) factor increase in the required separation between components of the mixture compared to the noiseless case.

### Ashish Goel, Michael Kapralov and Sanjeev Khanna. Perfect matchings via uniform sampling in regular bipartite graphs

Abstract: Regular bipartite graphs occur in many real life applications, including scheduling, routing, and task assignment. In particular, finding a perfect matching in a regular bipartite graph is a well-studied problem. The first non-trivial algorithm, with running time $O(mn)$, dates back to König's work in 1916 (here $m=nd$ is the number of edges in the graph, $2n$ the number of vertices, and $d$ the degree of each node). The currently most efficient algorithm takes time $O(m)$, and is due to Cole, Ost, and Schirra. In this paper, we further improve this running time to $O(\min\{m,n^{1.75}\ln n\})$. We obtain this improvement by proving a uniform sampling theorem: if we sample each edge in a $d$-regular bipartite graph independently with a probability $p = O(\frac{n\ln n}{d^2})$ then the resulting graph has a perfect matching with high probability. The proof involves a sequential decomposition procedure combined with an application of Karger's sampling theorem in each piece. Running the $O(m\sqrt{n})$ algorithm (due to Hopcroft and Karp) for finding maximum matchings in bipartite graphs on the sampled graph yields the stated running time. We provide an infinite family of instances to show that the sampling result is tight up to polylogarithmic factors. Thus any super-polylogarithmic improvements to our running time must either employ a different sampling procedure or improve the Hopcroft-Karp algorithm for the case of nearly regular bipartite graphs.

### David Karger and Debmalya Panigrahi. An $\tilde{O}(m)$ algorithm for constructing a cactus of an undirected graph

Abstract: We present an $\tilde{O}(m)$ algorithm for constructing the {\em cactus} data structure of an undirected graph, which captures all the global minimum edge cuts in the graph in $O(n)$ space. This represents a fundamental improvement over the previous best time bounds ($\tilde{O}(n^2)$ due to Karger and Stein) since the number of mincuts in an undirected graph can be $\tilde{\omega}(m)$, but has to be $O(n^2)$. Thus, unlike earlier algorithms, our algorithm cannot afford to spend even $O(1)$ time per mincut. Further, our result closes the gap between the time required for finding a single mincut ($\tilde{O}(m)$ due to Karger) and that for (implicitly) finding all the mincuts. Similar to the previous best algorithm, our algorithm is Monte-Carlo, ie gives the correct answer with high probability but does not give a certificate for checking correctness.

### Joel Tropp. Efficient Algorithms for Column Subset Selection

Abstract: Given a fixed matrix, the problem of column subset selection requests a column submatrix that has favorable spectral properties. Most research from the algorithms and numerical linear algebra communities focuses on a variant called rank-revealing {\sf QR}, which seeks a well-conditioned collection of columns that spans the (numerical) range of the matrix. The functional analysis literature contains another strand of work on column selection whose algorithmic implications have not been explored. In particular, a celebrated result of Bourgain and Tzafriri demonstrates that each matrix with normalized columns contains a large column submatrix that is exceptionally well conditioned. Unfortunately, standard proofs of this result cannot be regarded as algorithmic.

This paper presents a randomized, polynomial-time algorithm that produces the submatrix promised by Bourgain and Tzafriri. The method involves random sampling of columns, followed by a matrix factorization that exposes the well-conditioned subset of columns. This factorization, which is due to Grothendieck, is regarded as a central tool in modern functional analysis. The primary novelty in this work is an algorithm, based on eigenvalue minimization, for constructing the Grothendieck factorization. These ideas also result in a novel approximation algorithm for the $(\infty, 1)$ norm of a matrix, which is generally {\sf NP}-hard to compute exactly. As an added bonus, this work reveals a surprising connection between matrix factorization and the famous {\sc maxcut} semidefinite program.

### Gabriel Nivasch. Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations

Abstract: We present several new results regarding lambda_s(n), the maximum length of a Davenport-Schinzel sequence of order s on n distinct symbols.

First, we prove that lambda_s(n) <= n * 2^{1/t! alpha(n)^t + O(alpha(n)^{t-1})} for s>=4 even, and lambda_s(n) <= n * 2^{1/t! alpha(n)^t log_2 alpha(n) + O(alpha(n)^t)} for s>=3 odd, where t = floor((s-2)/2), and alpha(n) denotes the inverse Ackermann function. This constitutes an improvement for s>=6, since the previous bounds, by Agarwal, Sharir, and Shor (1989), had a leading coefficient of 1 instead of 1/t! in the exponent. The bounds for even s>=6 are now tight up to lower-order terms in the exponent. These new bounds result from a small improvement on the technique of Agarwal et al.

More importantly, we also present a new technique for deriving upper bounds for lambda_s(n). This new technique is based on some recurrences very similar to the ones used by the author, together with Alon, Kaplan, Sharir, and Smorodinsky (SODA 2008), for the problem of stabbing interval chains with j-tuples. With this new technique we: (1) re-derive the upper bound of lambda_3(n) <= 2n alpha(n) + O(n sqrt alpha(n)) (first shown by Klazar, 1999); (2) re-derive our own new upper bounds for general s; and (3) obtain improved upper bounds for the generalized Davenport-Schinzel sequences considered by Adamec, Klazar, and Valtr (1992).

Regarding lower bounds, we show that lambda_3(n) >= 2n alpha(n) - O(n) (the previous lower bound (Sharir and Agarwal, 1995) had a coefficient of 1/2), so the coefficient 2 is tight. We also present a simpler variant of the construction of Agarwal, Sharir, and Shor that achieves the known lower bounds of lambda_s(n) >= n * 2^{1/t! alpha(n)^t - O(alpha(n)^{t-1})} for s>=4 even.

### Raphael Yuster. Efficient algorithms on sets of permutations, dominance, and real-weighted APSP

Abstract: Sets of permutations play an important role in the design of some efficient algorithms. In this paper we design two algorithms that manipulate sets of permutations. Both algorithms, each solving a different problem, use fast matrix multiplication techniques to achieve a significant improvement in the running time over the naive solutions.

A set of permutations $P \subset S_n$ is {\em expanding} if the product of any two elements of $P$ yields a distinct permutation. Stated otherwise, $|P^2|=|P|^2$ where $P^2 \subset S_n$ is the set of products of two elements of $P$. Our first result is a randomized algorithm that computes $|P^2|$ and hence decides if $P$ is expanding. The algorithm also produces a table that, for any $\sigma_1,\sigma_2,\sigma_3,\sigma_4 \in P$, answers the query $\sigma_1\sigma_2 = \sigma_3\sigma_4$ in $\tilde{O}(1)$ time. The algorithm uses, among other ingredients, a combination of fast matrix multiplication and polynomial identity testing. In particular, for $|P|=n$ our algorithm runs in $O(n^\omega)$ time where $\omega < 2.376$ is the matrix multiplication exponent. We note that the naive deterministic solution for this problem requires $\Theta(n^3)$ time.

For a set of permutations $P \subset S_n$ we say that $i$ $k$-dominates $j$ if the number of permutations $\pi \in P$ for which $\pi(i) < \pi(j)$ is $k$. The {\em dominance matrix} of $P$ is the $n \times n$ matrix $D_P$ where $D_P(i,j)=k$ if and only if $i$ $k$-dominates $j$. We give an efficient algorithm for computing $D_P$ using fast {\em rectangular} matrix multiplication. In particular, when $|P|=n$ our algorithm runs in $O(n^{2.684})$ time. Computing the dominance matrix of permutations is computationally equivalent to the dominance problem in computational geometry. In particular, our algorithm slightly improves upon a well-known $O(n^{(\omega+3)/2})$ time algorithm of Matousek for the dominance problem. Permutation dominance is used, together with a few other ingredients, to obtain a truly sub-cubic algorithm for the {\em All Pairs Shortest Paths} (APSP) problem in real-weighted directed graphs, where the number of distinct weights emanating from each vertex is $O(n^{0.338})$. A very special case of this algorithm implies an $O(n^{2.842})$ time algorithm for real vertex-weighted APSP, which slightly improves a recent result of Chan [STOC-07].

### Gabor Tardos and Ehsan Amiri. High rate fingerprinting codes and the fi ngerprinting capacity

Abstract: Including a unique code in each copy of a distributed document is an effective way of fighting intellectual piracy. Codes designed for this purpose that are secure against collusion attacks are called fingerprinting codes.

In this paper we consider fingerprinting with the marking assumption and design codes that achieve much higher rates than previous constructions. We conjecture that these codes attain the maximum possible rate (the fingerprinting capacity) for any fixed number of pirates. We prove new upper bounds for the fingerprinting capacity that are not far from the rate of our codes.

We introduce the novel model of weak fingerprinting codes where one pirate should be caught only if the identity of all other pirates are revealed. We construct fingerprinting codes in this model with improved rates but our upper bound on the rate still applies. In fact, these improved codes achieve the fingerprinting capacity of the weak model by a recent upper bound.

Using analytic techniques we compare the rates of our codes in the standard model and the rates of the optimal codes in the weak model. To our surprise these rates asymptotically agree, that is, their ratio tends to $1$ as $t$ goes to infinity. Although we cannot prove that each one of our codes in the standard model achieves the fingerprinting capacity, this proves that asymptotically they do.

### Yury Person and Mathias Schacht. Almost all hypergraphs without Fano planes are bipartite

Abstract: The hypergraph of the Fano plane is the unique hypergraph with $7$ triples on $7$ vertices in which every pair of vertices is contained in a unique triple. It is not $2$-colorable, but becomes so on deleting any hyperedge. We show that taking uniformly at random a $3$-uniform hypergraph $H$ on $n$ vertices not containing the Fano plane, $H$ turns out to be bipartite (or $2$-colorable) with probability at least $1-2^{-\Omega(n^2)}$. To prove this result we will study structural properties of Fano plane-free hypergraphs. In particulary, we prove that only with exponentially small probability ($2^{-\Omega(n^3)}$) they are $\eps$-far from being bipartite.

These results seem to be interesting in the light of the well-known fact, that to decide whether a given $3$-uniform hypergraph is bipartite is $NP$-complete. On the other hand, the property of being bipartite is known to be testable. We hope that understanding better the structure of (hyper-)graph properties might be useful for average case analysis of running time of coloring algorithms on restricted hypergraph classes, and also advantageous in developing efficient property testers.

### Amr Elmasry. Pairing Heaps with $O(\log{\log{n}})$ {\it decrease} Cost

Abstract: We give a variation of the pairing heaps for which the time bounds for all the operations match the lower bound proved by Fredman for a family of similar self-adjusting heaps. Namely, our heap structure requires $O(1)$ for insert and find-min, $O(\log{n})$ for delete-min, and $O(\log\log{n})$ for decrease-key and meld (all the bounds are in the amortized sense except for find-min).

### Haim Kaplan and Uri Zwick. A simpler implementation and analysis of Chazelle's Soft Heaps

Abstract: Chazelle (JACM 47(6), 2000) devised an approximate meldable priority queue data structure, called SOFT HEAPS, and used it to obtain the fastest known deterministic comparison-based algorithm for computing minimum spanning trees, as well as some new algorithms for selection and approximate sorting problems. If $n$ elements are inserted into a collection of soft heaps, then up to $\epsilon n$ of the elements still contained in these heaps, for a given \emph{error parameter} $\epsilon$, may be CORRUPTED, i.e., have their keys artificially increased. In exchange for allowing these corruptions, each soft heap operation is performed in $O(\log\frac{1}{\eps})$ amortized time.

Chazelle's soft heaps are derived from the BINOMIAL HEAPS data structure in which each priority queue is composed of a collection of BINOMIAL TREES. We describe a simpler and more direct implementation of soft heaps in which each priority queue is composed of a collection of standard BINARY trees. Our implementation has the advantage that no CLEAN-UP operations similar to the ones used in Chazelle's implementation are required. We also present a concise and unified potential-based amortized analysis of the new implementation.

### Mikkel Thorup, Uri Zwick and Omid Madani. Discounted Deterministic Markov Decision Processes and Discounted All-Pairs Shortest Paths

Abstract: We present an $O(mn+n^2\log n)$-time algorithm for finding optimal strategies for discounted, infinite-horizon, Deterministic Markov Decision Processes (DMDP), where $n$ is the number of vertices (or states) and $m$ is the number of edges (or actions). This improves a recent $O(mn^2)$-time algorithm of Andersson and Vorobyov.

We also present algorithms for finding discounted all-pairs shortest paths.

### Alon Shalita and Uri Zwick. Efficient algorithms for the 2-gathering problem

Abstract: Pebbles are placed on some vertices of a directed graph. Is it possible to move each pebble along at most one edge of the graph so that in the final configuration no pebble is left alone? We give an $O(mn)$-time algorithm for solving this problem, which we call the 2-GATHERING problem, where $n$ is the number of vertices and $m$ is the number of edges of the graph. If such a 2-gathering is not possible, the algorithm finds a solution that minimizes the number of lonely' pebbles. The 2-gathering problem forms a non-trivial generalization of the non-bipartite matching problem and it is solved by extending the augmenting paths technique used to solve matching problems.

Polynomial time algorithms for the 2-gathering problem can be obtained via reductions to the \{K_{2},K_{3}\}-packing problem studied by Hell and Kirkpatrick, the general factor problem studied by Cornue'jols, and to the simplex matching problem studied recently by Anshelevich and Karagiozova. The resulting algorithms, however, are much slower than the new algorithm presented.

### david cohen-steiner, Herbert Edelsbrunner, John Harer and Dmitriy Morozov. Persistent Homology for Kernels, Images, and Cokernels

Abstract: Motivated by the measurement of local homology and of functions on noisy domains, we extend the notion of persistent homology to sequences of kernels, images, and cokernels of maps induced by inclusions in a filtration of pairs of spaces. Specifically, we note that persistence in this context is well defined, we prove that the persistence diagrams are stable, and we explain how to compute them.

### Fedor Fomin, Petr Golovach, Daniel Lokshtanov and Saket Saurabh. Clique-width: On the Price of Generality

Abstract: Many hard problems can be solved efficiently when the input is restricted to graphs of bounded treewidth. By the celebrated result of Courcelle, every decision problem expressible in monadic second order logic is fixed parameter tractable when parameterized by the treewidth of the input graph. Moreover, for every fixed k ? 0, such problems can be solved in linear time on graphs of treewidth at most k. In particular, this implies that basic problems like Dominating Set, Graph Coloring, Clique, and Hamiltonian Cycle are solvable in linear time on graphs of bounded treewidth. A significant amount of research in graph algorithms has been devoted to extending this result to larger classes of graphs. It was shown that some of the algorithmic meta-theorems for treewidth can be carried over to graphs of bounded clique-width. Courcelle, Makowsky, and Rotics proved that the analogue of Courcelle?s result holds for graphs of bounded clique-width when the logical formulas do not use edge set quantifications. Despite of its generality, this does not resolve the parameterized complexity of many basic problems concerning edge subsets (like Edge Dominating Set), vertex partitioning (like Graph Coloring), or global connectivity (like Hamiltonian Cycle). There are various algorithms solving some of these problems in polynomial time on graphs of clique-width at most k. However, these are not fixed parameter tractable algorithms and have typical running times O(n^f(k)), where n is the input length and f is some function. It was an open problem, explicitly mentioned in several papers, whether any of these problems is fixed parameter tractable when parameterized by the clique-width, i.e. solv-able in time O(g(k)·n^c), for some function g and a constant c not depending on k. In this paper we resolve this problem by showing that Edge Dominating Set, Hamiltonian Cycle, and Graph Coloring are W[1]-hard parameterized by clique-width. This shows that the running time O(n^f(k)) of many clique-width based algorithms is essentially the best we can hope for (up to a widely believed assumption from parameterized complexity, namely FPT != W[1])?the price we pay for generality.

### Parinya Chalermsook and Julia Chuzhoy. Maximum Independent Set of Rectangles

Abstract: We study the Maximum Independent Set of Rectangles problem (MISR): given a collection R of n axis-parallel rectangles, find a maximum-cardinality subset of disjoint rectangles. MISR is a special case of the classical Maximum Independent Set problem, where the input is restricted to intersection graphs of axis-parallel rectangles. Due to its many applications, ranging from map labeling to data mining, MISR has received a significant amount of attention from various research communities. Since the problem is NP-hard, the main focus has been on designing approximation algorithms. Several groups of researches have independently suggested O(log n)-approximation algorithms for MISR, and this remained the best currently known approximation factor for the problem. The main result of our paper is an O(log log n)-approximation algorithm for MISR. Our algorithm combines existing approaches for solving special cases of the problem, in which the input set of rectangles is restricted to containing only specific intersection types, with new insights into the combinatorial structure of sets of intersecting rectangles in the plane.

We also consider a generalization of MISR to higher dimensions, where rectangles are replaced by d-dimensional hyper-rectangles. This problem is known as Maximum Independent Set on d-box graphs. Our results for MISR imply an O((log n)^{d-2}loglog n) approximation algorithm for this problem, improving upon the best previously known O((log n)^{d-1})-approximation.

### Brendan Nagle, Annika Poerschke, Vojtech Rödl and Mathias Schacht. On Algorithmic Hypergraph Regularity

Abstract: Thomason and Chung, Graham, and Wilson were the first to systematically study quasi-random graphs and hypergraphs, and proved that several properties of random graphs imply each other in a determinstic sense. Their concepts of quasi-randomness match the notion of regularity from the earlier Szemeredi Regularity Lemma. In contrast, there exists no "natural" hypergraph regularity lemma matching the notions of quasi-random hypergraphs considered by those authors.

Here, we study several notions of quasi-randomness for 3-uniform hypergraphs which correspond to the regularity lemmas of Frankl and Rödl, Gowers and Haxell, Nagle and Rödl. We establish an equivalence among the three notions of regularity of these lemmas. Since the regularity lemma of Haxell et al. is algorithmic, we obtain algorithmic versions of the lemmas of Frankl-Rödl (a special case thereof) and Gowers as corollaries. As a further corollary, we show that the special case of the Frankl-Rödl lemma (which we can make algorithmic) suffices for an application of its corresponding Counting Lemma.

### Robi Krauthgamer, Seffi Naor and Roy Schwartz. Partitioning Graphs into Balanced Components

Abstract: We consider the {\em $k$-balanced partitioning} problem, where the goal is to partition the vertices of an input graph $G$ into $k$ equally sized components, while minimizing the total weight of the edges connecting different components. We allow $k$ to be part of the input and denote the cardinality of the vertex set by $n$. This problem is a natural and important generalization of well-known graph partitioning problems, including {\em minimum bisection} and {\em minimum balanced cut}.

We present a bi-criteria approximation algorithm that achieves an approximation factor of $O(\sqrt{\log{n}\log{k}})$, which matches or improves over previous algorithms for all relevant values of $k$. Our algorithm uses a semidefinite relaxation which combines $\ell _2^2$ metrics with spreading metrics. Surprisingly, we show that the integrality gap of the semidefinite relaxation is $\Omega (\log{k})$ even for large values of $k$ (e.g., $k=n^{\Omega(1)}$), implying that the dependence on $k$ of the approximation factor is necessary. This is in contrast to the situation with previous approximation algorithms for $k$-balanced partitioning which are based on linear programming relaxations and where the approximation factor is independent of $k$.

### Nikhil Bansal, Ho-Leung Chan and Kirk Pruhs. Speed Scaling with an Arbitrary Power Function

Abstract: All of the theoretical speed scaling research to date has assumed that the power function, which expresses the power consumption $P$ as a function of the processor speed $s$, is of the form $P=s^\alpha$, where $\alpha > 1$ is some constant. Motivated in part by technological advances, we initiate a study of speed scaling with arbitrary power functions. We consider the problem of minimizing the total flow plus energy. Our main result is a $(3+\epsilon)$-competitive algorithm for this problem, that holds for essentially any power function. We also give a $(2+\epsilon)$-competitive algorithm for the objective of fractional weighted flow plus energy. Even for power functions of the form $s^\alpha$, it was not previously known how to obtain competitiveness independent of $\alpha$ for these problems. We also introduce a model of allowable speeds that generalizes all known models in the literature.

### Zdenek Dvorak, Daniel Kral and Robin Thomas. Coloring triangle-free graphs on surfaces

Abstract: Gimbel and Thomassen asked whether the 3-colorability of a triangle-free graph drawn on a fixed surface can be tested in polynomial time. We settle the question by giving a linear-time algorithm for every surface. When combined with previous results this gives a linear-time algorithm to compute the chromatic number of a triangle-free graph drawn on a fixed surface.

Our algorithm is based on a structure theorem that for a triangle-free graph drawn on a surface S guarantees the existence of (and can be converted to a linear-time algorithm to find) a subgraph H, whose size depends only on S, such that there is an easy test whether a 3-coloring of H extends to a 3-coloring of G. The test is based on a topological obstruction, called the winding number" of a 3-coloring. To prove the structure theorem we make use of disjoint paths with specified ends (a.k.a. integral multicommodity flows) to find a 3-coloring.

If the input triangle-free graph G drawn in S is 3-colorable we can find a 3-coloring in quadratic time, and if G quadrangulates S then we can find the 3-coloring in linear time. The latter algorithm requires two ingredients that may be of independent interest: a generalization of a data structure of Kowalik and Kurowski to weighted graphs and a speedup of a disjoint paths algorithm of Robertson and Seymour to linear time.

### Amitabh Basu, Pierre Bonami, gerard cornuejols and Francois Margot. On the Relative Strength of Split, Triangle and Quadrilateral Cuts (Extended Abstract)

Abstract: Integer programs defined by two equations with two free integer variables and nonnegative continuous variables have three types of nontrivial facets: split, triangle or quadrilateral inequalities. In this paper, we compare the strength of these three families of inequalities. In particular we study how well each family approximates the integer hull. We show that, in a well defined sense, triangle inequalities provide a good approximation of the integer hull. The same statement holds for quadrilateral inequalities. On the other hand, the approximation produced by split inequalities may be arbitrarily bad.

### Raphael Clifford, Klim Efremenko, Ely Porat and Amir Rothschild. From coding theory to efficient pattern matching

Abstract: We consider the classic problem of pattern matching with few mismatches in the presence of promiscuously matching wildcard symbols. Given a text t of length n and a pattern p of length m with optional wildcard symbols and a bound k, our algorithm finds all the locations for which the pattern matches the text with Hamming distance at most k. The algorithm we present is deterministic and runs in \tilde{O}(kn) time, returning the location of each mismatch at no extra cost. The solutions we develop borrow from the tool set of algebraic coding theory and provide a new framework in which to tackle approximate pattern matching problems.

### Ramesh Hariharan and Anand Bhalgat. Fast Edge Orientation for Unweighted Graphs

Abstract: We consider an unweighted undirected graph with $n$ vertices, $m$ edges, and edge connectivity $2k$. The {\em weak edge orientation problem} requires that the edges of this graph be oriented so the resulting directed graph is at least $k$ edge connected. Nash-Williams proved the existence of such orientations and subsequently Frank \cite{F93}, Gabow \cite{G94}, and Nagamochi-Ibaraki gave algorithmic constructions. All of these algorithm took time at least quadratic in $n$. We provide the first sub-quadratic (in $n$) algorithm for this problem. Our algorithm takes $\tilde{O}(nk^4+m)$ time. This improves the previous best bounds of $\tilde{O}(n^2k^2+m)$ by Gabow \cite{G94} and $\tilde{O}(n^2m)$ by Nagamochi-Ibaraki when $k \le \sqrt{n}$. Indeed, many real networks have $k\ll n$.

Our algorithm uses the fast edge splitting paradigm introduced by Bhalgat et al. \cite{BHKP08}. We seek to split out a large fraction of the vertices, recurse on the resulting graph, and then put back the split-off vertices. The main challenge we face is that only vertices with even degree may be split-off in an undirected graph and there may not be any such vertex in the current graph. The edge orientation algorithms of Gabow and Nagamochi-Ibaraki as well as Frank's proof are based on showing the existence of at least two even degree vertices (in fact, vertices with degree $2k$) in a $2k$ minimally connected graph. We generalize this to show that in any edge minimal $2k$ connected graph, there are at least $n/3$ even degree vertices. These vertices are then split-off.

Our next challenge is to drop edges from the given graph so it remains $2k$ connected and yet has $\Omega(n)$ even degree vertices. We provide two algorithms for this. The first algorithm produces an edge-minimal $2k$ connected graph in time $\tilde{O}(nk^5+m)$; this improves the previous best $\tilde{O}(n^2k^2 + m)$ algorithm for this task due to by Gabow \cite{G94}. The second algorithm speeds this up by a factor of $k$ by giving up the minimality criterion; it discards edges specifically to produce $\Omega(n)$ even degree vertices while maintaining connectivity $2k$ and takes time $\tilde{O}(nk^4+m)$.

### Viswanath Nagarajan and Maxim Sviridenko. On the Maximum Quadratic Assignment Problem

Abstract: Quadratic assignment is a basic problem in combinatorial optimization, which generalizes several other problems such as Traveling Salesman, Linear Arrangement, Dense k Subgraph, and Clustering with given sizes. Quadratic Assignment is defined relative to two n by n symmetric non-negative matrices. In this paper, we study the Maximum Quadratic Assignment problem, and give an ~\sqrt{n} approximation algorithm, which is the first non-trivial approximation guarantee for this problem. The above guarantee also holds when the input matrices are asymmetric. An indication of the hardness of Maximum Quadratic Assignment is that it contains as a special case, the Dense k Subgraph problem, for which the best known approximation guarantee is ~n^{1/3} (Feige et al.~2001).

When one of the matrices satisfies triangle inequality, we give an algorithm achieving approximation ratio ~ 3.16, which improves over the previous best factor of 4 (Arkin et al. 2001).

See complete abstract in pdf file.

### Bernard Chazelle. Natural Algorithms

Abstract: We provide further evidence that the study of complex self-organizing systems can benefit from an algorithmic perspective. The subject has been traditionally viewed through the lens of physics and control theory. Using tools associated with computer science, we settle a longstanding open question in theoretical ecology: the convergence of bird flocks in the Reynolds model. We bound the time to reach steady state by a tower-of-twos of height exponential in the number of birds. We prove that, surprisingly, the tower-of-twos growth is intrinsic to the model. This unexpected result demonstrates the merits of approaching biological dynamical systems as "natural algorithms" and applying algorithmic tools to them.

### Timothy M. Chan. Comparison-Based, Time-Space Lower Bounds for Selection

Abstract: We establish the first nontrivial lower bounds on time-space tradeoffs for the selection problem. We prove that any comparison-based, randomized algorithm for finding the median requires $\Omega(n\log\log_S n)$ expected time in the RAM model (or more generally in the comparison branching program model), if we have $S$ bits of extra space besides the read-only input array. This bound is tight for all $S\gg\log n$, and remains true even if the array is given in a random order. Our result thus answers a 16-year-old question of Munro and Raman, and also complements recent lower bounds that are restricted to sequential access, as in the multi-pass streaming model [Chakrabarti \etal, SODA 2008].

We also prove that any comparison-based, deterministic, multi-pass streaming algorithm for finding the median requires $\Omega(n\log^*(n/s) + n\log_s n)$ worst-case time (in scanning plus comparisons), if we have $s$ cells of space. This bound is also tight for all $s\gg\log^2 n$. We can get similar deterministic lower bounds for I/O-efficient algorithms, or for the two-dimensional linear programming problem.

All proofs are elementary''.

### Peyman Afshani and Timothy M. Chan. Optimal Halfspace Range Reporting in Three Dimensions

Abstract: We give the first optimal solution to a standard problem in computational geometry: three-dimensional halfspace range reporting. We show that $n$ points in 3-d can be stored in a linear-space data structure so that all $k$ points inside a query halfspace can be reported in $O(\log n+k)$ time. The data structure can be built in $O(n\log n)$ expected time. The previous methods with optimal query time requires superlinear ($O(n\log\log n)$) space.

We mention consequences to external-memory data structures, and as an aside, we partially answer another open question concerning the crossing number in Matou\v sek's {\em shallow partition theorem\/} in the 3-d case (a tool used in known halfspace range reporting methods).

### Justin Salez and Devavrat Shah. Optimality of Belief Propagation for Random Assignment Problem

Abstract: The assignment problem concerns finding the minimum cost perfect matching in a complete weighted bipartite graph. The best known algorithm, due to Edmonds and Karp (1972), for this classical question finds a solution in O(n^3) time for a graph of size n. Clearly, any algorithm requires \Omega(n^2) time. For decades, it has not been answered whether optimal computation time is closer to n^3 or n2? In this paper, we provide answer to this question for random instance of assignment problem. Specifically, we establish that Belief Propagation essentially finds solution in O(n2) time when edge weights are i.i.d. with light tailed distribution. To establish this result, we use the formalism of local weak convergence introduced by Aldous (1992, 2000). The standard next step requires proving existence of ?correlation decay?. Interestingly enough, even though we find that there is no correlation decay, we are still able to prove convergence of belief propagation. Understanding such different method of convergence beyond correlation decay for BP should be of interest in its own right.

### Ping Li. Compressed Counting

Abstract: Counting the $\alpha$th frequency moment, $F_{(\alpha)} = \sum_{i=1}^D A_t[i]^\alpha$, of a streaming signal $A_t$ (where $t$ denotes time), has been an active area of research. When $0<\alpha\leq 2$, one popular algorithm for approximating $F_{(\alpha)}$ is based on symmetric stable random projections, whose sample complexity is $O\left(1/\epsilon^2\right)$, even for $\alpha = 1$.

Compressed Counting (CC) is proposed for efficiently computing the $\alpha$th frequency moment, also for $0<\alpha\leq2$. In the neighborhood of $\alpha = 1$, its sample complexity is $O\left(1/\epsilon\right)$, instead of $O\left(1/\epsilon^2\right)$. The underlying technique of CC is maximally-skewed stable random projections.

Our contributions include:

1) Compressed Counting (CC) is the first proposal of using skewed projections in data stream computations. We also show that maximally-skewed projections can achieve the best performance.

2) CC is the first algorithm which captures the intuition that, when $\alpha =1$ a simple counter suffices, and when $\alpha = 1\pm\Delta$ with small $\Delta$, the sample complexity should be low. We show the sample complexity of a proposed estimator $= \frac{G}{\epsilon^2}\log\left(\frac{2}{\delta}\right)$, where $G= O\left(\epsilon\right)$ as $\Delta\rightarrow 0$. In other words, for small $\Delta$, CC has the complexity $=O\left({1}/{\epsilon}\right)$. Previous results only achieved $O\left(1/\epsilon^2\right)$ (even for $\alpha =1$), which in general is expected and can not be improved, according to the central limit theorem.

3) We show, when $\alpha = 1\pm\Delta$, the asymptotic variance of a proposed estimator is $\propto \Delta$. As $\alpha \rightarrow 1$, CC achieves an infinite improvement'' over the previous results, in terms of the asymptotic variances.

4) Our results (especially when $\alpha=1\pm\Delta\approx 1$) have important applications. In some situation, $\Delta$ might be interpreted as the decay rate'' or interest rate,'' which is usually small. The method of moments is popular for statistical inference, which requires computing frequency moments. Also, some important summary statistics such as Renyi entropy and Tsallis entropy are functions of frequency moments and hence CC naturally provides an efficient algorithm to compute them. Very importantly, CC may serve the basic building element for developing other algorithms, for example, approximating the Shannon entropy using Renyi entropy and Tsallis entropy with $\alpha\approx 1$.

4) Our results enrich the fundamental theory of skewed stable distributions.

Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane and Mihai Patrascu. The Geometry of Binary Search Trees

Abstract: We present a novel connection between binary search trees (BSTs) and points in the plane satisfying a simple property. Using this correspondence, we achieve the following results:

1. A surprisingly clean restatement in geometric terms of many results and conjectures relating to BSTs and dynamic optimality.

2. A new lower bound for searching in the BST model, which subsumes the previous two known bounds of Wilber [FOCS'86].

3. The first proposal for dynamic optimality not based on splay trees. A natural greedy but offline algorithm was presented by Lucas [1988], and independently by Munro [2000], and was conjectured to be an (additive) approximation of the best binary search tree. We show that there exists an equal-cost online algorithm, transforming the conjecture of Lucas and Munro into the conjecture that the greedy algorithm is dynamically optimal.

### Satoru Iwata and James Orlin. A Simple Combinatorial Algorithm for Submodular Function Minimization

Abstract: This paper presents a new simple algorithm for minimizing submodular functions. For integer valued submodular functions, the algorithm runs in O(n^6 EO log nM)time, where n is the cardinality of the ground set, M is the maximum absolute value of the function value, and EO is the time for function evaluation. The algorithm can be improved to run in O((n^4 EO + n^5) log nM) time. The strongly polynomial version of this faster algorithm runs in O((n^5 EO + n^6) log n) time for real valued general submodular functions. These are comparable to the best known running time bounds for submodular function minimization.

The algorithm can also be implemented in strongly polynomial time using only additions, subtractions, comparisons, and the oracle calls for function evaluation. This is the first fully combinatorial submodular function minimization algorithm that does not rely on the scaling method.

### Prasad Raghavendra and David Steurer. Towards Computing the Grothendieck Constant

Abstract: The \emph{Grothendieck constant $K_G$} is the smallest constant such that for every $n\in \N$ and every matrix $A = (a_{ij})$ the following holds, \begin{displaymath} \sup_{\vec u_i,\vec v_j \in B^{(n)}} \sum_{ij} a_{ij} \langle \vec u_i , \vec v_j\rangle \leq K_G \cdot \sup_{x_i,y_j \in [-1,1]} \sum_{ij} a_{ij} x_i y_j \, , \end{displaymath} where $B^{( n)}$ is the unit ball in $\mathbb R^n$. Despite several efforts \cite{krivine, reeds}, the value of the constant $K_G$ remains unknown. The Grothendieck constant $K_G$ is precisely the integrality gap of a natural SDP relaxation for the \textsc{$K_{N,N}$-QuadraticProgramming} problem. The input to this problem is a matrix $A = (a_{ij})$ and the objective is to maximize the quadratic form $\sum_{ij} a_{ij} x_i y_j$ over $x_i, y_j \in [-1,1]$. In this work, we apply techniques from~\cite{prasad1} to the \BQP problem. % Using some standard but non-trivial modifications, the reduction in \cite{prasad1} yields the following hardness result: Assuming the Unique Games Conjecture, it is NP-hard to approximate the \BQP problem to any factor better than the Grothendieck constant $K_G$. By adapting a bootstrapping'' argument used in a proof of Grothendieck inequality \cite{linden}, we perform a tighter analysis than \cite{prasad1}. Through this careful analysis, we obtain the following new results: \begin{itemize} \item An approximation algorithm for \BQP that is guaranteed to achieve an approximation ratio arbitrarily close to the Grothendieck constant $K_G$ (optimal approximation ratio assuming the Unique Games Conjecture). \item We show that the Grothendieck constant $K_G$ can be computed within an error $\eta$, in time depending only on $\eta$. Specifically, for each $\eta$, we formulate an explicit finite linear program, whose optimum is $\eta$-close to the Grothendieck constant. \end{itemize}

We also exhibit a simple family of operators on the Gaussian Hilbert space that is guaranteed to contain tight examples for the Grothendieck inequality. To achieve this, we give a direct conversion from dictatorship tests to integrality gap instances bypassing the use of a reduction from \textsc{UniqueGames} and the Khot-Vishnoi \cite{khotvishnoi} integrality gap instances for \textsc{UniqueGames}.

### Mordecai J. Golin, Xiaoming Xu and Jiajin Yu. A Generic Top-Down Dynamic-Programming Approach to Prefix-Free Coding

Abstract: Given a probability distribution over a set of n words, the Huffman-Coding problem is to find a minimal-cost prefix free code for transmitting/storing those words. Due to its nice structural properties, the basic Huffman-coding problem can be solved in O(n log n) time but, because they lack these properties, variations of the problem are more difficult. A small number of such variations have been shown to be solvable using a bottom-up (on the code tree) dynamic programming approach but the most generic solution method utilizes a top-down dynamic-programming one.

In this paper we show that the top-down approach can be sped up, permitting an order of magnitude improvement in the running time of many algorithms in the literature for such Huffman-coding variations as mixed radix, reserved length and one-ended coding. These speedups are immediate implications of a general structural property that permits batching together the calculation of many DP entries.

### Ken-ichi Kawarabayashi, Erik Demaine and Mohammad Taghi Haijaghayi. Additive Approximation Algorithms for List-Coloring Minor-Closed Class of Graphs

Abstract: It is known that computing the list-chromatic number is much harder than the chromatic number (assuming that the complexity classes $NP$ and $coNP$ are different.). In fact, the problem of deciding if a given graph is $f$-list-colorable for a function $f : V \to \{k-1,k\}$ for $k \geq 3$ is $\Pi_{2}^p$-complete. In general, it is believed that approximating list-coloring is hard for dense graphs.

In this paper, we are interested in sparse graphs. More specifically, we deal with minor-closed class of graphs, i.e., graphs without $K_k$-minors. We develop the seminal structure theorem of Robertson and Seymour, and then give an additive approximation for list-coloring within $k-2$ of the list-chromatic number. This improves the $O(k)$-multiplicative-approximation algorithm by Kawarabayashi and Mohar (STOC'06). Clearly our result gives rise to an additive approximation algorithm for graph-coloring of minor-closed class of graphs too. This result is comparable to the 2-approximation algorithm of graph-coloring by Demaine, Hajiaghayi and Kawarabayashi (FOCS'05), since our additive approximation algorithm may give a better graph-coloring. This result also answers a question posed by Robin Thomas (who conjectured that there is an additive approximation algorithm for graph-coloring of minor-closed class of graphs).

Our structure theorem is of independent interest in the sense that it gives rise to a new insight on well-connected $H$-minor-free graphs. In particular, this class of graphs can be easily decomposed into two parts so that one part has bounded tree-width and the other part is disjoint union of bounded genus graphs. Moreover, we can control the number of edges between two parts. Also, the proof method itself tells us how knowledge of a local structure can be used to gain a global structure. This may be of interest, since this gives a new insight how to decompose a graph, with help of a local structure information.

### Ken-ichi Kawarabayashi and Bruce Reed. A Nearly Linear Time Algorithm For The Half Integral Parity Disjoint Paths Packing Problem

Abstract: We consider the following problem, which is called the {\it half integral parity disjoint paths packing problem}.

\medskip

{\bf Input}: A graph $G$, $k$ pair of vertices $(s_1,t_1),(s_2,t_2),\dots, (s_k,t_k)$ in $G$ (which are sometimes called {\it terminals}), and a parity $l_i$ for each $i$ with $1 \leq i \leq k$, where $l_i=0$ or $1$.

\medskip

{\bf Output} : Paths $P_1,\dots,P_k$ in $G$ such that $P_i$ joins $s_i$ and $t_i$ for $i=1,2,\dots,k$ and parity of length of the path $P_i$ is $l_i$, i.e, if $l_i=0$, then length of $P_i$ is even, and if $l_i=1$, then length of $P_i$ is odd for $i=1,2,\dots,k$.

In addition, each vertex is on at most two of these paths.

\medskip

We present an $O(m \alpha(m,n) \log n)$ algorithm for fixed $k$, where $n,m$ are the number of vertices and the number of edges, respectively, and the function $\alpha(m,n)$ is the inverse of the Ackermann function. This is the first polynomial time algorithm for this problem, and generalizes polynomial time algorithms by Kleinberg (STOC'98) and Kawarabayashi and Reed (SODA'08), respectively, for the half integral disjoint paths packing problem, i.e., without the parity requirement.

As with the Robertson-Seymour algorithm to solve the $k$ disjoint paths problem, in each iteration, we would like to either use a huge clique minor as a ''crossbar", or exploit the structure of graphs in which we cannot find such a minor. Here, however, we must maintain the parity of the paths and can only use an ''odd clique minor". We must also describe the structure of those graphs in which we cannot find such a minor and discuss how to exploit it.

In fact, we also have algorithms running in $O(m^{(1+\epsilon)})$ time for any $\epsilon > 0$ for this problem, if $k$ is up to $o(\log{\log{\log n}})$ for general graphs, up to $o(\log{\log n})$ for planar graphs, and up to $o(\log{\log n/g})$ for graphs on the surface, where $g$ is Euler genus. Furthermore, if $k$ is fixed, then we have linear time algorithms for the planar case and for the bounded genus case.

### Michel Goemans, Nicholas J.A. Harvey, Satoru Iwata and Vahab Mirrokni. Approximating Submodular Functions Everywhere

Abstract: Submodular functions are a key concept in combinatorial optimization. Algorithms that involve submodular functions usually assume that they are given by a (value) oracle. Using only polynomially many queries to the oracle, one can minimize a submodular function or approximate its maximum within a constant.

In this paper, we consider the problem of approximating a monotone submodular function $f$ on a ground set of size $n$ {\it everywhere}, after only polynomially many oracle queries. Our main result is a deterministic algorithm that make polynomially many oracle queries to derive a function $\hat{f}$ of the form $\hat{f}(S)=\sqrt{\sum_{i\in S} c_i}$ such that, for {\it every} set $S$, $\hat{f}(S)$ approximates $f(S)$ within a factor $\alpha(n)$, where $\alpha(n)=\sqrt{n+1}$ for rank functions of matroids and $\alpha(n)=O(\sqrt{n} \log{n})$ for general monotone submodular functions. Our result is based on approximately finding a maximum volume inscribed ellipsoid in a symmetrized polymatroid, and the analysis involves various properties of submodular functions and polymatroids. We should point out that the general algorithm of Grötschel, Lov\'asz and Schrijver for finding a large inscribed ellipsoid in a centrally symmetric convex body given by a separation oracle would only give us an approximation factor of $O(n)$.

Our algorithm is tight up to logarithmic factors. Indeed, we show that no algorithm can achieve a factor better than $\Omega(\sqrt{n} / \log(n))$, even for rank functions of a matroid.

### Baharak Rastegari, Anne Condon and Kevin Leyton-Brown. Stepwise Randomized Combinatorial Auctions Achieve Revenue Monotonicity

Abstract: In combinatorial auctions that use VCG, a seller can sometimes increase revenue by dropping bidders. In our previous work (AAAI'07), we showed that such failures of revenue monotonicity'' occur under an extremely broad range of deterministic strategyproof combinatorial auction mechanisms, even when bidders have known single-minded'' valuations. In this work we consider the question of whether revenue monotonic, strategyproof mechanisms for such bidders can be found in the broader class of randomized mechanisms. We demonstrate that---surprisingly---such mechanisms do exist, show how they can be constructed, and consider algorithmic techniques for implementing them in polynomial time.

More formally, we characterize a class of randomized mechanisms defined for known single-minded bidders that are strategyproof and revenue monotonic, and furthermore satisfy some other desirable properties, namely participation, consumer sovereignty and maximality, representing the mechanism as a solution to a quadratically constrained linear program. We prove that the QCLP is always feasible (i.e., for all bidder valuations) and give its solution analytically. Furthermore, we give an algorithm for running such a mechanism in time quadratic in the number of bidders; this is interesting because constructing an instance of such mechanisms from our QCLP formulation in a naive way can be of exponential time.

Ilia Binder and Mark Braverman. The complexity of simulating Brownian Motion Abstract: We analyze the complexity of the Walk on Spheres algorithm for simulating Brownian Motion in a domain Omega in R^d. The algorithm, which was first proposed in the 1950s, produces samples from the hitting probability distribution of the Brownian Motion process on boundary of Omega within an error of epsilon. The algorithm is used as a building block for solving a variety of differential equations, including the Dirichlet Problem.

The WoS algorithm simulates a BM starting at a point X_0=x in a given bounded domain Omega until it gets epsilon-close to the boundary of Omega. At every step, the algorithm measures the distance d_k from its current position X_k to the boundary of Omega and jumps a distance of d_k/2 in a uniformly random direction from X_k to obtain X_{k+1}. The algorithm terminates when it reaches X_n that is epsilon-close to the boundary of Omega.

It is not hard to see that the algorithm requires at least Omega(\log 1/epsilon) steps to converge. Only partial results with respect to upper bounds existed. In 1959 M. Motoo established an O(\log 1/epsilon) bound on the running time for convex domains. The results were later generalized for a wider, but still very restricted, class of planar and 3-dimensional domains by G.A. Mikhailov (1979). In our earlier work (2007), we established an upper bound of O(\log^2 1/epsilon) on the rate of convergence of WoS for arbitrary planar domains.

In this paper we introduce subharmonic energy functions to obtain very general upper bounds on the convergence of the algorithm. Special instances of the upper bounds yield the following results for bounded domains Omega:

* if Omega is a planar domain with connected exterior, the WoS converges in O(\log 1/epsilon) steps;

### Umang Bhaskar, Lisa Fleischer, Darrell Hoy and Chien-Chung Huang. Equilibria of Collusive Flow Games are not Unique

Abstract: In STOC 2006, Hayrapetyan, Wexler, and Tardos introduced the problem of studying collusion in congestion games. In this work, we show that collusion adds significant complexity to the structure of equilibria in nonatomic routing games, answering an open question posed by Comminetti, Correa, and Steir-Moses (ICALP 2006):

Without collusion, it follows from well-known convexity arguments that equilibria are unique (up to induced latencies). The question is, does this uniqueness continue to hold in the presence of collusion?

We answer no: We show that if collusion is allowed in nonatomic routing games, there may be multiple equilibria. We demonstrate this multiplicity via 2 specific examples. In addition, we show our examples are topologically minimal by giving a complete characterization of network topologies for which, up to induced latencies, unique equilibria exist.

### Sam Greenberg, Amanda Pascoe and Dana Randall. Sampling Biased Lattice Configurations using Exponential Metrics

Abstract: We define a geometric distance function that can be used to show fast mixing of certain natural Markov Chains for biased lattice models, including a reversible tiling model that arises in the context of self-assembly and a coloring model that arises in the context of asynchronous cellular automata. For each of these models, we show that the local Markov chain converges rapidly to the stationary distribution and we believe that couplings based on exponential metrics can be used for many related lattice models.

### Benoît Hudson, Gary Miller, Todd Phillips and Don Sheehy. Size Complexity of Volume Meshes vs. Surface Meshes

Abstract: Typical volume meshes in three dimensions are designed to conform to an underlying two-dimensional surface mesh, with volume mesh element size growing larger away from the surface. The surface mesh may be uniformly spaced or highly graded, and may have fine resolution due to extrinsic mesh size concerns. When we desire that such a mesh have good aspect ratio, we require that some space-filling scaffold vertices be inserted off the surface. We show that under simple preconditions, the number of scaffold vertices will only be linear in the number of surface vertices. We analyze the number of scaffold vertices in a setting that encompasses many existing volume meshing algorithms.

### Yury Lifshits and Shengyu Zhang. Combinatorial Algorithms for Nearest Neighbors, Near-Duplicates and Small-World Design.

Abstract: We study the so called combinatorial framework for algorithmic problems in similarity spaces. Namely, the input dataset is represented by a comparison oracle that given three points x,y,y' answers whether y or y' is closer to x. We assume that the similarity order of the dataset satisfies the four variations of the following disorder inequality: if x is the A'th most similar object to y and y is the B'th most similar object to z, then x is among the D(A+B) most similar objects to z.

Though the oracle gives much less information compared to the standard general metric space model where distance values are given, one can still design very efficient algorithms for various fundamental computational tasks. For nearest neighbor search we present deterministic and exact algorithm with almost linear time and space complexity of preprocessing, and near-logarithmic time complexity of search. Then, for near-duplicate detection we present the first known deterministic algorithm that requires just near-linear time + time proportional to the size of output. Finally, we show that for any dataset satisfying the disorder inequality a visibility graph can be constructed: all out-degrees are near-logarithmic and greedy routing deterministically converges to the nearest neighbor of a target in logarithmic number of steps. The later result is the first known work-around for Navarro's impossibility of generalizing Delaunay graphs.

The technical contribution of the paper consists of handling "false positives" in data structures and an algorithmic technique up-aside-down-filter.