=========================================================================== An Online Scalable Algorithm for Average Flow Time in Broadcast Scheduling --------------------------------------------------------------------------- Authors: Benjamin Moseley (University of Illinois Urbana-Champaign) Sungjin Im (University of Illinois Urbana-Champaign) Topics: Algorithm Analysis, Approximation Algorithms, Online problems, Scheduling and Resource Allocation --------------------------------------------------------------------------- In this paper the online pull-based broadcast model is considered. In this model, there are $n$ pages of data stored at a server and requests arrive for pages online. When the server broadcasts page $p$, all outstanding requests for the same page $p$ are simultaneously satisfied. We consider the problem of minimizing average (total) flow time online where all pages are unit-sized. For this problem, there has been a decade-long search for an online algorithm which is scalable, i.e. $(1+\eps)$-speed $O(1)$-competitive for any fixed $\eps >0$. Before this work, no known online algorithm was a candidate to be scalable. In this paper, we develop a new algorithm for this problem and give the first analysis of an online scalable algorithm. =========================================================================== Probabilistic Analysis of the Semidefinite Relaxation Detector in Digital Communications --------------------------------------------------------------------------- Authors: Anthony Man-Cho So (The Chinese University of Hong Kong) Topics: Algorithm Analysis, Approximation Algorithms, Mathematical Programming, Optimization --------------------------------------------------------------------------- We consider the problem of detecting a vector of symbols that is being transmitted over a fading multiple-input multiple-output (MIMO) channel, where each symbol is an $M$-th root of unity for some fixed $M \ge 2$. Although the symbol vector that minimizes the error probability can be found by the so-called maximum-likelihood (ML) detector, its computation is intractable in general. In this paper we analyze a popular polynomial-time heuristic, called the semidefinite relaxation (SDR) detector, for the problem and establish its first non-asymptotic performance guarantee. Specifically, in the low signal-to-noise ratio (SNR) region, we show that for any $M \ge 2$, the SDR detector will yield a constant factor approximation to the optimal log-likelihood value with a probability that increases exponentially fast to $1$ as the channel size increases. In the high SNR region, it is known that for $M=2$, the SDR detector will yield an exact solution to the ML detection problem with a probability that converges to $1$. We refine this result by establishing the rate of convergence. Our work can be viewed as an average-case analysis of a certain SDP relaxation, and the input distribution we use is motivated by physical considerations. Our results also refine and extend those in previous work, which are all asymptotic in nature and apply only to the problem of detecting binary (i.e. when $M=2$) vectors. In particular, our results can give better insight into the performance of the SDR detector in practical settings. =========================================================================== An Improved Construction of Progression-Free Sets --------------------------------------------------------------------------- Authors: Michael Elkin (Ben-Gurion University of the Negev) Topics: Combinatorics, Geometry, Number Theory --------------------------------------------------------------------------- The problem of constructing dense subsets S of {1,2,..,n} that contain no arithmetic triple was introduced by Erdos and Turan in 1936. They have presented a construction with |S| = Omega(n^{\log_3 2}) elements. Their construction was improved by Salem and Spencer, and further improved by Behrend in 1946. The lower bound of Behrend is |S| = Omega({ n \over {{2^{2 \sqrt{2} \sqrt{\log_2 n}}} \cdot \log^{1/4} n}}). Since then the problem became one of the most central, most fundamental, and most intensively studied problems in additive number theory. Nevertheless, no improvement of the lower bound of Behrend was reported since 1946. In this paper we present a construction that improves the result of Behrend by a factor of Theta(sqrt{log n}), and shows that |S| = Omega({ n \over {{2^{2 \sqrt{2} \sqrt{\log_2 n}}} }} \cdot \log^{1/4} n \right). In particular, our result implies that the construction of Behrend is not optimal. Our construction and proof are elementary and self-contained. Also, the construction can be implemented by an efficient algorithm. Behrend's construction has numerous applications in Theoretical Computer Science. In particular, it is used for fast matrix multiplication, for property testing, and in the area of communication complexity. Plugging in our construction instead of Behrend construction in the matrix multiplication algorithm of Coppersmith and Winograd improves the state-of-the-art upper bound on the complexity of the matrix multiplication by a factor of log^\nu n, for some fixed constant \nu > 0. We also present an application of our technique in Computational Geometry. =========================================================================== Solving the Replacement Paths Problem for Planar Directed Graphs in O(n*log n) Time --------------------------------------------------------------------------- Authors: Christian Wulff-Nilsen (Department of Computer Science, University of Copenhagen) Topics: Algorithm Analysis, Graph Algorithms, Graph Theory, Internet and Network Algorithms, Optimization --------------------------------------------------------------------------- In a graph G with non-negative edge lengths, let P be a shortest path from a vertex s to a vertex t. We consider the problem of computing, for each edge e on P, the length of a shortest path in G from s to t that avoids e. This is known as the replacement paths problem. We give a linear-space algorithm with O(n*log n) running time for n-vertex planar directed graphs. The previous best time bound was O(n*(log n)^2). =========================================================================== Correlation Clustering with Noisy Input --------------------------------------------------------------------------- Authors: Claire Mathieu (Brown University) Warren Schudy (Brown University) Topics: Approximation Algorithms, Graph Algorithms, Mathematical Programming, Optimization, Probability, Random Graphs --------------------------------------------------------------------------- Correlation clustering is a type of clustering that uses a basic form of input data: For every pair of data items, the input specifies whether they are similar (belonging to the same cluster) or dissimilar (belonging to different clusters). This information may be inconsistent, and the goal is to find a clustering (partition of the vertices) that disagrees with as few pieces of information as possible. Correlation clustering is APX-hard for worst-case inputs. We study the following semi-random noisy model to generate the input: start from an arbitrary partition of the vertices into clusters. Then, for each pair of vertices, the similarity information is corrupted (noisy) independently with probability $p$. Finally, an adversary generates the input by choosing similarity/dissimilarity information arbitrarily for each corrupted pair of vertices. In this model, our algorithm produces a clustering with cost at most $1 + O(n^{-1/6})$ times the cost of the optimal clustering, as long as $ p <= 1/2 - n^{-1/3}$. Moreover, if the noise $p$ is small, that is, $p=O(n^{-\epsilon})$, then we can exactly reconstruct all clusters of the planted clustering that have size $\Omega(1/\epsilon)$, and provide a certificate (witness) proving that those clusters are in any optimal clustering. Among other techniques, we use the natural semi-definite programming relaxation followed by an interesting rounding phase. The analysis uses semi-definite programming duality and spectral properties of random matrices. =========================================================================== A Nearly Optimal Algorithm for Approximating Replacement Paths and k Shortest Simple Paths in General Graphs --------------------------------------------------------------------------- Authors: Aaron Bernstein (MIT) Topics: Approximation Algorithms, Graph Algorithms --------------------------------------------------------------------------- \noindent Let $G = (V,E)$ be a directed graph with non-negative edge weights, let $s,t$ be two specified vertices in this graph, and let $\pi(s,t)$ be the shortest path between them. In the \emph{replacement paths} problem we want to compute, for every edge $e$ on $\pi(s,t)$, the shortest path from $s$ to $t$ that avoids $e$. The naive solution to this problem would be to remove each edge $e$, one at a time, and compute the shortest $s-t$ path each time; this yields a running time of $O(mn + n^2\log n)$. Gotthilf and Lewenstein \cite{GL09} recently improved this to $O(mn + n^2\log\log n)$, but no $o(mn)$ algorithms are known. \\ \\ We present the first \emph{approximation} algorithm for replacement paths in weighted, directed graphs. Given any $\eps \in [0, 1)$, our algorithm returns $\oeps$-approximate replacement paths in $O(\eps^{-1}\log^2 n \log(nC/c)(m + n\log n)) = \widetilde{O}(m\log(nC/c)/\eps)$ time, where $C$ is the largest edge weight in the graph and $c$ is the smallest positive weight. \\ \\ We also present an even faster $\oeps$ approximate algorithm for the simpler problem of approximating the $k$ shortest simple $s-t$ paths in a graph. That is, our algorithm outputs $k$ different simple $s-t$ paths, where the kth path we output is a $\oeps$ approximation to the actual kth shortest simple $s-t$ path. The running time of our algorithm is $O(k \eps^{-1} \log^2 n (m + n\log n)) = \wo(km/\eps)$. The fastest \emph{exact} algorithm for this problem has a running time of $O(k(mn + n^2\log\log n)) = \wo(kmn)$ \cite{GL09}. The previous best approximation algorithm was developed by Roditty \cite{R07}; it has a stretch of $3/2$ and a running time of $\wo(km\sqrt{n})$ (it does not work for replacement paths). \\ \\ Note that all of our running times are nearly optimal except for the $O(\log(nC/c))$ factor in the replacement paths algorithm. Also, our algorithm can solve the variant of approximate replacement paths where we avoid vertices instead of edges. =========================================================================== A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics --------------------------------------------------------------------------- Authors: T-H. Hubert Chan (Max-Planck-Institut fuer Informatik) Khaled Elbassioni (Max-Planck-Institut fuer Informatik) Topics: Algorithm Analysis, Approximation Algorithms, Optimization --------------------------------------------------------------------------- We consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find a shortest tour that visits each of a collection of $n$ subsets (regions or neighborhoods) in the underlying metric space. We give a QPTAS when the regions are what we call $\alpha$-fat weakly disjoint. This notion combines the existing notions of diameter variation, fatness and disjointness for geometric objects and generalizes these notions to any arbitrary metric space. Intuitively, the regions can be grouped into a bounded number of types, where in each type, the regions have similar upper bounds for their diameters, and each such region can designate a point such that these points are far away from one another. Our result generalizes the PTAS for TSPN on the Euclidean plane by Mitchell~\cite{M07} and the QPTAS for TSP on doubling metrics by Talwar~\cite{Tal04}. We also observe that our techniques directly extend to a QPTAS for the Group Steiner Tree Problem on doubling metrics, with the same assumption on the groups. =========================================================================== A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing. --------------------------------------------------------------------------- Authors: Aparna Das (Brown University) Claire Mathieu (Brown University) Topics: Approximation Algorithms, Graph Algorithms --------------------------------------------------------------------------- In the capacitated vehicle routing problem, introduced by Dantzig and Ramser in 1959, we are given the locations of n customers and a depot, along with a vehicle of capacity k, and wish to find a minimum length collection of tours, each starting from the depot and visiting at most k customers, whose union covers all the customers. We give a quasi-polynomial time approximation scheme for the setting where the customers and the depot are on the plane, and distances are given by the Euclidean metric. =========================================================================== Fully-Functional Succinct Trees --------------------------------------------------------------------------- Authors: Kunihiko Sadakane (National Institute of Informatics) Gonzalo Navarro (University of Chile) Topics: Compression, Data Structures --------------------------------------------------------------------------- We propose new succinct representations of ordinal trees, which have been studied extensively. It is known that any $n$-node static tree can be represented in $2n + o(n)$ bits and various operations on the tree can be supported in constant time under the word-RAM model. However existing data structures are not satisfactory in both theory and practice because (1) the lower-order term is $\Omega(n \log\log n/\log n)$ and cannot be neglected, (2) the hidden constant is also large, and (3) the data structures are complicated and difficult to be implemented. We propose a simple and flexible data structure, called the range min-max tree, that reduces the large number of relevant tree operations considered in the literature, to a few primitives that are carried out in constant time on sufficiently small trees. The result is extended to trees of arbitrary size, achieving $2n + O(n /\polylog(n))$ bits of space. The redundancy is significantly lower than any previous proposal, and the data structure is easily implemented. =========================================================================== Online Learning with Queries --------------------------------------------------------------------------- Authors: Chao-Kai Chiang (Academia Sinica) Chi-Jen Lu (Academia Sinica) Topics: Learning, Online problems, Probability --------------------------------------------------------------------------- In the standard online learning problem, a player has to iteratively choose an action before knowing anything about the corresponding loss. However, there are situations in which it seems possible for the player to spend some effort or resources to collect some prior information before her action. This motivates us to study a variant of the online learning problem, in which the player is allowed to query $B$ bits from the loss vector in each iteration before choosing her action. We provide an algorithm for this problem. Suppose each loss value is represented by $K$ bits and distinct loss values differ by at least $\delta$, and suppose there are $N$ actions to choose and $T$ rounds to play. Then our algorithm achieves a regret of the following form. Before $B$ approaching $B_1 = NK/2$, the regret stays at $O(\sqrt{T \ln N})$, and after $B$ exceeding $B_1$ but before approaching $B_2 = NK/2 + 3K - 1$, the regret drops slightly to $O(\sqrt{(T\ln N)/N})$, while after $B$ exceeding $B_2$, the regret takes a dramatic drop to $(N\ln N)/\delta$. Our algorithm is in fact close to optimal as we also provide a regret lower bound which almost matches the regret upper bound achieved by the algorithm. =========================================================================== On the Exact Space Complexity of Sketching and Streaming Small Norms --------------------------------------------------------------------------- Authors: Daniel M. Kane (Harvard University) Jelani Nelson (MIT) David P. Woodruff (IBM Almaden) Topics: Streaming Algorithms --------------------------------------------------------------------------- We settle the 1-pass space complexity of (1+eps)-approximating the Lp norm, for real p with 1 <= p <= 2, of a length-n vector updated in a length-m stream with updates to its coordinates. We assume the updates are integers in the range [-M, M]. In particular, we show the space required is Theta(eps^{-2}*log(mM) + loglog(n)) bits. Our result also holds for 0 < p < 1; although Lp is not a norm in this case, it remains a well-defined function. Our upper bound improves upon previous algorithms of [Indyk, JACM '06] and [Li, SODA '08]. This improvement comes from showing an improved derandomization of the Lp sketch of Indyk by using k-wise independence for small k, as opposed to using the heavy hammer of a generic pseudorandom generator against space-bounded computation such as Nisan's PRG. Our lower bound improves upon previous work of [Alon-Matias-Szegedy, JCSS '99] and [Woodruff, SODA '04], and is based on showing a direct sum property for the 1-way communication of the gap-Hamming problem. =========================================================================== Hardness Results of Homology Localization --------------------------------------------------------------------------- Authors: Chao Chen (Rensselaer Polytechnic Institute) Daniel Freedman (Rensselaer Polytechnic Institute and Hewlett-Packard Laboratories, Israel) Topics: Geometry, Topological Problems --------------------------------------------------------------------------- We address the problem of localizing homology classes, namely, finding the cycle representing a given class with the most concise geometric measure. We focus on the volume measure, that is, the 1-norm of a cycle. Two main results are presented. First, we prove the problem is NP-hard to approximate within any constant factor. Second, we prove that for homology of 2-dimension or higher, the problem is NP-hard to approximate even when the Betti number is $O(1)$. A side effect is the inapproximability of the problem of computing the nonbounding cycle with the smallest volume, and computing cycles representing a homology basis with the minimal total volume. We also discuss other geometric measures (diameter and radius) and show their disadvantages in homology localization. =========================================================================== Towards a calculus for non-linear spectral gaps --------------------------------------------------------------------------- Authors: Manor Mendel (The Open University of Israel) Assaf Naor (Courant Institute) Topics: Geometry, Graph Theory, Metric Embeddings --------------------------------------------------------------------------- Given a finite regular graph G=(V,E) and a metric space (X,d_X) let \gamma_+(G,X) denote the smallest constant \gamma_+ such that for all f,g:V\to X we have: \frac{1}{|V|^2}\sum_{x,y\in V} d_X(f(x),g(y))^2\le \frac{\gamma_+}{|E|} \sum_{xy\in E} d_X(f(x),g(y))^2. In the special case X=R this quantity coincides with the reciprocal of the absolute spectral gap of G, but for other geometries the parameter \gamma_+(G,X), which we still think of as measuring the non-linear spectral gap of G with respect to X (even though there is no actual spectrum present here), can behave very differently. Non-linear spectral gaps arise often in the theory of metric embeddings, and in the present paper we systematically study the theory of non-linear spectral gaps, partially in order to obtain a combinatorial construction of ``super-expanders". Super-expanders are bounded-degree graph families which have a non-linear spectral gap with respect to every uniformly convex normed space (note that since any normed space contains a copy of the line R, super-expanders are automatically also expanders in the traditional sense). Such remarkable graph families were previously known to exist due to a tour de force algebraic construction of Lafforgue, who studied them in order to show that there exist families of bounded degree graphs which do not admit a coarse embedding into any uniformly convex Banach space. Our construction is different and combinatorial, and it highlights the fact that ideas developed by computer scientists, specifically the zig-zag construction of Reingold-Vadhan-Wigderson, are inherently non-linear, and can be used to obtain geometric results, in addition to their well-known remarkable combinatorial and and algorithmic applications. We show that non-linear spectral graphs behave sub-multiplicatively under zig-zag products---a fact which ammounts to a simple iteration of the inequality above. This yields as a special case a very simple (linear algebra free) proof of the Reingold-Vadhan-Wigderson theorem which states that zig-zag products preserve the property of having an absolute spectral gap (with quantitative control on the size of the gap). The zig-zag iteration of Reingold-Vadhan-Wigderson also involves taking graph powers, which is trivial to analyze in the classical ``linear" setting. In our work, the behavior of non-linear spectral gaps under graph powers becomes a major geometric obstacle, and we show that for uniformly convex normed spaces there exists a satisfactory substitute for spectral calculus which makes sense in the non-linear setting. These facts, in conjunction with a variant of Ball's notion of Markov cotype, and a Fourier analytic proof of the existence of appropriate ``base graphs", are shown to imply that Reingold-Vadhan-Wigderson type constructions can be carried out in the non-linear setting to obtain new constructions of super-expanders. =========================================================================== Paired Approximation Problems and Incompatible Inapproximabilities --------------------------------------------------------------------------- Authors: David Eppstein (University of California, Irvine) Topics: Algorithm Analysis, Approximation Algorithms, Complexity, Graph Algorithms --------------------------------------------------------------------------- This paper considers pairs of optimization problems that are defined from a single input and for which it is desired to find a good approximation to either one of the problems. In many instances, it is possible to efficiently find an approximation of this type that is better than known inapproximability lower bounds for either of the two individual optimization problems forming the pair. In particular, we find either a $(1+\epsilon)$-approximation to $(1,2)$-TSP or a $1/\epsilon$-approximation to maximum independent set, from a given graph, in linear time. We show a similar paired approximation result for finding either a coloring or a long path. However, no such tradeoff exists in some other cases: for set cover and hitting set problems defined from a single set family, and for clique and independent set problems on the same graph, it is not possible to find an approximation when both problems are combined that is better than the best approximation for either problem on its own. =========================================================================== Solving Simple Stochastic Tail Games --------------------------------------------------------------------------- Authors: Hugo Gimbert (CNRS, LaBRI, Bordeaux) Florian Horn (IST Austria, Wien) Topics: Complexity, Game Theory, Markov Chains, Probability --------------------------------------------------------------------------- Stochastic games are a natural model for open reactive processes: one player represents the controller and his opponent represents a hostile environment. The evolution of the system depends on the decisions of the players, supplemented by random transitions. There are two main algorithmic problems on such games: computing the values (quantitative analysis) and deciding whether a player can win with probability $1$ (qualitative analysis). In this paper we reduce the quantitative analysis to the qualitative analysis: we provide an algorithm for computing values which uses qualitative analysis as a sub-procedure. The correctness proof of this algorithm reveals several nice properties of perfect-information stochastic tail games, in particular the existence of optimal strategies. We apply these results to games whose winning conditions are boolean combinations of mean-payoff and Büchi conditions. =========================================================================== On the Cell Probe Complexity of Dynamic Membership --------------------------------------------------------------------------- Authors: KE YI (Hong Kong University of Science and Technology) QIN ZHANG (Hong Kong University of Science and Technology) Topics: Data Structures --------------------------------------------------------------------------- We consider the dynamic membership problem, one of the most fundamental data structure problems, in the cell probe model with an arbitrary cell size. We consider a cell probe model equipped with a cache that consists of at least a constant number of cells; reading or writing the cache is free of charge. It is known that the availability of a cache could significantly lower the amortized update cost to $o(1)$, for nearly all common data structures. In this paper, we show that for any deterministic membership data structure under a random input sequence, if we require that at any time, the expected average query cost is no more than $1 + \delta$ for some small constant $\delta$, then the expected amortized update cost must be at least $\Omega(1)$, namely, the cache is essentially useless. This tradeoff turns out to be irrelevant to the space the data structure uses. We also extend this lower bound to randomized data structures, by using a minimax principle tailored for dynamic data structures, which might be of independent interests. =========================================================================== The $1+\beta$ Choice Process and Weighted Balls-into-Bins --------------------------------------------------------------------------- Authors: Yuval Peres (Microsoft Research - Redmond) Kunal Talwar (Microsoft Research - SVC) Udi Wieder (Microsoft Research - SVC) Topics: Markov Chains, Probability, Scheduling and Resource Allocation --------------------------------------------------------------------------- Suppose $m$ balls are sequentially thrown into $n$ bins where each ball goes into a random bin. It is well-known that the gap between the load of the most loaded bin and the average is $\Theta(\sqrt{\frac{m\log n}{n}})$, for large $m$. If each ball goes to the lesser loaded of two random bins, this gap dramatically reduces to $\Theta(\log\log n)$ independent of $m$. Consider now the following ``$(1+\beta)$-choice'' process for some parameter $\beta \in (0,1)$: each ball goes to a random bin with probability $(1-\beta)$ and the lesser loaded of two random bins with probability $\beta$. {\em How does the gap for such a process behave?} Suppose that the weight of each ball was drawn from a geometric distribution. {\em How is the gap (now defined in terms of weight) affected?} In this work, we develop general techniques for analyzing such balls-into-bins processes. Specifically, we show that for the $(1+\beta)$-choice process above, the gap is $\Theta(\log n/\beta)$, irrespective of $m$. Moreover the gap stays at $\Theta(\log n/\beta)$ in the weighted case for a large class of weight distributions. No non-trivial explicit bounds were previously known in the weighted case, even for the 2-choice paradigm. =========================================================================== Basis Reduction, and the Complexity of Branch-and-Bound --------------------------------------------------------------------------- Authors: Gabor Pataki (UNC Chapel Hill) Mustafa Tural (UNC Chapel Hill) Topics: Mathematical Programming, Optimization --------------------------------------------------------------------------- The classical branch-and-bound algorithm for the integer feasibility problem \begin{equation} \label{ip0} \text{Find} \, x \in Q \cap \zad{n}, \,\, \text{with} \,\, Q = \left\{ \, x \, | \, \begin{pmatrix} \ell_1 \\ \ell_2 \end{pmatrix} \, \leq \, \begin{pmatrix} A \\ I \end{pmatrix} \leq \begin{pmatrix} w_1 \\ w_2 \end{pmatrix} \right\} \eeq has exponential worst case complexity. We prove that it is surprisingly efficient on reformulations of (\ref{ip0}), in which the columns of the constraint matrix are short, and near orthogonal, i.e. a reduced basis of the generated lattice. The analysis builds on Furst and Kannan's work on the subset sum problem. It also uses an upper bound on the size of the branch-and-bound tree which depends on the norms of the Gram-Schmidt vectors of the constraint matrix. We show that when the entries of $A$ are from $\{1, \dots, M\}$ for a large enough $M$, branch-and-bound solves almost all reformulated instances at the rootnode, and explore practical aspects of this result. We compute numerical values of $M$ which guarantee that $90$, and $99$ percent of the reformulated problems solve at the root: these turn out to be surprisingly small when the problem size is moderate. A computational study also confirms that random integer programs become easier, as the coefficients grow. =========================================================================== Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface --------------------------------------------------------------------------- Authors: Petr Hlineny (FI MU Brno) Markus Chimani (TU Dortmund) Topics: Approximation Algorithms, Graph Algorithms, Graph Theory, Topological Problems --------------------------------------------------------------------------- We provide an $O(n\log n)$ time constant factor approximation algorithm for the crossing number of a graph of bounded maximum degree which is ``densely enough'' embeddable on any fixed orientable surface. Our approach combines some known tools with a powerful new lower bound on the crossing number of an embedded graph. This result extends previous results that gave such approximations in particular cases of projective, toroidal or apex graphs; it is a qualitative improvement over previously published algorithms that constructed low-crossing-number drawings of embeddable graphs without giving any approximation guarantees. No constant factor approximation algorithms for the crossing number problem over comparably rich classes of graphs are known to date. =========================================================================== Testing Planarity of Partially Embedded Graphs --------------------------------------------------------------------------- Authors: Patrizio Angelini (University Rome 3, Italy) Giuseppe Di Battista (University Rome 3, Italy) Fabrizio Frati (University Rome 3, Italy) Vit Jelinek (Charles University, Prague, Czech republic) Jan Kratochvil (Charles University, Prague, Czech republic) Maurizio Patrignani (University Rome 3, Italy) Ignaz Rutter (Karlsruhe University, Germany) Topics: Algorithm Analysis, Complexity, Graph Algorithms, Graph Theory, Metric Embeddings --------------------------------------------------------------------------- We study the following problem: Given a planar graph $G$ and a planar drawing (embedding) of a subgraph of $G$, can such a drawing be extended to a planar drawing of the entire graph $G$? This problem fits the paradigm of extending a partial solution to a complete one, which has been studied before in many different settings. Unlike many cases, when the presence of a partial solution in the input makes an otherwise easy problem hard, we show that the planarity question remains polynomial-time solvable. Our algorithm is based on several combinatorial lemmata which show that the planarity of partially embedded graphs meets the ``oncas'' behaviour -- obvious necessary conditions for planarity are also sufficient. These conditions are expressed in terms of the interplay between (a) rotation schemes and containment relationships between cycles and (b) the decomposition of a graph into its connected, biconnected and triconnected components. This implies that no dynamic programming is needed for a decision algorithm and that the elements of the decomposition can be processed independently. Further, by equipping the components of the decomposition with suitable data structures and by carefully splitting the problem into simpler subproblems, we improve our algorithm to reach linear-time complexity. Finally, we consider several generalizations of the problem, e.g.\ minimizing the number of edges of the partial embedding that need to be rerouted, and argue that they already become NP-hard. Also, we show how our algorithm can be applied to solve related Graph Drawing problems. =========================================================================== Solving MAX-2-SAT Above a Tight Lower Bound --------------------------------------------------------------------------- Authors: Gregory Gutin (University of London, UK) Eun Jung Kim (University of London, UK) Stefan Szeider (University of Durham, UK) Anders Yeo (University of London, UK) Topics: Algorithm Analysis, Graph Algorithms, Optimization --------------------------------------------------------------------------- We present an exact algorithm that decides in time $m^{O(1)} + 2^{O(k^2)}$ whether a given set of $m$ binary clauses admits a truth assignment that satisfies at least $(3m+k)/4$ clauses. Thus MAX-2-SAT is fixed-parameter tractable when parameterized above the tight lower bound $3m/4$. Our algorithm is based on a polynomial-time data reduction procedure that reduces a problem instance to an equivalent one with $O(k^2)$ variables. =========================================================================== Rumour spreading and graph conductance --------------------------------------------------------------------------- Authors: Flavio Chierichetti (Sapienza University, Roma, Italy) Silvio Lattanzi (Sapienza University, Roma, Italy) Alessandro Panconesi (Sapienza University, Roma, Italy) Topics: Algorithm Analysis, Distributed and Parallel Computing, Graph Algorithms, Internet and Network Algorithms, Probability --------------------------------------------------------------------------- We show that if a connected graph has conductance C then rumour spreading, also known as randomized broadcast, succesfully broadcasts a message within O(polylog(N)/C^3) many steps, with high probability (N is the number of nodes in the network). An interesting feature of our approach is that it draws a connection with the spectral sparsification procedure of Spielman and Teng. =========================================================================== VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension --------------------------------------------------------------------------- Authors: Elchanan Mossel (Weizmann Institute & UC Berkeley) Christos Papadimitriou (UC Berkeley) Michael Schapira (Yale University & UC Berkeley) Yaron Singer (UB Berkeley) Topics: Combinatorics, Mechanism Design --------------------------------------------------------------------------- The existence of incentive-compatible computationally-efficient protocols for combinatorial auctions with decent approximation ratios is the paradigmatic problem in computational mechanism design. It is believed that in many cases good approximations for combinatorial auctions may be unattainable due to an inherent clash between truthfulness and computational efficiency. However, to date, \emph{researchers lack the machinery to prove such results}. In this paper, we present a new approach: We take the first steps towards the development of new technologies for lower bounding the \emph{VC-dimension of $k$-tuples of disjoint sets}. We apply this machinery to prove the first \emph{computational-complexity} inapproximability results for incentive-compatible mechanisms for combinatorial auctions. These results hold for the important class of VCG-based mechanisms, and are based on the complexity assumption that NP has no polynomial-size circuits. We believe that our approach holds great promise. Indeed, subsequently to our work, Buchfuhrer and Umans, and, independently, Dughmi \emph{et al.}, strengthened our results via extensions of our techniques, thus proving conjectures we presented in an earlier version of this paper. =========================================================================== Asymmetric Traveling Salesman Path and Directed Latency Problems --------------------------------------------------------------------------- Authors: Zachary Friggstad (University of Alberta) Mohammad R. Salavatipour (University of Alberta) Zoya Svitkina (University of Alberta) Topics: Algorithm Analysis, Approximation Algorithms, Graph Algorithms, Mathematical Programming, Optimization --------------------------------------------------------------------------- We study integrality gaps and approximability of two closely related problems on directed graphs. Given a set V of n nodes in an underlying asymmetric metric d and two specified nodes s and t, both problems ask to find an s-t path visiting all other nodes. In the asymmetric traveling salesman path problem (ATSPP), the objective is to minimize the total cost of this path. In the directed latency problem, the objective is to minimize the sum of distances on this path from s to each node. Both of these problems are NP-hard. The best known approximation algorithms for ATSPP have ratios O(log n), but only a bound of O(sqrt(n)) for the integrality gap of its linear programming relaxation has been known. For directed latency, the best previously known approximation algorithm has a guarantee of O(n^(1/2+epsilon)), for any constant epsilon>0. We present a new algorithm for the ATSPP problem that has approximation ratio of O(log n), matching the best known ones, but whose analysis also bounds the integrality gap of the LP relaxation of ATSPP by the same factor. This solves an open problem posed by Chekuri and Pal (2007). We then pursue a deeper study of this LP and its variations and their use in approximating directed latency. Our second major result is an O(log n)-approximation to the directed latency problem. This also places an O(log n) bound on the integrality gap of a new LP relaxation of the latency problem that we introduce. We note that this is essentially the best possible ratio unless an asymptotically better approximation exists for the well-studied asymmetric traveling salesman tour problem. =========================================================================== Data Structures for Range Minimum Queries in Multidimensional Arrays --------------------------------------------------------------------------- Authors: Hao Yuan (Purdue University) Mikhail J. Atallah (Purdue University) Topics: Algorithm Analysis, Data Structures, Geometry, Pattern Matching --------------------------------------------------------------------------- Given a d-dimensional array A with N entries, the Range Minimum Query (RMQ) asks for the minimum element within a contiguous subarray of A. The 1D RMQ problem has been studied intensively because of its relevance to the Nearest Common Ancestor problem and its important use in stringology. If constant-time query answering is required, linear time and space preprocessing algorithms were known for the 1D case, but not for the higher dimensional cases. In this paper, we give the first linear-time preprocessing algorithm for arrays with fixed dimension, such that any range minimum query can be answered in constant time. This improves the preprocessing time over all previous work under the same model, i.e., RAM with logarithmic word size. =========================================================================== Incentive Compatible Budget Elicitation in Multi-unit Auctions --------------------------------------------------------------------------- Authors: Sayan Bhattacharya (Duke University) Vincent Conitzer (Duke University) Kamesh Munagala (Duke University) Lirong Xia (Duke University) Topics: Economics, Mechanism Design --------------------------------------------------------------------------- In this paper, we consider the problem of designing incentive compatible auctions for multiple (homogeneous) units of a good, when bidders have private valuations and private budget constraints. When only the valuations are private and the budgets are public, Dobzinski et al show that the adaptive clinching auction is the unique incentive-compatible auction achieving Pareto-optimality. They further show that this auction is not truthful with private budgets, so that there is no deterministic Pareto-optimal auction with private budgets. Our main contribution is to show the following Budget Monotonicity property of this auction: When there is only one infinitely divisible good, a bidder cannot improve her utility by reporting a budget smaller than the truth. This implies that the adaptive clinching auction is incentive compatible when over-reporting the budget is not possible (for instance, when funds must be shown upfront). We can also make reporting larger budgets suboptimal with a small randomized modification to the auction. In either case, this makes the modified auction Pareto-optimal with private budgets. We also show that the Budget Monotonicity property does not hold for auctioning indivisible units of the good, showing a sharp contrast between the divisible and indivisible cases. The Budget Monotonicity property also implies other improved results in this context. For revenue maximization, the same auction improves the best-known competitive ratio due to Abrams by a factor of 4, and asymptotically approaches the performance of the optimal single-price auction. Finally, we consider the problem of revenue maximization (or social welfare) in a Bayesian setting. We allow the bidders have public size constraints (on the amount of good they are willing to buy) in addition to private budget constraints. We show a simple poly-time computable 5.83-approximation to the optimal Bayesian incentive compatible mechanism, that is implementable in dominant strategies. Our technique again crucially needs the ability to prevent bidders from over-reporting budgets via randomization. We show the approximation result via designing a rounding scheme for an LP relaxation of the problem, which may be of independent interest. =========================================================================== Sharp kernel clustering algorithms and their associated Grothendieck inequalities --------------------------------------------------------------------------- Authors: Subhash Khot (Courant Institute) Assaf Naor (Courant Institute) Topics: Algorithm Analysis, Approximation Algorithms, Complexity, Geometry, Learning, Optimization --------------------------------------------------------------------------- In the kernel clustering problem we are given a (large) $n\times n$ symmetric positive semidefinite matrix $A=(a_{ij})$ with $\sum_{i=1}^n\sum_{j=1}^n a_{ij}=0$ and a (small) $k\times k$ symmetric positive semidefinite matrix $B=(b_{ij})$. The goal is to find a partition $\{S_1,\ldots,S_k\}$ of $\{1,\ldots n\}$ which maximizes $ \sum_{i=1}^k\sum_{j=1}^k \left(\sum_{(p,q)\in S_i\times S_j}a_{pq}\right)b_{ij}$. We design a polynomial time approximation algorithm that achieves an approximation ratio of $\frac{R(B)^2}{C(B)}$, where $R(B)$ and $C(B)$ are geometric parameters that depend only on the matrix $B$, defined as follows: if $b_{ij} = \langle v_i, v_j \rangle$ is the Gram matrix representation of $B$ for some $v_1,\ldots,v_k\in \R^k$ then $R(B)$ is the minimum radius of a Euclidean ball containing the points $\{v_1, \ldots, v_k\}$. The parameter $C(B)$ is defined as the maximum over all measurable partitions $\{A_1,\ldots,A_k\}$ of $\R^{k-1}$ of the quantity $\sum_{i=1}^k\sum_{j=1}^k b_{ij}\langle z_i,z_j\rangle$, where for $i\in \{1,\ldots,k\}$ the vector $z_i\in \R^{k-1}$ is the Gaussian moment of $A_i$, i.e., $z_i=\frac{1}{(2\pi)^{(k-1)/2}}\int_{A_i}xe^{-\|x\|_2^2/2}dx$. We also show that for every $\eps > 0$, achieving an approximation guarantee of $(1-\e)\frac{R(B)^2}{C(B)}$ is Unique Games hard. =========================================================================== On the Optimality of Spiral Search --------------------------------------------------------------------------- Authors: Elmar Langetepe (University of Bonn, Institute of Computer Science I) Topics: Algorithm Analysis, Combinatorics, Complexity, Geometry, Online problems --------------------------------------------------------------------------- Searching for a point in the plane is a well-known search game problem introduced in the early eigthies. The best known search strategy is given by a spiral and achieves a \emph{competitive ratio} of $17.289\ldots$ It was shown by Gal \cite{g-sg-80} that this strategy is the best strategy among all \emph{monotone} and \emph{periodic} strategies. Since then it was unknown whether the given strategy is optimal in general. This paper settles this old open fundamental search problem and shows that spiral search is indeed optimal. The given problem can be considered as the continous version of the well-known $m$-ray search problem and also appears in several non-geometric applications and modifications. Therefore the optimality of spiral search is an important questions considered by many researchers in the last decades. We answer the logarithmic spiral conjecture for the given problem. The lower bound construction might be helpful for similar settings, it also simplifies existing proofs on classical $m$-ray search. =========================================================================== Cell-probe lower bounds for prefix sums and matching brackets --------------------------------------------------------------------------- Authors: Emanuele Viola (Northeastern University) Topics: Combinatorics, Complexity, Data Structures, Databases and Information Retrieval --------------------------------------------------------------------------- We prove that to store n bits x0... x1 so that each prefix sum (a.k.a. rank) query Sum(i) := {k < i} xk can be answered by non-adaptively probing q cells of lg n bits, one needs memory n + n/log^O(q) n: This matches a recent upper bound of n+n/log (q) n by Patrascu (FOCS 2008), also non-adaptive. We also obtain a log |bal| + n/log^{2^{O(q)}} n$ lower bound for storing strings of balanced brackets x in Bal \subseteq {0,1}^n so that matching-bracket queries can be answered by non-adaptively probing q cells. To obtain these bounds we show that a too efficient data structure allows us to break the correlations between query answers. =========================================================================== The focus of attention problem --------------------------------------------------------------------------- Authors: Dries Goossens (KULeuven) Sergey Polyakovskiy (KULeuven) Frits Spieksma (KULeuven) Gerhard Woeginger (Eindhoven University of Technology) Topics: Algorithm Analysis, Complexity, Optimization --------------------------------------------------------------------------- Motivated by applications in the area of sensor networks, Isler, Khanna, Spletzer and Taylor (2005) discuss an algorithmic problem where 2n cameras have to be assigned in disjoint pairs to n targets. The cameras are located on a straight line, whereas the targets are somewhere in the plane. They assume that the 2n cameras are positioned on the x-axis, in the 2n points with coordinates (x(i), 0) with 1 <= i <= n. They discuss an error measure motivated by stereo reconstruction that mainly depends on the y-coordinates y(1),..., y(n) of the n targets: If the i-th and the j-th camera together are assigned to the k-th target, then the corresponding incurred error cost is c(ijk) = y(k)/(|x(i)-x(j)|). The objective is to find an assignment of camera pairs to targets such that the sum of all error costs c(ijk) is minimized. Our results We will investigate a generalization of this cost structure that is based on a real parameter p. An instance of problem p-FOA is specified by 2n real numbers x(1),...,x(2n) and by n real numbers y(1),...,y(n). The corresponding cost-coefficient for matching x(i) and x(j) with y(k) is c(ijk) = y(k)/(|x_i-x_j|^p). The goal is to find an assignment that minimizes the sum of all costs. We provide a complete complexity classification of problem p-FOA: *) For every real p with -1 <= p <= 0, problem p-FOA is polynomially solvable. *) For every real p with p < -1 or p > 0, problem p-FOA is strongly NP-hard. *) Even the special case with equi-distant cameras is strongly NP-hard. This settles a question left open in Isler et al. (2005). As our main contribution, we fully resolve the approximability status of p-FOA: *) For every real p, problem p-FOA possesses a PTAS. Our PTAS extends the results and ideas of Isler et al. (2005) for the equi-distant special case. The design of our PTAS is quite intricate, and introduces a number of new ideas to the area. Reference: V. Isler, S. Khanna, J.R. Spletzer, C.J. Taylor (2005). Target tracking with distributed sensors: The focus of attention problem. Computer Vision and Image Understanding 100, 225--247. =========================================================================== A locality-sensitive hash for real vectors --------------------------------------------------------------------------- Authors: Tyler Neylon (Bynomial, Inc.) Topics: Approximation Algorithms, Databases and Information Retrieval, Geometry, Optimization --------------------------------------------------------------------------- We present a simple and practical algorithm for the $c-$approximate near neighbor problem ($c-$NN): given $n$ points $P\subset\R^d$ and radius $R$, build a data structure which, given $q\in\R^d$, can with probability $1-\delta$ return a point $p\in P$ with $\mathsf{dist}(p,q)\le cR$ if there is any $p^*\in P$ with $\mathsf{dist}(p^*,q)\le R$. For $c=d+1$, our algorithm deterministically ($\delta=0$) preprocesses in time $O(nd\log d)$, space $O(dn)$, and answers queries in expected time $O(d^2)$; this is the first known algorithm to deterministically guarantee an $O(d)-$NN solution in constant time with respect to $n$ for all $\ell_p$ metrics. A probabilistic version empirically achieves useful $c$ values ($c < 2$) where $c$ appears to grow minimally as $d\to\infty$. A query time of $O(d\log d)$ is available, providing slightly less accuracy. These techniques can also be used to approximately find (pointers between) all pairs $x,y\in P$ with $\mathsf{dist}(x,y) \le R$ in time $O(nd\log d)$. The key to the algorithm is a locality-sensitive hash: a mapping $h:\R^d\to U$ with the property that $h(x) = h(y)$ is much more likely for nearby $x,y$. We introduce a somewhat regular simplex which tessellates $\R^d$, and efficiently hash each point in any simplex of this tessellation to all $d+1$ corners; any points in neighboring cells will be hashed to a shared corner and noticed as nearby points. This method is completely independent of dimension reduction, so that additional space and time savings are available by first reducing all input vectors. =========================================================================== On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second Order Logic --------------------------------------------------------------------------- Authors: Stephan Kreutzer (University of Oxford) Siamak Tazari (Humboldt Universität zu Berlin) Topics: Approximation Algorithms, Complexity, Graph Algorithms, Graph Theory --------------------------------------------------------------------------- Brambles were introduced as the dual notion to treewidth, one of the most central concepts of the graph minor theory of Robertson and Seymour. Recently, Grohe and Marx showed that there are graphs G, in which every bramble of order larger than the square root of the treewidth is of exponential size in the size of G. On the positive side, they show the existence of polynomial-sized brambles of the order of the square root of the treewidth, up to log factors. We provide the first polynomial time algorithm to construct a bramble in general graphs and achieve this bound, up to log-factors. We use this algorithm to construct grid-like minors, a replacement structure for grid-minors recently introduced by Reed and Wood, in polynomial time. Using the grid-like minors, we introduce the notion of a perfect bramble and an algorithm to find one in polynomial time. Perfect brambles are brambles with a particularly simple structure and they also provide us with a subgraph that has bounded degree and still large treewidth; we use them to obtain a meta-theorem on deciding certain parameterized subgraph-closed problems on general graphs in time singly exponential in the parameter; the only other result with a similar flavor that is known to us is due to Demaine and Hajiaghayi and obtains a doubly-exponential bound on the parameter (albeit, for a more general class of parameterized problems). The second part of our work deals with providing a lower bound to Courcelle's famous theorem from almost two decades ago, stating that every graph property that can be expressed by a sentence in monadic second-order logic (MSO), can be decided by a linear time algorithm on classes of graphs of bounded treewidth. Whereas much work has been done on designing, improving, and applying algorithms on graphs of bounded treewidth, not much is known on the side of lower bounds: what bound on the treewidth of a class of graphs "forbids" polynomial-time parameterized algorithms to decide MSO-sentences? This question has only recently received attention with the first systematic study appearing in [Kreutzer 2009]. Using our results from the first part of our work we can improve on it significantly and establish a strong lower bound for Courcelle's theorem on classes of colored graphs. =========================================================================== Compact Ancestry Labeling Schemes for XML Trees --------------------------------------------------------------------------- Authors: Fraigniaud Pierre (CNRS and University Paris Diderot) Korman Amos (CNRS and University Paris Diderot) Topics: Combinatorics, Data Structures, Databases and Information Retrieval --------------------------------------------------------------------------- An ancestry labeling scheme labels the nodes of any tree in such a way that ancestry queries between any two nodes can be answered just by looking at their corresponding labels. The common measure to evaluate the quality of an ancestry scheme is by its label size, that is the maximum number of bits stored in a label, taken over all n-node trees. The design of ancestry labeling schemes finds applications in XML search engines. In these contexts, even small improvements in the label size are important. In fact, the literature about this topic is interested in the exact label size rather than just its order of magnitude. As a result, following the proposal of a simple interval based ancestry scheme with label size 2 log n bits (Kannan et al., SIDMA 92), a considerable amount of work was devoted to improve the bound on the label size. The current state of the art upper bound is log n + O(sqrt{log n}) bits (Abiteboul et al., SICOMP 06) which is still far from the known log n + Omega(loglog n) lower bound (Alstrup et al., SODA 03). Moreover, the hidden constant factor in the additive O(sqrt{log n}) term is large, which makes that scheme less efficient than the simple interval based scheme for typical current XML trees. It is for this reason that Kaplan et al. suggested other ancestry schemes which, on average, use labels whose size, for typical XML data, is smaller by about 10%-30% than the ones used for the interval based scheme (SODA 02). Motivated by the fact that typical XML trees have extremely small depth, this paper parameterizes the quality measure of an ancestry scheme not only by the number of nodes in the given tree but also by its depth. Our main result is the construction of an ancestry scheme that labels n-node trees of depth d with labels of size log n+2 log d +O(1). This result is essentially optimal for trees of constant depth which is in fact the typical case in real XML data. In addition to our main result, we prove a result that may be of independent interest concerning the existence of a universal graph of linear size for the family of constant depth trees. This result improves the best known bound of 2^{O(log^*n)} n (Alstrup and Rauhe, FOCS 02) on the size of such a universal graph (the latter bound, however, holds for a universal graph for the family of all n-node trees). =========================================================================== The forest hiding problem --------------------------------------------------------------------------- Authors: Adrian Dumitrescu (University of Wisconsin-Milwaukee) Minghui Jiang (Utah State University) Topics: Geometry --------------------------------------------------------------------------- Let $\Omega$ be a disk of radius $R$ in the plane. A set $F$ of closed unit disks contained in $\Omega$ forms a maximal packing if the unit disks are pairwise disjoint and the set is maximal: i.e., it is not possible to add another disk to $F$ while maintaining the packing property. A point $p$ is hidden within the ``forest'' defined by $F$ if any ray with apex $p$ intersects some disk of $F$: that is, a person standing at $p$ can hide without being seen from outside the forest. We show that if the radius $R$ of $\Omega$ is large enough, one can find a hidden point for any maximal packing of unit disks in $\Omega$. This proves a conjecture of Joseph~Mitchell. We also present an $O(n^{5/2} \log n)$-time algorithm that, given a forest with $n$ (not necessarily congruent) disks, computes the boundary illumination map of all disks in the forest. =========================================================================== How to meet asynchronously (almost) everywhere --------------------------------------------------------------------------- Authors: Jurek Czyzowicz (UQO, Gatineau, Canada) Arnaud Labourel (UQO, Gatineau, Canada) Andrzej Pelc (UQO, Gatineau, Canada) Topics: Graph Algorithms, Online problems --------------------------------------------------------------------------- Two mobile agents (robots) with distinct labels have to meet in an arbitrary, possibly infinite, unknown connected graph or in an unknown connected terrain in the plane. Agents are modeled as points, and the route of each of them only depends on its label and on the unknown environment. The actual walk of each agent also depends on an asynchronous adversary that may arbitrarily vary the speed of the agent, stop it, or even move it back and forth, as long as the walk of the agent in each segment of its route is continuous, does not leave it and covers all of it. Meeting in a graph means that both agents must be at the same time in some node or in some point inside an edge of the graph, while meeting in a terrain means that both agents must be at the same time in some point of the terrain. Does there exist a deterministic algorithm that allows any two agents to meet in any unknown environment in spite of this very powerfull adversary? We give deterministic rendezvous algorithms for agents starting at arbitrary nodes of any anonymous connected graph (finite or infinite) and for agents starting at any interior points with rational coordinates in any closed region of the plane with path-connected interior. While our algorithms work in a very general setting - agents can, indeed, meet almost everywhere - we show that none of the above few limitations imposed on the environment can be removed. On the other hand, our algorithm also guarantees the following approximate rendezvous for agents starting at arbitrary interior points of a terrain as above: agents will eventually get at an arbitrarily small positive distance from each other. =========================================================================== Decomposition, Approximation, and Coloring of Odd-Minor-Free Graphs --------------------------------------------------------------------------- Authors: Erik D. Demaine (MIT) MohammadTaghi Hajiaghayi (AT&T Labs -- Research) Ken-ichi Kawarabayashi (National Institute for Informatics) Topics: Graph Algorithms, Graph Theory --------------------------------------------------------------------------- We prove two structural decomposition theorems about graphs excluding a fixed odd minor H, and show how these theorems can be used to obtain approximation algorithms for several algorithmic problems in such graphs. As one example of how these structural results conquer difficult problems, we obtain a polynomial-time 2-approximation for vertex coloring in odd-H-minor-free graphs, improving on the previous O(|V(H)|)-approximation for such graphs from STOC 2006 and generalizing the 2-approximation for H-minor-free graphs from FOCS 2005. We also obtain PTASs and subexponential fixed-parameter algorithms for problems such as maximum independent set, maximum clique, and minimum vertex cover in odd-H-minor-free graphs, extending results of Grohe, Eppstein, and Baker. The class of odd-H-minor-free graphs is a vast generalization of the well-studied H-minor-free graph families and includes, for example, all bipartite graphs plus a bounded number of apices. Odd-H-minor-free graphs are particularly interesting from a structural graph theory perspective because they break away from the sparsity of H-minor-free graphs, permitting a quadratic number of edges. Our thesis is that most algorithmic results that have been obtained for both H-minor-free graphs and bipartite graphs can be generalized to odd-H-minor-free graphs. The class of H-minor-free graphs has already proved extremely useful and powerful, with applications in many areas such as network design and compact routing. Odd minors have attracted much interest in the graph theory community as well because of their connections and applications to Graph Minor Theory, discrete optimization, and Hadwiger's conjecture. Our decomposition results provide new structural insights into odd-H-minor-free graphs, on the one hand generalizing the central structural result from Graph Minor Theory, and on the other hand providing an algorithmic decomposition into two bounded-treewidth graphs, generalizing a similar result for minors obtained in FOCS 2005. These decompositions have already played important algorithmic roles for H-minor-free graphs; recent similar decompositions have been developed in STOC 2005 and SODA 2007. Our results broaden the applicability of these decompositions to odd-H-minor-free graphs. =========================================================================== Tree Embeddings for Two-Edge-Connected Network Design --------------------------------------------------------------------------- Authors: Anupam Gupta (Carnegie Mellon University) Ravishankar Krishnaswamy (Carnegie Mellon University) R. Ravi (Carnegie Mellon University) Topics: Approximation Algorithms, Graph Algorithms, Mathematical Programming, Optimization --------------------------------------------------------------------------- The group Steiner problem is a classical network design problem where we are given a graph and a collection of groups of vertices, and want to build a min-cost subgraph that connects the root vertex to at least one vertex from each group. What if we wanted to build a subgraph that "two-edge-connects" the root to each group---that is, for every group g, the subgraph should contain two edge-disjoint paths from the root to some vertex in g? What if wanted the two edge-disjoint paths to end up at distinct vertices in the group, so that the loss of a single member of the group would not destroy connectivity? In this paper, we investigate general techniques that can be used to solve these and other 2-connected network design problems. In particular we observe that tree-embedding techniques can be used to "simplify" instances of network design problems. While this is a simple observation, the additional structure obtained by it can be used to systematically obtain approximation algorithms by writing linear programming relaxations and rounding algorithms, much as they have been used for network design problems for (single-)connectivity. We illustrate the potential of these techniques by giving poly-logarithmic approximation algorithms for two-edge-connected versions of the group Steiner problem, the connected facility location, and the k-MST problem. Our results for the first two problems give the first non-trivial approximation algorithms for them. =========================================================================== A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover --------------------------------------------------------------------------- Authors: Nikhil Bansal (IBM TJ Watson Research) Anupam Gupta (Carnegie Mellon University) Ravishankar Krishnaswamy (Carnegie Mellon University) Topics: Approximation Algorithms, Mathematical Programming, Optimization --------------------------------------------------------------------------- Consider the following "generalized min-sum set cover" or "multiple intents re-ranking" problem proposed by Azar et al. (STOC 2009). We are given a universe of elements and a collection of subsets, with each set S having a covering requirement of K(S). The objective is to pick one element at a time such that the average "covering time" of the sets is minimized, where the covering time of a set S is the first time at which K(S) elements from it have been selected. There are two well-studied extreme cases of this problem: (i) when K(S) = 1 for all sets, we get the min-sum set cover problem, and (ii) when K(S) = |S| for all sets, we get the minimum-latency set cover problem. Constant factor approximations are known for both these problems. In their paper, Azar et al. considered the general problem and gave a logarithmic approximation algorithm for it. In this paper, we improve their result and give a simple randomized constant factor approximation algorithm for the generalized min-sum set cover problem. Our approach involves strengthening a natural LP relaxation by including the "knapsack cover inequalities", and then using a randomized rounding scheme which considers increasing prefixes of time, rounds the (fractional) assignments in these prefixes, and then combines these integral assignments into a single ordering. =========================================================================== Differentially Private Approximation Algorithms --------------------------------------------------------------------------- Authors: Anupam Gupta (Carnegie Mellon University) Katrina Ligett (Carnegie Mellon University) Frank McSherry (Microsoft Research) Aaron Roth (Carnegie Mellon University) Kunal Talwar (Microsoft Research) Topics: Algorithm Analysis, Approximation Algorithms, Graph Algorithms, Privacy --------------------------------------------------------------------------- Consider the following problem: given a metric space, some of whose points are ``clients'', open a set of at most $k$ facilities to minimize the average distance from the clients to these facilities. This is just the well-studied $k$-median problem, for which many approximation algorithms and hardness results are known. Note that the objective function encourages opening facilities in areas where there are many clients, and given a solution, it is often possible to get a good idea of where the clients are located. However, this poses the following quandry: what if the identity of the clients is sensitive information that we would like to keep private? \emph{Is it even possible to design good algorithms for this problem that preserve the privacy of the clients?} In this paper, we initiate a systematic study of algorithms for discrete optimization problems in the framework of differential privacy (which formalizes the idea of protecting the privacy of individual input elements). We show that many such problems indeed have good approximation algorithms that preserve differential privacy; this is even in cases where it is impossible to preserve cryptographic definitions of privacy while computing any non-trivial approximation to even the *value* of an optimal solution, let alone the entire solution. We consider a host of problems: vertex and set cover, min-cut, k-median, facility location, and Steiner tree, and give approximation algorithms and lower bounds for these problems. We also consider the recently introduced submodular maximization problem, ``Combinatorial Public Projects'' (CPP), shown by Papadimitriou et al. to be inapproximable to subpolynomial multiplicative factors by any efficient and *truthful* algorithm: for this, we give a differentially private (and hence *approximately* truthful) algorithm that achieves a logarithmic additive approximation. =========================================================================== Lower Bounds for Testing Triangle-freeness in Boolean Functions --------------------------------------------------------------------------- Authors: Arnab Bhattacharyya (MIT) Ning Xie (MIT) Topics: Algebra, Combinatorics, Complexity, Property Testing --------------------------------------------------------------------------- Let $f_{1}, f_{2}, f_{3}:\F_2^n \to \{0,1\}$ be three Boolean functions. We say a triple $(x,y,x+y)$ is a \emph{triangle} in the function triple $(f_{1}, f_{2}, f_{3})$ if $f_{1}(x)=f_{2}(y)=f_{3}(x+y)=1$. $(f_{1}, f_{2}, f_{3})$ is said to be \emph{triangle-free} if there is no triangle in the triple. The distance between a function triple and triangle-freeness is the minimum fraction of function values one needs to modify in order to make the function triple triangle-free. A \emph{canonical tester} for triangle-freeness repeatedly picks $x$ and $y$ uniformly and independently at random and checks if $f_{1}(x)=f_{2}(y)=f_{3}(x+y)=1$. Based on an algebraic regularity lemma, Green showed that the number of queries for the canonical testing algorithm is upper-bounded by a tower of $2$'s whose height is polynomial in $1/\epsilon$. A trivial query complexity lower bound of $\Omega(1/\epsilon)$ is straightforward to show. In this paper, we give the first non-trivial query complexity lower bound for testing triangle-freeness in Boolean functions. We show that, for every small enough $\epsilon$ there exists an integer $n_{0}(\epsilon)$ such that for all $n\geq n_{0}$ there exists a function triple $f_{1}, f_{2}, f_{3}: \F_2^n \to \{0,1\}$ depending on all the $n$ variables which is $\epsilon$-far from being triangle-free and requires $(\frac{1}{\epsilon})^{4.847\cdots}$ queries for the canonical tester. For the single function case that $f_{1}=f_{2}=f_{3}$, we obtain a weaker lower bound of $(\frac{1}{\epsilon})^{3.409\cdots}$. We also show that the query complexity of adaptive one-sided testers for matroid-freeness is polynomially related to the query complexity of the canonical tester. This yields $(1/\epsilon)^{2.423\cdots}$ and $(1/\epsilon)^{1.704\cdots}$ query complexity lower bounds for multi-function and single-function triangle-freeness respectively, with respect to general one-sided testers. =========================================================================== Efficiently Decodable Non-adaptive Group Testing --------------------------------------------------------------------------- Authors: Piotr Indyk (MIT) Hung Q. Ngo (University at Buffalo, SUNY) Atri Rudra (University at Buffalo, SUNY) Topics: Coding Theory, Combinatorics, Complexity, Streaming Algorithms, Sublinear Algorithms --------------------------------------------------------------------------- Motivated by applications in data stream algorithms, we consider the following "efficiently decodable'' non-adaptive group testing problem. There is an unknown string $x\in\{0,1\}^n$ with at most $d$ ones in it. We are allowed to query any subset $S\subseteq [n]$ of the indices. The answer to the query tells whether $x_S$ is the all zero string or not. The objective is to design as few queries as possible (say, $t$ queries) such that $x$ can be identified as fast as possible (say, $\poly(t)$-time). The well studied $d$-disjunct matrices (for which one can obtain $t=O(d^2\log{n})$) in general only allows for a "decoding" time of $O(nt)$, which can be exponentially larger than $\poly(t)$ for small values of $d$. This paper presents a randomness efficient construction of $d$-disjunct matrices (they are representations of group testing algorithms) with $t=O(d^2\log{n})$ tests that can be decoded in time $\poly(d)\cdot t\log^2{t}+O(t^2)$. To the best of our knowledge, this is the first result that achieves an efficient decoding time and matches the best known $O(d^2\log{n})$ bound on the number of tests. We also derandomize the construction, which results in a polynomial time deterministic construction of such matrices when $d=O(\log{n}/\log\log{n})$. These results have applications in determining ``hot items" [Cormode and Muthukrishnan, TODS 2005] and data forensics [Goodrich, Atallah and Tamassia, ANCS 2005]. A crucial building block in our construction is the notion of $(d,\ell)$-list disjunct matrices, where the goal is to output at most $d+\ell$ positions in $x$, including all the (at most $d$) positions that have a one in them. List disjunct matrices turn out to be interesting objects in their own right and were also considered independently by [Cheraghchi, FCT 2009]. We present connections between list disjunct matrices, expanders, dispersers and disjunct matrices. List disjunct matrices have applications in constructing $(d,\ell)$-sparsity separator structures [Ganguly, ISAAC 2008] and in constructing tolerant testers for Reed-Solomon codes in the data stream model. =========================================================================== Improved Approximation Algorithms for the Minimum Latency Problem via Prize-Collecting Strolls --------------------------------------------------------------------------- Authors: Aaron Archer (AT&T Labs -- Research) Anna Blasiak (Cornell University) Topics: Approximation Algorithms, Graph Algorithms, Internet and Network Algorithms, Mathematical Programming, Optimization, Scheduling and Resource Allocation --------------------------------------------------------------------------- The \emph{minimum latency problem} (MLP) is a well-studied variant of the \emph{traveling salesman problem} (TSP). In the MLP, the server's goal is to minimize the average latency that the clients experience prior to being served, rather than the total latency experienced by the server (as in the TSP). The MLP sometimes goes by other names, such as the \emph{traveling repairman problem}, or the \emph{deliveryman problem}. In practice, the metric space defining an MLP instance usually arises as the shortest path metric on a weighted graph. Unlike most combinatorial optimization problems, the MLP is NP-hard even on trees (Sitters, 2001). Our main result is an improved approximation algorithm for the MLP on trees, upon which we build improved approximation algorithms for a much wider class of graphs. The MLP on trees is interesting for several reasons. First, many of the aspects that make the problem difficult on general graphs are already present in the tree case. Second, all existing approximation algorithms for general graphs are built on approximation algorithms for the tree case. Third, there has been no improvement for the tree case since the 3.59-approximation of Goemans and Kleinberg, first introduced 13 years ago in 1996. Fourth, in the intervening period, the best ratio for general metrics has been improved to match the 3.59 for trees (Chaudhuri et al., 2003). In this paper, we improve the approximation ratio for trees to 3.03. In fact, our 3.03-approximation algorithm works for any class of graphs in which the related \emph{prize-collecting stroll} (PCS) problem is solvable in polynomial time, such as graphs of constant treewidth. More generally, for any class of graphs that admit a Lagrangian-preserving $\beta$-approximation algorithm, we can use this algorithm as a black box to achieve a $3.03 \beta$-approximation for the MLP. Sadly, this does not immediately improve the ratio of 3.59 for general graphs, because the current best value of $\beta$ for that case is 2. One interesting piece of our analysis is the solution of an infinite-dimensional linear program, used to analyze a finite-dimensional factor-revealing linear program (FRLP). We believe that our methods may hold promise for easing the analysis of other FRLPs encountered in the literature. =========================================================================== Phase Transition for the Mixing Time of the Glauber Dynamics for Coloring Regular Trees --------------------------------------------------------------------------- Authors: Prasad Tetali (School of Mathematics and School of Computer Science, Georgia Institute of Technology) Juan Vera (Department of Management Sciences, University of Waterloo) Eric Vigoda (School of Computer Science, Georgia Institute of Technology) Linji Yang (School of Computer Science, Georgia Institute of Technology) Topics: Markov Chains, Probability --------------------------------------------------------------------------- We prove that the mixing time of the Glauber dynamics for random k-colorings of the complete tree with branching factor b undergoes a phase transition at k=b(1+o_b(1))/\ln{b}. Our main result shows nearly sharp bounds on the mixing time of the dynamics on the complete tree with n vertices for k=Cb/\ln{b} colors with constant C. For C\geq 1 we prove the mixing time is O(n^{1+o_b(1)}\ln^2{n}). On the other side, for C< 1 the mixing time experiences a slowing down, in particular, we prove it is O(n^{1/C + o_b(1)}\ln^2{n}) and \Omega(n^{1/C-o_b(1)}). The critical point C=1 is interesting since it coincides (at least up to first order) to the so-called reconstruction threshold which was recently established by Sly. The reconstruction threshold has been of considerable interest recently since it appears to have close connections to the efficiency of certain local algorithms, and this work was inspired by our attempt to understand these connections in this particular setting. =========================================================================== A Space--Time Tradeoff for Permutation Problems --------------------------------------------------------------------------- Authors: Mikko Koivisto (Helsinki Institute for Information Technology HIIT, Dept. of Computer Science, Univ. of Helsinki) Pekka Parviainen (Helsinki Institute for Information Technology HIIT, Dept. of Computer Science, Univ. of Helsinki) Topics: Algebra, Combinatorics, Graph Algorithms, Optimization --------------------------------------------------------------------------- Various fundamental combinatorial problems can be formulated as finding a feasible permutation of n elements. Typically, such a problem can be solved by dynamic programming in time and space O*(2^n), or by the Gurevich--Shelah recurrence in time O*(4^n) and space polynomial in n; the O* notation suppresses a factor polynomial in n. A straightforward combination of these techniques runs in time O*(2^{2n-s}) and space O*(2^s) for any s = n, n/2, n/4, .... This raises the question whether one can make the tradeoff smooth, particularly for n/2 < s < n, or improve it to time O*(T^n) and space O*(S^n) at some T and S with TS < 4. Here, we answer the question affirmatively by providing such a smooth scheme for \sqrt{2} < S < 2. The scheme is based on suitably constructed families of partial orders on the $n$ elements such that every linear order on the elements is a linear extension of some of the partial orders in a family. We also show that our construction is optimal within a natural class of such families of partial orders. Applications to the traveling salesman, feedback arcset, cutwidth, and treewidth problems are discussed. =========================================================================== Randomized Shellsort: A Simple Oblivious Sorting Algorithm --------------------------------------------------------------------------- Authors: Michael T. Goodrich (Univ. of California, Irvine) Topics: Algorithm Analysis, Experimental Algorithmics, Probability --------------------------------------------------------------------------- In this paper, we describe randomized Shellsort—a simple, randomized, data-oblivious version of the Shellsort algorithm that always runs in O(n log n) time and, as we show, succeeds in sorting any given input permutation with very high probability. Thus, randomized Shellsort is arguably the first sorting algorithm that is simultaneously simple, time-optimal, and data-oblivious. Taken together, these properties imply applications in the design of new efficient privacy-preserving computations based on the secure multi-party computation (SMC) paradigm. In addition, by a trivial conversion of this Monte Carlo algorithm to its Las Vegas equivalent, one gets the first version of Shellsort with a running time that is provably O(n log n) with very high probability. =========================================================================== A Polynomial Time Approximation Scheme for k-Consensus Clustering --------------------------------------------------------------------------- Authors: Tom Coleman (The University of Melbourne) Anthony Wirth (The University of Melbourne) Topics: Approximation Algorithms, Graph Algorithms, Optimization --------------------------------------------------------------------------- This paper introduces a polynomial time approximation scheme for the Consensus Clustering problem when the number of clusters returned is bounded (by k). Consensus Clustering is a fundamental aggregation problem, with considerable application. It is analysed here as a metric variant of the Correlation Clustering problem. The PTAS exploits a connection between Correlation Clustering and the k-cut problems. This requires the introduction of a new rebalancing technique, based on minimum cost perfect matchings, to provide clusters of the required sizes. Both Consensus Clustering and Correlation Clustering have been the focus of considerable recent study. There is an existing dichotomy between the k-restricted Correlation Clustering problems and the unrestricted versions. The former, in general, admit a PTAS, whereas the latter are, in general, APX-hard. This paper extends the dichotomy to the metric case, responding to the result that Consensus Clustering is APX-hard to approximate. =========================================================================== Correlation Robust Stochastic Optimization --------------------------------------------------------------------------- Authors: Shipra Agrawal (Stanford University) Yichuan Ding (Stanford University) Amin Saberi (Stanford University) Yinyu Ye (Stanford University) Topics: Algorithm Analysis, Approximation Algorithms, Internet and Network Algorithms, Mathematical Programming, Optimization, Probability, Random Structures --------------------------------------------------------------------------- We consider a robust model proposed by Scarf, 1958, for stochastic optimization when only the marginal probabilities of random variables are given, and the correlation between the random variables is unknown. In the robust model, the objective is to minimize expected cost against worst possible joint distribution with those marginals. We introduce the concept of correlation gap to compare this model to the stochastic optimization model that ignores correlations and minimizes expected cost under independent Bernoulli distribution. We identify a class of functions, using concepts of summable cost sharing schemes from game theory, for which the correlation gap is well-bounded and the robust model can be approximated closely by the independent distribution model. As a result, we derive efficient approximation schemes for many popular cost functions, like submodular functions, facility location, and Steiner tree. As a byproduct of our analysis, we also improve some existing results in the areas of social welfare maximization and existence of Walrasian equilibria, which may be of independent interest. =========================================================================== On Nonlinear Forbidden Matrices: A Refutation of a Furedi-Hajnal Conjecture --------------------------------------------------------------------------- Authors: Seth Pettie (University of Michigan) Topics: Combinatorics --------------------------------------------------------------------------- A matrix $A\in \{0,1\}^{m\times n}$ is said to avoid a forbidden pattern $P\in\{0,1\}^{k\times l}$ if no $k\times l$ submatrix of $A$ matches $P$, where a $0$ in $P$ can match either a 0 or 1 in $A$. Let $Ex(P,n)$ be the maximum weight (i.e., number of 1s) of an $n\times n$ matrix avoiding $P$. The theory of forbidden submatrices subsumes many extremal problems in combinatorics and graph theory, including Davenport-Schinzel sequences and their generalizations, Stanley and Wilf's permutation avoidance problem, and Turan-type subgraph avoidance problems. Forbidden submatrices have found many applications in discrete geometry and the analysis of both geometric and non-geometric algorithms. In general terms, to bound the complexity of an arrangement of objections or the running time of an algorithm, one transcribes the objects or operations as a 0-1 matrix that provably avoids some forbidden pattern or collection of patterns $P$. This method is useful only to the extent that $Ex(P,n)$ can be tightly bounded, for specific $P$s or whole classes of $P$s. A 0-1 matrix can be interpreted as the incidence matrix of a bipartite graph where vertices on either side of the bipartition are ordered. In 1992, Furedi and Hajnal conjectured that imposing an order on the vertices only affects the extremal function up to a logarithmic factor, and, in particular, they conjectured that all acyclic forbidden matrices (i.e., corresponding to forests) have extremal functions in $O(n\log n)$. To be specific, let $Ex_{Tu}(G,n)$ be the maximum number of edges in an $n$-node graph avoiding subgraphs isomorphic to $G$ and let $G(P)$ be the unordered graph corresponding to the 0-1 matrix $P$. They conjectured: (A) Ex(P,n) = O(Ex_{Tu}(G(P),n) \log n) for all patterns $P$ (B) Ex(P,n) = O(n\log n) for all acyclic $P$ The general conjecture (A) was refuted just a few years ago by Pach and Tardos. However the specific conjecture (B) is more relevant to applications in algorithms and geometry: nearly all such applications use acyclic patterns. In the first part of this paper we refute conjecture (B) by exhibiting a specific $4\times 5$ pattern with extremal function $\Omega(n\log n\log\log n)$. Our lower bound construction uses two types of matrix composition operations: one operation roughly squares the density of a sparse 0-1 matrix and the other sparsifies it. In the second part of this paper we make some progress on another question asked by Furedi and Hajnal, namely, to identify the properties of a forbidden pattern that cause nonlinearity in its extremal function. We find tight or nearly tight bounds on certain small forbidden patterns and present a significantly simplified proof that there are infinitely many minimal nonlinear forbidden matrices w.r.t. containment. =========================================================================== Convergence, Stability, and Discrete Approximation of Laplace Spectra --------------------------------------------------------------------------- Authors: Tamal K. Dey (The Ohio State University) Pawas Ranjan (The Ohio State University) Yusu Wang (The Ohio State University) Topics: Geometry, Learning --------------------------------------------------------------------------- Spectral methods have been widely used in a broad range of application fields. One important object involved in such methods is the Laplace-Beltrami operator of a manifold. Indeed, a variety of work in graphics and geometric optimization uses the eigen-structures of the Laplace operator, and applications include mesh smoothing, compression, editing, shape segmentation, matching, and parametrization, among others. While the Laplace operator is defined (mathematically) for a smooth domain, in these applications, the underlying manifold is often approximated by a discrete mesh, and the spectral structure of the manifold Laplacian is estimated from some discrete Laplace operator constructed from this mesh. In this paper, we study the important question of how well the spectrum computed from the discrete mesh approximates the true spectrum of the manifold Laplacian. We exploit a recent result on mesh Laplacian and provide the first convergence result to relate the spectrum constructed from a mesh with the true spectrum. We also study how stable these eigen-structures and their discrete approximations are when the underlying manifold is perturbed, and provide explicit bounds for the Laplacian spectra of two ``close'' manifolds, as well as a convergence result for their discrete approximations. Finally, we present various experimental results to demonstrate that these discrete spectra are both accurate and robust in practice. =========================================================================== Generating a d-dimensional linear subspace efficiently --------------------------------------------------------------------------- Authors: Rapahael Yuster (University of Haifa) Topics: Algebra, Algorithm Analysis --------------------------------------------------------------------------- We present an algorithm for computing a $d$-dimensional subspace of the row space of a matrix. For an $n \times n$ matrix $A$ with $m$ nonzero entries and with $rank(A) \ge d$ the algorithm generates a $d \times n$ matrix with full row rank and which is a subspace of $Rows(A)$. If $rank(A) < d$ the algorithm generates a $rank(A) \times n$ row-equivalent matrix. The running time of the algorithm is $$ O( \min\{ n^{2-2/\omega}m^{1/\omega}d^{\omega-2+1/\omega}~,~ n^2d^{\omega-2} \} ) $$ where $\omega < 2.376$ is the matrix multiplication exponent. An immediate corollary of the algorithm is the construction of a row-reduced equivalent matrix of $A$, and hence the computation of $rank(A)$, in time $O( \min\{n^{2-2/\omega}m^{1/\omega}rank(A)^{\omega-2+1/\omega}~,~ n^2rank(A)^{\omega-2} \} )$. We note that the running time is sub-quadratic if $d < (n^2/m)^{0.528}$. =========================================================================== Classified Stable Matching --------------------------------------------------------------------------- Authors: Chien-Chung Huang (Max-Planck-Institut) Topics: Algorithm Analysis, Mathematical Programming --------------------------------------------------------------------------- We introduce the {\sc classified stable matching} problem, a problem motivated by academic hiring. Suppose that a number of institutes are hiring faculty members from a pool of applicants. Both institutes and applicants have preferences over the other side. An institute classifies the applicants based on their research areas (or any other criterion), and, for each class, it sets a lower bound and an upper bound on the number of applicants it would hire in that class. The objective is to find a stable matching from which no group of participants has reason to deviate. Moreover, the matching should respect the upper/lower bounds of the classes. In the first part of the paper, we study classified stable matching problems whose classifications belong to a fixed set of ``order types.'' We show that if the set consists entirely of downward forests, there is a polynomial-time algorithm; otherwise, it is NP-complete to decide the existence of a stable matching. In the second part, we investigate the problem using a polyhedral approach. Suppose that all classifications are laminar families and there is no lower bound. We propose a set of linear inequalities to describe stable matchings and prove that the polytope is integral. This integrality allows us to find various ``optimal'' stable matchings using Ellipsoid algorithm in polynomial time. By studying the geometric structure of fractional stable matchings, we are able to generalize a theorem of Teo and Sethuraman in the context of classified stable matching: given any number of stable matchings, if every applicant is assigned to his median choice among all stable matchings, the outcome is still a stable matching. Finally, a ramification of our result is the description of the stable matching polytope for the many-to-many (unclassified) stable matching problem. This answers an open question posed by Sethuraman, Teo and Qian (math. oper. res. 2006). =========================================================================== On linear and semidefinite programming relaxations for hypergraph matching --------------------------------------------------------------------------- Authors: Yuk Hei Chan (The Chinese University of Hong Kong) Lap Chi Lau (The Chinese University of Hong Kong) Topics: Approximation Algorithms, Graph Algorithms, Mathematical Programming --------------------------------------------------------------------------- The hypergraph matching problem is to find a largest collection of disjoint hyperedges in a hypergraph. This is a well-studied problem in combinatorial optimization and graph theory with various applications. The best known approximation algorithms for this problem are all based on local search. In this paper we analyze different linear and semidefinite programming relaxations for the hypergraph matching problem. Our main results are the following: - We consider the standard linear programming relaxation of the problem. We provide an algorithmic proof that the integrality gap is exactly k-1+1/k for k-uniform hypergraphs, and is exactly k-1 for k-partite hypergraphs. This yields an improved approximation algorithm for the weighted 3-dimensional matching problem. Our algorithm combines the use of the iterative rounding method and the local ratio method, showing a new way to analyze packing linear programs. - We study the strengthening of the standard LP relaxation by local constraints. We show that, even after linear number of rounds of the Sherali-Adams lift-and-project procedure on the standard LP relaxation, there are k-uniform hypergraphs with integrality gap at least k-2. On the other hand, we prove that for every constant k, there is a strengthening of the standard LP relaxation by only a polynomial number of constraints, with integrality gap at most (k+1)/2 for k-uniform hypergraphs. The construction uses a result in extremal combinatorics. - We consider the standard semidefinite programming relaxation of the problem. We prove that the Lovasz theta function provides an SDP relaxation with integrality gap at most (k+1)/2. The proof gives an indirect way (not by a rounding algorithm) to bound the ratio between any local optimal solution and any optimal SDP solution. This shows a new connection between local search and linear and semidefinite programming relaxations. =========================================================================== Counting Stars and Other Small Subgraphs in Sublinear Time --------------------------------------------------------------------------- Authors: Mira Gonen (Tel-Aviv University) Dana Ron (Tel-Aviv University) Yuval Shavitt (Tel-Aviv University) Topics: Algorithm Analysis, Combinatorics, Graph Algorithms, Graph Theory, Internet and Network Algorithms, Sublinear Algorithms --------------------------------------------------------------------------- Detecting and counting the number of copies of certain subgraphs (also known as {\em network motifs\/} or {\em graphlets\/}), is motivated by applications in a variety of areas ranging from Biology to the study of the World-Wide-Web. Several polynomial algorithms have been suggested for counting or detecting the number of occurrences of certain network motifs. However, a need for more efficient algorithms arises when the input graph is very large, as is indeed the case in many applications of motif counting. In this paper we design % for the first time, {\em sublinear\/} algorithms for approximating the number of copies of certain constant-size subgraphs in a graph $G$. That is, our algorithms do not read the whole graph, but rather query parts of the graph. The main focus of this work is on the basic problem of counting the number of length-$2$ paths and more generally on counting the number of stars of a certain size. Specifically, we design an algorithm that, given an approximation parameter $0 < \eps < 1$ and query access to a graph $G$, outputs an estimate $\hstars$ such that with high constant probability, %(over the coin flips of the algorithm), $(1-\eps)\stars(G) \leq \hstars\leq (1+\eps)\stars(G)$, where $\stars(G)$ denotes the number of stars of size $s+1$ in the graph. The expected query complexity and running time of the algorithm are $O\left(\frac{n}{(\stars(G))^{\frac{1}{s+1}}} + \min\left\{n^{1-\frac{1}{s}},\frac{n^{s-\frac{1}{s}}} {(\stars(G))^{1-\frac{1}{s}}}\right\}\right) \cdot \poly(\log n,1/\eps)\;$. We also prove lower bounds showing that this algorithm is tight up to polylogarithmic factors in $n$ and the dependence on $\eps$. Our work extends the work of Feige ({\em SIAM Journal on Computing, 2006\/}) and Goldreich and Ron ({\em Random Structures and Algorithms, 2008 \/}) on approximating the number of edges (or average degree) in a graph. Combined with these results, our result can be used to obtain an estimate on the variance of the degrees in the graph and corresponding higher moments. In addition, we give some (negative) results on approximating the number of triangles and on approximating the number of length-$3$-paths in sublinear time. =========================================================================== Deletion Without Rebalancing in Balanced Binary Trees --------------------------------------------------------------------------- Authors: Siddhartha Sen (Princeton University) Robert E. Tarjan (Princeton University) Topics: Algorithm Analysis, Data Structures, Databases and Information Retrieval --------------------------------------------------------------------------- We address the vexing issue of deletions in balanced trees. Rebalancing after a deletion is generally more complicated than rebalancing after an insertion. Textbooks neglect deletion rebalancing, and many database systems do not do it. We describe a relaxation of AVL trees in which rebalancing is done after insertions but not after deletions, yet access time remains logarithmic in the number of insertions. For many applications of balanced trees, our structure offers performance competitive with that of classical balanced trees. With the addition of periodic rebuilding, the performance of our structure is theoretically superior to that of many if not all classic balanced tree structures. Our structure needs $\bigO(\log\log m)$ bits of balance information per node, where $m$ is the number of insertions. As in an AVL tree, an insertion takes up to two rotations and $\bigO(1)$ amortized time. Using an analysis that relies on an exponential potential function, we show that rebalancing steps occur with a frequency that is exponentially small in the height of the affected node. =========================================================================== Regular Expression Matching with Multi-Strings --------------------------------------------------------------------------- Authors: Philip Bille (Technical University of Denmark) Mikkel Thorup (AT&T Labs-Research) Topics: Bioinformatics, Databases and Information Retrieval, Internet and Network Algorithms, Pattern Matching, Streaming Algorithms, String Algorithms --------------------------------------------------------------------------- Regular expression matching is a key task (and often computational bottleneck) in a variety of software tools and applications. For instance, the standard \texttt{grep} and \texttt{sed} utilities, scripting languages such as \texttt{perl}, internet traffic analysis, XML querying, and protein searching. The basic defintion of a regular expression is that we combine characters with union, concatenation, and kleene star operators. The length $m$ is proportional to the number of characters. However, often the initial operation is to concatenate characters in fairly long strings, e.g., if we search for certain combinations of words in a firewall. As a result, the number $\widetilde m$ of strings in the regular expression is significantly smaller than $m$. Our goal is to essentially replace $m$ with $\widetilde m$ in the complexity bounds for regular expression matching. After an $O(m\log m)$ time and $O(m)$ space preprocessing of the expression, we can match it in a string presented as a stream of characters in $O(\lceil \widetilde{m} \frac{\log w}w\rceil)$ time per character, where $w$ is the number of bits in a memory word. For large $w$ this corresponds to the previous best bound of $O(\lceil m \frac{\log w}w\rceil)$. Prior to this work no $O(\widetilde m)$ bound per character was known. =========================================================================== The edge disjoint paths problem in Eulerian graphs and $4$-edge-connected graphs --------------------------------------------------------------------------- Authors: Ken-ichi Kawarabayashi (National Institute of Informatics) Yusuke Kobayashi (University of Tokyo) Topics: Graph Algorithms, Graph Theory --------------------------------------------------------------------------- We consider the following well-known problem, which is called the edge-disjoint paths problem. Input: A graph $G$ with $n$ vertices and $m$ edges, $k$ pairs of vertices $(s_1,t_1),(s_2,t_2),\dots, (s_k,t_k)$ in $G$. Output: Edge-disjoint paths $P_1,\dots,P_k$ in $G$ such that $P_i$ joins $s_i$ and $t_i$ for $i=1,2,\dots,k$. Robertson and Seymour's graph minor project gives rise to an $O(m^3)$ algorithm for this problem for any fixed $k$, but their proof of the correctness needs the whole Graph Minor project, spanning 23 papers and at least 500 pages proof. We give a faster algorithm and a much simpler proof of the correctness for the edge-disjoint paths problem for any fixed $k$. Our results can be summarized as follows: (1) If an input graph $G$ is either $4$-edge-connected or Eulerian, then our algorithm only needs to look for the following three simple reductions: (i) Excluding vertices of high degree. (ii) Excluding $\leq 3$-edge cut. (iii) Excluding large clique minors. (2) When an input graph $G$ is either $4$-edge-connected or Eulerian, our algorithm still runs in polynomial time even if $k$ is not fixed but $k=O((\log \log \log n)^{\frac{1}{2}-\epsilon})$ for some $\epsilon > 0$. Thus our hidden constant in this case is dramatically smaller than Robertson-Seymour's. In addition, if an input graph $G$ is either $4$-edge-connected planar or Eulerian planar, then our algorithm still runs in polynomial time even if $k$ is not fixed but $k = O((\log n)^{\frac{1}{2}-\epsilon})$ for some $\epsilon > 0$. Moreover, if an input graph is either $4$-edge-connected $H$-minor-free or Eulerian $H$-minor-free, then our algorithm still runs in polynomial time even if $k$ is not fixed but $k=O((\log \log n)^{\frac{1}{2}-\epsilon})$ for some $\epsilon > 0$. (3) We also give our own algorithm for the edge-disjoint paths problem in general graphs. We basically follow Robertson-Seymour's algorithm, but we cut half of the proof of the correctness for their algorithm. In addition, the time complexity of our algorithm is $O(n^2)$, which is faster than Robertson and Seymour's. =========================================================================== Coresets and Sketches for High Dimensional Subspace Approximation Problems --------------------------------------------------------------------------- Authors: Dan Feldman (School of Computer Science; Tel Aviv University; Tel Aviv 69978, Israel) Morteza Monemizadeh (Department of Computer Science, University of Dortmund; , Germany) Christian Sohler (Department of Computer Science, University of Dortmund; , Germany) David P. Woodruff (IBM Almaden Research Center, San Jose, CA) Topics: Approximation Algorithms, Geometry, Learning, Streaming Algorithms, Sublinear Algorithms --------------------------------------------------------------------------- Given a point set $P$ in $\REAL^d$, an $F_q(\ell_p)$-subspace approximation problem asks for a subspace that minimizes the sum of $q$-th powers of $\ell_p$-distances to this subspace. In this paper we develop techniques for subspace approximation, regression, and matrix approximation that can be used to deal with massive data sets in high dimensional spaces. In particular, we develop coresets and sketches, i.e. small space representations that approximate the input point set $P$ with respect to a subspace approximation problem. Our results are: \begin{itemize} \item A dimensionality reduction method that can be applied to $F_q(\ell_p)$-clustering and shape fitting problems \cite{DDHKM09, Har06c}. \item The first strong coreset for $F_1(\ell_2)$-subspace approximation in high dimensional spaces, i.e. of size polynomial in the dimension of the space. \item A $(1+\epsilon)$-approximation algorithm for the $j$-dimensional $F_1(\ell_2)$-subspace approximation problem with running time $O(nd (j/\eps)^{O(1)} + (n+d) 2^{O(j/\epsilon)^{O(1)}})$. \item A streaming algorithm that maintains a coreset for the $F_1(\ell_2)$-subspace approximation problem and uses $\tilde{O}(d(\frac{j2^{ O(\sqrt{\log n})}}{\epsilon^2})^{\poly(j)})$ space, where the space gives the number of memory cells used. \item Several streaming algorithm with bounded precision in the turnstile model. We significantly extend the results of \cite{CW09} for approximate linear regression, distance to subspace approximation, and best rank-$j$ approximation, to error measures other than the Frobenius norm, obtaining $1$-pass sublinear, near-optimal space complexity for these problems. Our time is always polynomial for constant $j/\eps$, even for the time to extract a $(1+\eps)$-approximation to the best rank-$j$ subspace from the sketch. \end{itemize} =========================================================================== 1-pass Relative-Error L_p-Sampling with Applications --------------------------------------------------------------------------- Authors: Morteza Monemizadeh (Department of Computer Science, University of Dortmund; , Germany) David P. Woodruff (IBM Almaden Research Center, San Jose, CA) Topics: Streaming Algorithms --------------------------------------------------------------------------- For any p in [1,2], we give a 1-pass poly((log n)/epsilon)-space algorithm which, given a data stream of length m with insertions and deletions of an n-dimensional vector a with updates in the range {-M, -M+1, ..., M-1, M} outputs a sample of {1, 2, ..., m} for which for all i the probability that i is returned is (1 +- epsilon)|a_i|^p/F_p(a) + n^{-C}, where a_i denotes the (possibly negative) value of coordinate i, F_p(a) = sum_{i=1}^m |a_i|^p = ||a||_p^p denotes the p-th frequency moment (i.e., the p-th power of the L_p norm), and C > 0 is an arbitrarily large constant. Here we assume that n,m, and M are polynomially related. Our generic sampling framework improves and unifies algorithms for several communication and streaming problems, including cascaded norms, heavy hitters, and moment estimation. It also gives the first relative-error forward sampling algorithm in a data stream with deletions, answering an open question of Cormode et al. =========================================================================== One-Counter Markov Decision Processes --------------------------------------------------------------------------- Authors: Tomas Brazdil (Faculty of Informatics, Masaryk University) Vaclav Brozek (Faculty of Informatics, Masaryk University) Kousha Etessami (School of Informatics, University of Edinburgh) Antonin Kucera (Faculty of Informatics, Masaryk University) Dominik Wojtczak (CWI, Amsterdam) Topics: Complexity, Game Theory, Markov Chains, Optimization, Probability --------------------------------------------------------------------------- We study the computational complexity of central analysis problems for One-Counter Markov Decision Processes (OC-MDPs), a class of finitely-presented, countable-state MDPs. OC-MDPs extend finite-state MDPs with an unbounded counter. The counter can be incremented, decremented, or not changed during each state transition, and transitions may be enabled or not depending on both the current state and on whether the counter value is 0 or not. Some states are ``random'', from where the next transition is chosen according to a given probability distribution, while other states are ``controlled'', from where the next transition is chosen by the controller. Different objectives for the controller give rise to different computational problems, aimed at computing optimal achievable objective values and optimal strategies. OC-MDPs are in fact equivalent to a controlled extension of (discrete-time) Quasi-Birth-Death processes (QBDs), a purely stochastic model heavily studied in queueing theory and applied probability. They can thus be viewed as a natural ``adversarial'' extension of a classic stochastic model. They can also be viewed as a natural probabilistic/controlled extension of classic one-counter automata. OC-MDPs also subsume (as a very restricted special case) a recently studied MDP model called ``solvency games'' that model a risk-averse gambling scenario. Basic computational questions for OC-MDPs include ``termination'' questions and ``limit'' questions, such as the following: does the controller have a strategy to ensure that the counter (which may, for example, count the number of jobs in the queue) will hit value 0 (the empty queue) almost surely (a.s.)? Or that the counter will have lim sup value infinity, a.s.? Or, that it will hit value 0 in a selected terminal state, a.s.? Or, in case such properties are not satisfied almost surely, compute their optimal probability over all strategies. We provide new upper and lower bounds on the complexity of such problems. Specifically, we show that several quantitative and almost-sure limit problems can be answered in polynomial time, and that almost-sure termination problems (without selection of desired terminal states) can also be answered in polynomial time. On the other hand, we show that the almost-sure termination problem with selected terminal states is PSPACE-hard and we provide an exponential time algorithm for this problem. We also characterize classes of strategies that suffice for optimality in several of these settings. Our upper bounds combine a number of techniques from the theory of MDP reward models, the theory of random walks, and a variety of automata-theoretic methods. =========================================================================== How far can you reach? --------------------------------------------------------------------------- Authors: Ciprian Borcea (Dept. of Mathematics, Rider University) Ileana Streinu (Computer Science Department, Smith College) Topics: Geometry, Metric Embeddings, Robotics --------------------------------------------------------------------------- Robot Arm Reachability, the problem of computing the extremal configurations of a 3D revolute-jointed manipulator, is a long standing open problem in Robotics. In this paper we completely solve it for orthogonal polygonal chains, which appear as a special case of a larger family, fully characterized here by a technical condition. Until now, in spite of the practical importance of the problem, only numerical optimization heuristics were available. These were not even guaranteed to produce the optimum; in fact, the problem was not even known to be computationally solvable, and in practice, the numerical heuristics were applicable only to small problem sizes. We present surprisingly elementary and efficient (mostly linear time) algorithms for four fundamental problems: (1) finding the minimum and the maximum reach value, (2) finding an extremal configuration (or enumerating all of them), (3) folding a given chain to a given extremal position, and (4) folding a chain in a way that changes the endpoint distance function monotonically. Our theoretical results reduce the first problem to finding a shortest path between two vertices in an associated simple triangulated polygon, and the last problem to a simple version of the planar Carpenter's Rule Problem. =========================================================================== Region growing for multi-route cuts --------------------------------------------------------------------------- Authors: Shuchi Chawla (University of Wisconsin - Madison) Siddharth Barman (University of Wisconsin - Madison) Topics: Approximation Algorithms, Graph Algorithms, Optimization --------------------------------------------------------------------------- We study a number of \emph{multi-route cut} problems: given a graph $G=(V,E)$ and connectivity thresholds $k_{(u,v)}$ on pairs of nodes, the goal is to find a minimum cost set of edges or vertices the removal of which reduces the connectivity between every pair $(u,v)$ to strictly below its given threshold. These problems arise in the context of reliability in communication networks; They are natural generalizations of traditional minimum cut problems where the thresholds are either $1$ (we want to completely separate the pair) or $\infty$ (we don't care about the connectivity for the pair). We provide the first non-trivial approximations to a number of variants of the problem including for both node-disjoint and edge-disjoint connectivity thresholds. A main contribution of our work is an extension of the region growing technique for approximating minimum multicuts to the multi-route setting. When the connectivity thresholds are either $2$ or $\infty$ (the ``$2$-route cut'' case), we obtain polylogarithmic approximations while satisfying the thresholds exactly. For arbitrary connectivity thresholds this approach leads to bicriteria approximations where we approximately satisfy the thresholds and approximately minimize the cost. We present a number of different algorithms achieving different cost-connectivity tradeoffs. =========================================================================== Faster exponential time algorithms for the shortest vector problem --------------------------------------------------------------------------- Authors: Daniele Micciancio (University of California, San Diego) Panagiotis Voulgaris (University of California, San Diego) Topics: Algorithm Analysis, Cryptography, Experimental Algorithmics --------------------------------------------------------------------------- We present new faster algorithms for the exact solution of the shortest vector problem in arbitrary lattices. Our main result shows that the shortest vector in any $n$-dimensional lattice can be found in time $2^{3.199 n}$ and space $2^{1.325 n}$. This improves the best previously known algorithm by Ajtai, Kumar and Sivakumar [Proceedings of STOC 2001] which was shown by Nguyen and Vidick [J. Math. Crypto. 2(2):181--207] to run in time $2^{5.9n}$ and space $2^{2.95n}$. We also present a practical variant of our algorithm which provably uses an amount of space proportional to $\tau_n$, the ``kissing'' constant in dimension $n$. Based on the best currently known upper and lower bounds on the kissing constant, the space complexity of our second algorithm is provably bounded by $2^{0.41n}$, and it is likely to be at most $2^{0.21n}$ in practice. No upper bound on the running time of our second algorithm is currently known, but experimentally the algorithm seems to perform fairly well in practice, with running time $2^{0.48n}$, and space complexity $2^{0.18n}$. =========================================================================== Finding the Jaccard Median --------------------------------------------------------------------------- Authors: Flavio Chierichetti (Sapienza University of Rome) Ravi Kumar (Yahoo! Research Santa Clara) Sandeep Pandey (Yahoo! Research Santa Clara) Sergei Vassilvitskii (Yahoo! Research New York) Topics: Approximation Algorithms, Optimization --------------------------------------------------------------------------- The median problem in the weighted Jaccard metric was analyzed for the first time by Sp\"ath in 1981. Up until now, only an exponential-time exact algorithm was known. We (a) show that the problem does not admit a FPTAS (assuming P $\ne$ NP), even when restricted to binary vectors and (b) give a PTAS for the general weighted Jaccard metric. The PTAS leverages of a number of different algorithmic ideas and our hardness result makes use of a gadget which appears to be ``unique'' in interesting ways. =========================================================================== The scaling window for a random graph with a given degree sequence --------------------------------------------------------------------------- Authors: Hamed Hatami (University of Toronto) Michael Molloy (University of Toronto) Topics: Graph Theory, Random Graphs --------------------------------------------------------------------------- We consider a random graph on a given degree sequence $D$, satisfying certain conditions. We focus on two parameters $Q=Q(D), R=R(D)$. Molloy and Reed proved that $Q=0$ is the threshold for the random graph to have a giant component. We prove that if $|Q|=O(n^{-1/3} R^{2/3})$ then, with high probability, the size of the largest component of the random graph will be of order $\Theta(n^{2/3}R^{-1/3})$. If $Q$ is asymptotically larger/smaller that $n^{-1/3}R^{2/3}$ then the size of the largest component is asymptotically larger/smaller than $n^{2/3}R^{-1/3}$. In other words, we establish the scaling window. =========================================================================== Energy Efficient Scheduling for Data Centers via Partial Shutdown --------------------------------------------------------------------------- Authors: Samir Khuller (University of Maryland) Jian Li (University of Maryland) Barna Saha (University of Maryland) Topics: Approximation Algorithms, Scheduling and Resource Allocation --------------------------------------------------------------------------- Motivated by issues of saving energy in data centers we define a collection of new problems referred to as ``machine activation'' problems. The central framework we introduce considers a collection of $m$ machines (unrelated or related) with each machine $i$ having an {\em activation cost} of $a_i$. There is also a collection of $n$ jobs that need to be performed and $p_{ij}$ is the processing time of job $j$ on machine $i$. Standard scheduling models assume that the set of machines is fixed and all machines are available. However, in our setting, we assume that there is an activation cost budget of $A$ -- we would like to {\em select} a subset $S$ of the machines to activate with total cost $a(S) \le A$ and {\em find} a schedule for the $n$ jobs on the machines in $S$ minimizing the makespan (or any other metric). We consider both the unrelated machines setting, as well as the setting of scheduling uniformly related parallel machines, where machine $i$ has cost $a_i$ and speed $s_i$, and the processing time of job $j$ on machine $i$ is $p_{ij} = \frac{p_j}{s_i}$, where $p_j$ is the processing requirement of job $j$. For the general unrelated machine activation problem, our main results are that if there is a schedule with makespan $T(A)$ and activation cost $A$ then we can obtain a schedule with makespan $\makespanconstant T(A)$ and activation cost $\costconstant A$, for any $\epsilon >0$. We also consider assignment costs for jobs as in the generalized assignment problem, and using our framework, provide algorithms that minimize the machine activation and the assignment cost simultaneously. For the uniformly related parallel machine scheduling problem, we develop a polynomial time scheme that outputs a schedule with the property that the activation cost of the subset of machines is at most $A$ and the makespan is at most $(1+\epsilon) T(A)$ for any $\epsilon >0$. For the special case of $m$ identical speed machines, the machine activation problem is trivial, since the cheapest subset of $k$ machines is always the best choice if the optimal solution activates $k$ machines. In addition, we consider the case when some jobs can be dropped (and are treated as outliers). =========================================================================== Sharp Dichotomies for Regret Minimization in Metric Spaces --------------------------------------------------------------------------- Authors: Robert Kleinberg (Cornell University) Aleksandrs Slivkins (Microsoft Research (SVC)) Topics: Algorithm Analysis, Learning, Online problems, Optimization --------------------------------------------------------------------------- The Lipschitz multi-armed bandit (MAB) problem generalizes the classical multi-armed bandit problem by assuming one is given side information consisting of a priori upper bounds on the difference in expected payoff between certain pairs of strategies. Classical results of Lai and Robbins and Auer et al imply a logarithmic regret bound for the Lipschitz MAB problem on finite metric spaces. Recent results on continuum-armed bandit problems and their generalizations imply lower bounds of $\sqrt{t}$, or stronger, for many infinite metric spaces such as the unit interval. Is this dichotomy universal? We prove that the answer is yes: for every metric space, the optimal regret of a Lipschitz MAB algorithm is either bounded above by any $f\in \omega(\log t)$, or bounded below by any $g\in o(\sqrt{t})$. Perhaps surprisingly, this dichotomy does not coincide with the distinction between finite and infinite metric spaces; instead it depends on whether the completion of the metric space is compact and countable. Our proof connects upper and lower bound techniques in online learning with classical topological notions such as perfect sets and the Cantor-Bendixson theorem. We also consider the "full-feedback" (a.k.a., "best-expert") version of Lipschitz MAB problem, termed the "Lipschitz experts problem", and show that this problem exhibits a similar dichotomy. We proceed to give nearly matching upper and lower bounds on regret in the Lipschitz experts problem on uncountable metric spaces. These bounds are of the form $\tilde{\Theta}(t^\gamma)$, where the exponent $\gamma\in [\tfrac12, 1]$ depends on the metric space. To characterize this dependence, we introduce a novel dimensionality notion tailored to the experts problem. Finally, we show that both Lipschitz bandits and Lipschitz experts problems become completely intractable (in the sense that no algorithm has regret $o(t)$) if and only if the completion of the metric space is non-compact. =========================================================================== Lower Bounds for Sparse Recovery --------------------------------------------------------------------------- Authors: khanh do ba (MIT CSAIL) piotr indyk (MIT CSAIL) eric price (MIT CSAIL) Topics: Approximation Algorithms, Coding Theory, Compression, Geometry, Information Theory, Streaming Algorithms, Sublinear Algorithms --------------------------------------------------------------------------- Over the recent years, a new *linear* method for compressing high-dimensional data has been discovered. For an n-dimensional vector x, its *sketch* is equal to Ax, where A is an m x n matrix, possibly chosen at random. Although typically the sketch length m is much smaller than the number of dimensions n, the sketch often contains plenty of information about x. A particularly useful and well-studied problem is that of sparse recovery: given Ax, recover a k-sparse vector x* (with at most k non-zeros) such that ||x-x*||_p <= C min_{k-sparse x'} ||x-x'||_q for some norm parameters p and q and an approximation factor C=C(k). Sparse recovery has numerous applications to areas such as data stream computing and compressed sensing. It is known that there exist matrices A that achieve the above guarantee with p=q=1 and constant C (in fact, even somewhat stronger bounds), with sketch length m=O(k log (n/k)). However, perhaps surprisingly, it is not known if this bound can be improved any further, even though matching lower bounds are known for specific *algorithms*, specific *matrix types*, or other recovery scenarios (e.g., involving measurement noise). The lack of tight lower bounds represents a major gap in our understanding of the problem. In this paper we make significant progress on this issue. In particular we show that: - in the deterministic case, where we require one matrix A to work for all signals x, we show a tight lower bound of Omega(k log (n/k)), thus resolving the issue completely - in the randomized case, where we require that a matrix A chosen at random from some distribution should work for a *fixed* vector x with probability at least 1-1/n, we show a lower bound of Omega(log n / log log n) =========================================================================== The Complexity of Guarding Terrains --------------------------------------------------------------------------- Authors: James King (McGill University) Erik Krohn (University of Iowa) Topics: Complexity, Geometry --------------------------------------------------------------------------- A set G of points on a 1.5-dimensional terrain, also known as an x-monotone polygonal chain, is said to guard the terrain if any point on the terrain is ‘seen’ by a point in G. Two points on the terrain see each other if and only if the line segment between them is never strictly below the terrain. The minimum terrain guarding problem asks for a minimum guarding set for the given input terrain. We prove that the decision version of this problem is NP-hard. This solves a significant open problem and complements recent positive approximability results for the optimization problem. Our proof uses a reduction from PLANAR 3-SAT. We build gadgets capable of ‘mirroring’ a consistent variable assignment back and forth across a main valley. The structural simplicity of 1.5-dimensional terrains makes it difficult to build general clause gadgets that do not destroy this assignment when they are evaluated. However, we exploit the structure in instances of PLANAR 3-SAT to find very specific operations involving only ‘adjacent’ variables. For these restricted operations we can construct gadgets that allow a full reduction to work. =========================================================================== An (almost) Linear Time Algorithm For Odd Cycles Transversal --------------------------------------------------------------------------- Authors: Ken-ichi Kawarabayashi (National Institute of Informatics) Bruce Reed (McGill University) Topics: Graph Algorithms, Graph Theory --------------------------------------------------------------------------- We consider the following problem, which is called the odd cycles transversal problem. Input: A graph G and an integer k. Output : A vertex set X \in V(G) with at most k vertices such that G-X is bipartite. We present an O(m \alpha(m,n)) time algorithm for this problem for any 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 improves the time complexity of the algorithms by Reed, and by Reed, Smith and Vetta who gave an O(nm) time algorithm for this problem. Our algorithm also implies the edge version of the problem, i.e, there is an edge set X' \in E(G) such that G-X' is bipartite. Using this algorithm and our recent result(SODA'09), we give an O(m \alpha(m,n) + n \log n) algorithm for the following problem for any fixed k: Input: A graph G and an integer k. Output : Determine whether or not there is a half-integral k disjoint odd cycles packing, i.e, k odd cycles C_1,\dots,C_k in G such that each vertex is on at most two of these odd cycles. We also give a simpler proof for the following result by Reed. The Erd\H{o}s-P\'osa property holds for the half-integral disjoint odd cycles packing problem. I.e. either G has a half-integral k disjoint odd cycles packing or G has a vertex set X of order at most f(k) such that G-X is bipartite for some function f of k. Note that the Erd\H{o}s-P\'osa property does not hold for odd cycles in general. =========================================================================== Thin Partitions: Isoperimetric Inequalities and Sampling Algorithms for some Nonconvex Families --------------------------------------------------------------------------- Authors: Karthekeyan Chandrasekaran (Georgia Institute of Technology) Daniel Dadush (Georgia Institute of Technology) Santosh Vempala (Georgia Institute of Technology) Topics: Geometry, Markov Chains, Probability --------------------------------------------------------------------------- Star-shaped bodies are an important nonconvex generalization of convex bodies (e.g., linear programming with violations). Here we present an ecient algorithm for sampling a given star-shaped body. The complexity of the algorithm grows polynomially in the dimension and inverse polynomially in the fraction of the volume taken up by the kernel of the star-shaped body. The analysis is based on a new isoperimetric inequality. Our main technical contribution is a tool for proving such inequalities when the domain is not convex. As a consequence, we obtain a polynomial algorithm for computing the volume of such a set as well. In contrast, linear optimization over star-shaped sets is NP-hard. =========================================================================== Resource Minimization for Fire Containment --------------------------------------------------------------------------- Authors: Parinya Chalermsook (University of Chicago) Julia Chuzhoy (TTI-C) Topics: Approximation Algorithms, Graph Algorithms, Scheduling and Resource Allocation --------------------------------------------------------------------------- We consider the following model for fire containment. We are given an undirected graph G=(V,E) with a source vertex s where the fire starts. At each time step, firefighters can save up to k vertices of the graph, while the fire spreads from burning vertices to all their neighbors that have not been saved so far. Our goal is to choose the vertices to be saved at each time step so as to contain the fire. This is a simple mathematical model abstracting the dynamic nature of fire containment and other natural processes, such as, for example, the spread of a perfectly contagious disease, and its containment via vaccination. In this paper we focus on the Resource Minimization Fire Containment (RMFC) problem, where we are additionally given a subset T of vertices called terminals that need to be protected from fire. The objective is to minimize k - the maximum number of vertices to be saved at any time step, so that the fire does not spread to any vertex of T. The problem is hard to approximate up to any factor better than 2 even on trees. We show an $O(\log^*n)$-approximation algorithm for RMFC on trees, by rounding a natural linear programming relaxation of the problem. We also show that an even stronger LP relaxation has an integrality gap of $\Omega(\log^*n)$ on trees. Finally, we consider RMFC on directed layered graphs, and show an O(\log n)-approximation LP-rounding algorithm, matching the integrality gap of the LP relaxation. =========================================================================== Price of Anarchy for Greedy Auctions --------------------------------------------------------------------------- Authors: Brendan Lucier (University of Toronto) Allan Borodin (University of Toronto) Topics: Approximation Algorithms, Game Theory, Mechanism Design --------------------------------------------------------------------------- We consider mechanisms for utilitarian combinatorial allocation problems, where agents are not assumed to be single-minded. This class of problems includes combinatorial auctions, multi-unit auctions, unsplittable flow problems, profit-maximizing scheduling, and others. We study the price of anarchy for such mechanisms, which is a bound on the approximation ratio obtained at any mixed Nash equilibrium. We demonstrate that a broad class of greedy approximation algorithms can be implemented as mechanisms for which the price of anarchy nearly matches the performance of the original algorithm. This is true even in Bayesian settings, where the agents' valuations are drawn from publicly known distributions. Furthermore, for a rich subclass of allocation problems, pure Nash equilibria are guaranteed to exist for these mechanisms. For many problems, the approximation factors obtained at equilibrium improve upon the best known results for deterministic truthful mechanisms. In particular, we exhibit a simple deterministic mechanism for the general combinatorial auction with $O(\sqrt{m})$ price of anarchy. =========================================================================== Inapproximability for planar embedding problems --------------------------------------------------------------------------- Authors: Jeff Edmonds (York University) Anastasios Sidiropoulos (University of Toronto) Anastasios Zouzias (University of Toronto) Topics: Approximation Algorithms, Complexity, Geometry, Metric Embeddings --------------------------------------------------------------------------- We consider the problem of computing a minimum-distortion bijection between two point-sets in R^2. We prove the first non-trivial inapproximability result for this problem, for the case when the distortion is constant. More precisely, we show that there exist constants 0 < alpha < beta, such that it is NP-hard to distinguish between spaces for which the distortion is either at most alpha, or at least beta, under the Euclidean norm. This addresses a question of [Kenyon, Rabani and Sinclair 2004], and extends a result due to [Papadimitriou and Safra 2005], who gave inapproximability for point-sets in R^3. We also apply similar ideas to the problem of computing a minimum distortion embedding of a finite metric space into R^2. We obtain an analogous inapproximability result under the \ell_{\infty} norm for this problem. Inapproximability for the case of constant distortion was previously known only for dimension at least 3 [Matousek and Sidiropoulos 2008]. =========================================================================== How good is the Chord algorithm? --------------------------------------------------------------------------- Authors: Constantinos Daskalakis (MIT) Ilias Diakonikolas (Columbia University) Mihalis Yannakakis (Columbia University) Topics: Algorithm Analysis, Approximation Algorithms, Geometry, Optimization --------------------------------------------------------------------------- The Chord algorithm is a popular, simple method for the succinct approximation of curves, which is widely used, under different names, in a variety of areas, such as, multiobjective and parametric optimization, computational geometry, and graphics. We analyze the performance of the chord algorithm, as compared with the optimal approximation that achieves a desired accuracy with the minimum number of points, and prove sharp upper and lower bounds, both in the worst case and average case setting. =========================================================================== On the Equilibria of Asynchronous Games --------------------------------------------------------------------------- Authors: Aaron Roth (Carnegie Mellon University) Nina Balcan (Microsoft Research and Georgia Tech) Adam Kalai (Microsoft Research) Yishay Mansour (Google Research and Tel Aviv University) Topics: Algorithm Analysis, Approximation Algorithms, Economics, Game Theory --------------------------------------------------------------------------- We consider computational aspects of alternating move games, repeated games in which players take actions at alternating time steps rather than playing simultaneously. This model is in many ways more computationally tractable than the simultaneous move model: Unlike in the simultaneous move model, in which computing even a 1-shot Nash equilibrium is PPAD complete, equilibria for the finitely repeated case of alternating move games can be computed simply using backwards induction. In the infinitely repeated case, alternating move games always admit equilibrium strategies in stationary policies: memoryless strategies that only depend on the current state of the game. Our main result is a PTAS for computing epsilon-approximate pure equilibria in alternating move general-sum games that admit pure equilibria. We show that this accounts for all but a negligible fraction of alternating move games. This is in contrast to the simultaneous move model, in which computing even an alpha-approximate pure Nash equilibrium in concisely represented games is PLS-complete, for any computable alpha. We also give an FPTAS for computing epsilon-approximate (non-stationary policy) equilibria in any alternating move game. =========================================================================== Recognizing a totally odd K_4-subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements --------------------------------------------------------------------------- Authors: Ken-ichi Kawarabayashi (National Institute of Informatics) Zhentao Li (McGill University) Bruce Reed (McGill University and INRIA, Laboratoire I3S, CNRS) Topics: Graph Algorithms, Graph Theory --------------------------------------------------------------------------- A totally odd K_4-subdivision is a subdivision of K_4 where each subdivided edge has odd length. The recognition of a totally odd K_4-subdivision plays an important role in both graph theory and combinatorial optimization. Sewell and Trotter (1993), Zang (1998) and Thomassen (1999) independently conjectured the existence of a polynomial time recognition algorithm. In this paper, we give the first polynomial time algorithm for solving this problem. We also study the the parity two disjoint rooted paths problem where we determine if there exists two vertex disjoint paths of a specified parity between two pairs of terminals. Using a similar technique, we give an O(|E(G)||V(G)| alpha(|E(G)|,|V(G)|)) algorithm for the parity two disjoint rooted paths problem on an input graph G, where alpha(|E(G)|,|V(G)|) is the inverse of the Ackermann function. We note that this clearly gives an algorithm for the well-known non-parity version of the two disjoint rooted paths problem. We then extend our approach to give a polynomial time algorithm which determines, for any fixed k, whether there exists a cycle of a given parity through k independent input edges. This generalizes the non-parity version of the algorithm. Thomassen[Combinatorica, 2001] gave a polynomial algorithm for the case $k=2$ and hoped to use this algorithm to recognize a totally odd K_4-subdivision. Our algorithm runs in O(|E(G)||V(G)| alpha(|E(G)|,|V(G)|)) for any fixed k. Finally, we give an O(|V(G)|^2 + |E(G)| alpha(|E(G)|,|V(G)| log |V(G)|)) algorithm to decide whether a graph contains k disjoint paths from A to B (with |A|=|B|=k) that are not all of the same parity. This answers a conjecture of Thomassen [Surveys in Combinatorics, 1999]. This problem arises from the study of totally odd K_4-subdivisions in 3-connected graphs [Surveys in Combinatorics, 1999]. =========================================================================== Highway Dimension, Shortest Paths, and Provably Efficient Algorithms --------------------------------------------------------------------------- Authors: Ittai Abraham (Microsoft Research) Amos Fiat (TAU) Andrew Goldberg (Microsoft Research) Renato Werneck (Microsoft Research) Topics: Algorithm Analysis, Graph Algorithms --------------------------------------------------------------------------- Computing shortest path driving directions has motivated many heuristics that answer queries on continental scale networks, with tens of millions of intersections, literally instantly, and with very low storage overhead. In this paper we complement the experimental evidence and give rigorous proofs of efficiency for many of the heuristics suggested over the past decade. We introduce the notion of highway dimension and show how low highway dimension gives a unified explanation for several seemingly unconnected algorithms. We also seek to explain the experimental evidence that road networks have low highway dimension by giving a natural generative model of road creation that produces such networks. =========================================================================== Limits on the Social Welfare of Maximal-In-Range Auction Mechanisms --------------------------------------------------------------------------- Authors: Dave Buchfuhrer (Caltech) Chris Umans (Caltech) Topics: Approximation Algorithms, Combinatorics, Complexity, Game Theory, Mechanism Design --------------------------------------------------------------------------- Many commonly-used auction mechanisms are maximal-in-range. We show that any "maximal-in-range" mechanism for n bidders cannot both approximate the social welfare with a ratio better than min(n, O(m^eta)) for any constant eta < 1/2 and run in polynomial time unless NP has polynomial circuits. This significantly improves upon a previous bound on the social welfare of polynomial time maximal-in-range mechanisms of 2n/(n+1) for constant n. The min(n, O(m^eta)) bound is tight, as a min(n, O(m^1/2)) approximation of the social welfare is achievable. =========================================================================== Counting Inversions, Offline Orthogonal Range Counting, and Related Problems --------------------------------------------------------------------------- Authors: Timothy M. Chan (U. Waterloo) Mihai Patrascu (AT&T Labs) Topics: Data Structures, Geometry --------------------------------------------------------------------------- We give an $O(n\sqrt{\lg n})$-time algorithm for counting the number of inversions in a permutation on $n$ elements. This improves a long-standing previous bound of $O(n\lg n/\lg\lg n)$ that followed from Dietz's data structure [WADS'89], and answers a question of Andersson and Petersson [SODA'95]. As Dietz's result is known to be optimal for the related dynamic rank problem, our result demonstrates a significant improvement in the \emph{offline} setting. Our new technique is quite simple: we perform a ``vertical partitioning'' of a trie (akin to van Emde Boas trees), and use ideas from external memory. However, the technique finds numerous applications: for example, we obtain \begin{itemize} \item in $d$ dimensions, an algorithm to answer $n$ offline orthogonal range counting queries in time $O(n\lg^{d-2+1/d}n)$; \item an improved construction time for online data structures for orthogonal range counting; \item an improved update time for the partial sums problem; \item faster Word RAM algorithms for finding the maximum depth in an arrangement of axis-aligned rectangles, and for the slope selection problem. \end{itemize} As a bonus, we also give a simple $(1+\eps)$-approximation algorithm for counting inversions that runs in linear time, improving the previous $O(n\lg\lg n)$ bound by Andersson and Petersson. =========================================================================== Near-Tight Bounds for Testing Ulam Distance --------------------------------------------------------------------------- Authors: Alexandr Andoni (MIT) Huy Le Nguyen (MIT) Topics: Approximation Algorithms, Pattern Matching, String Algorithms, Sublinear Algorithms --------------------------------------------------------------------------- We give near-tight bounds for estimating the edit distance between two non-repetitive strings (Ulam distance) with constant approximation, in sub-linear time. If the two strings are at edit distance $R$, then our algorithm runs in time $\tilde O(d/R+\sqrt{d})$ and outputs a constant approximation to R. We also prove a matching lower bound (up to logarithmic terms). Both upper and lower bounds are improvements over previous results from, respectively, [Andoni-Indyk-Krauthgamer, SODA'09] and [Batu-Ergun-Kilian-Magen-Raskhodnikova-Rubinfeld-Sami, STOC'03]. =========================================================================== Data-Specific Analysis of String Sorting --------------------------------------------------------------------------- Authors: Raimund Seidel (Saarland University) Topics: Algorithm Analysis, String Algorithms --------------------------------------------------------------------------- We consider the complexity of sorting strings in the model that counts comparisons between symbols and not just comparisons between strings. We show that for any set of strings $S$ the complexity of sorting $S$ can naturally be expressed in terms of the trie induced by $S$. This holds not only for lower bounds but also for the running times of various algorithms. Thus this ``data-specific'' analysis allows a direct comparison of different algorithms running on the same data. We give such ``data-specific'' analyses for various versions of quicksort and versions of mergesort. As a corollary we arrive at a very simple analysis of quicksorting random strings, which so far required rather sophisticated mathematical tools. As part of this we provide insights in the analysis of tries of random strings which may be interesting in their own right. =========================================================================== Graph genus and random partitions --------------------------------------------------------------------------- Authors: James R. Lee (University of Washington) Anastasios Sidiropoulos (University of Toronto) Topics: Approximation Algorithms, Geometry, Metric Embeddings, Probability, Topological Problems --------------------------------------------------------------------------- We study the quantitative geometry of graphs with small genus. In particular, we exhibit new, optimal random partitioning schemes for such graphs. Using these geometric primitives, we give exponentially improved dependence on genus for a number of problems like approximate max-flow/min-cut theorems, approximations for uniform and non-uniform Sparsest Cut, treewidth approximation, Laplacian eigenvalue bounds, Lipschitz extension theorems, and various embeddings into normed spaces. =========================================================================== Optimally Reconstructing Weighted Graphs Using Queries --------------------------------------------------------------------------- Authors: Hanna Mazzawi Topics: Combinatorics, Learning --------------------------------------------------------------------------- In this paper, we consider the problem of reconstructing a hidden graph with $m$ edges using additive queries. Given a graph $G=(V,E)$ and a set of vertices $S\subseteq V$, an additive query, $Q(S)$, asks for the number of edges in the subgraph induced by $S$. The information theoretic lower bound for the query complexity of reconstructing a graph with $n$ vertices and $m$ edges is $$ O\left(\frac{m\log \frac{n^2}{m}}{\log m}\right).$$ In this paper we give the first polynomial time algorithm with query complexity that matches this lower bound\footnote{In this paper, by optimal we mean asymptotically. That is, up to a constant factor.}. This solves the open problem by [S. Choi and J. Han Kim. Optimal Query Complexity Bounds for Finding Graphs. \emph{STOC} ,749--758 ,2008]. In the paper, we actually show an algorithm for the generalized problem of reconstructing weighted graphs. In the weighted case, an additive query, $Q(S)$, asks for the sum of weights of edges in the subgraph induces by $S$. The complexity of the algorithm also matches the information theoretic lower bound. =========================================================================== EDF-schedulability of synchronous periodic task systems is coNP-hard --------------------------------------------------------------------------- Authors: Friedrich Eisenbrand (Institute of Mathematics, EPFL, Lausanne, Switzerland) Thomas Rothvoß (Institute of Mathematics, EPFL, Lausanne, Switzerland) Topics: Complexity, Number Theory, Scheduling and Resource Allocation --------------------------------------------------------------------------- In the synchronous periodic task model, a set T_1,...,T_n of tasks is given, each releasing jobs of running time c_i and relative deadline d_i at each integer multiple of the period p_i. It is a classical result that Earliest Deadline First (EDF) is an optimal preemptive uni-processor scheduling policy. For constrained deadlines, i.e. d_i <= p_i, the EDF-schedule is feasible if and only if \[ \forall Q >= 0: \sum_{i=1}^n (\floor{(Q-d_i)/p_i} + 1) * c_i <= Q. \] Despite of an enormous amount of literature dealing with this topic, the complexity status of this test has remained unknown. We prove that testing EDF-schedulability of such a task system is coNP-hard. This solves Problem 2 from the survey "Open Problems in Real-time Scheduling" by Baruah & Pruhs. The hardness result is achieved by applying recent results on inapproximability of Diophantine approximation. =========================================================================== Algorithmic Lower Bounds for Problems Parameterized by Clique-width --------------------------------------------------------------------------- Authors: Fedor V. Fomin (University of Bergen) Petr A. Golovach (University of Bergen) Daniel Lokshtanov (University of Bergen) Saket Saurabh (University of Bergen) Topics: Algorithm Analysis, Complexity, Graph Algorithms --------------------------------------------------------------------------- Many NP-hard problems can be solved efficiently when the input is restricted to graphs of bounded tree-width or clique-width. In particular, by the celebrated result of Courcelle, every decision problem expressible in monadic second order logic is fixed parameter tractable when parameterized by the tree-width of the input graph. On the other hand if we restrict ourselves to graphs of clique-width at most $t$, then there are many natural problems for which the running time of the best known algorithms is of the form $n^{f(t)}$, where $n$ is the input length and $f$ is some function. It was an open question whether natural problems like Graph Coloring, Max-Cut, Edge Dominating Set, and Hamiltonian Path are fixed parameter tractable when parameterized by the clique-width of the input graph. As a first step toward obtaining lower bounds for clique-width parameterizations, in [SODA 2009], we showed that unless $FPT\neqW[1]$, there is no algorithm with run time $O(g(t)\cdot n^c)$, for some function $g$ and a constant $c$ not depending on $t$, for Graph Coloring, Edge Dominating Set and Hamiltonian Path. But the lower bounds obtained in [SODA 2009] are weak when compared to the upper bounds on the time complexity of the known algorithms for these problems when parameterized by the clique-width. In this paper, we obtain the asymptotically tight bounds for Max-Cut and Edge Dominating Set by showing that both problems 1. cannot be solved in time $f(t)n^{o(t)}$, unless Exponential Time Hypothesis (ETH) collapses; and 2. can be solved in time $n^{O(t)}$, where $f$ is an arbitrary function of $t$, on input of size $n$ and clique-width at most $t$. We obtain our lower bounds by giving non-trivial structure-preserving ``linear FPT reductions". =========================================================================== An Improved Competitive Algorithm for Reordering Buffer Management --------------------------------------------------------------------------- Authors: Noa Avigdor-Elgrabli (Technion) Yuval Rabani (Technion) Topics: Approximation Algorithms, Online problems --------------------------------------------------------------------------- We design and analyze an on-line reordering buffer management algorithm with improved $O\left(\frac{\log k}{\log\log k}\right)$ competitive ratio for non-uniform costs, where $k$ is the buffer size. This improves on the best previous result (even for uniform costs) of Englert and Westermann (ICALP 2005) giving $O(\log k)$ competitive ratio, which was also the best (off-line) approximation algorithm for this problem. Our analysis is based on an intricate dual fitting argument using a linear programming relaxation for the problem that we introduce in this paper. =========================================================================== Deterministic Algorithms for the Lovasz Local Lemma --------------------------------------------------------------------------- Authors: Karthekeyan Chandrasekaran (Gatech) Navin Goyal (Microsoft Research, India) Bernhard Haeupler (MIT) Topics: Algorithm Analysis, Combinatorics, Distributed and Parallel Computing, Probability, Random Structures --------------------------------------------------------------------------- The Lovasz Local Lemma (LLL) is a powerful result in probability theory that states that the probability that none of a set of bad events happens is nonzero if the probability of each event is small compared to the number of events that depend on it. It is often used in combination with the probabilistic method for non-constructive existence proofs. A prominent application is to k-CNF formulas, where LLL implies that, if every clause in the formula shares variables with at most d<2^k/e other clauses then such a formula has a satisfying assignment. Recently, a randomized algorithm to efficiently construct a satisfying assignment was given by Moser. Subsequently Moser and Tardos gave a randomized algorithm to construct the structures guaranteed by the LLL in a very general algorithmic framework. We address the main problem left open by Moser and Tardos of derandomizing these algorithms efficiently. Specifically, for a k-CNF formula with m clauses and d<= 2^{k/(1+\eps)}/e for some \eps\in (0,1), we give an algorithm that finds a satisfying assignment in time \tilde{O}(m^{2(1+1/\eps)}). This improves upon the deterministic algorithms of Moser and of Moser-Tardos with running time m^{\Omega(k^2)} which is superpolynomial for k=\omega(1) and upon other previous algorithms which work only for d<= 2^{k/16}/e. Our algorithm works efficiently for a general version of LLL under the algorithmic framework of Moser and Tardos, and is also parallelizable, i.e., has polylogarithmic running time using polynomially many processors. =========================================================================== Streaming Algorithms for extent problems in high dimensions --------------------------------------------------------------------------- Authors: Pankaj K Agarwal (Department of Computer Science, Duke University) R. Sharathkumar (Department of Computer Science, Duke University) Topics: Approximation Algorithms, Data Structures, Geometry, Streaming Algorithms --------------------------------------------------------------------------- We develop streaming algorithms for maintaining extent measures of a stream S of n points in R^d. We focus on designing streaming algorithms that use polynomial in d (poly(d)) and sub-linear in n space. For the problems of computing diameter, width and minimum enclosing ball of S, we obtain lower bounds on the worst-case approximation ratio of any streaming algorithm that uses poly(d) space. On the positive side, we design an insertion-only data structure called the blurred ball cover that maintains a set C \subseteq S of $O(1/eps^3 log 1/\eps)$ points. We show that blurred ball cover can be used for answering approximate farthest-point queries and maintaining approximate minimum enclosing ball and diameter of S. The size of blurred ball cover is linear in d and independent of n. =========================================================================== Algorithms and Complexity for Periodic Real-Time Scheduling --------------------------------------------------------------------------- Authors: Vincenzo Bonifaci (University of L'Aquila and Sapienza University of Rome, Italy) Ho-Leung Chan (Max-Planck-Insitut fuer Informatik, Saarbruecken, Germany) Alberto Marchetti-Spaccamela (Sapienza University of Rome, Italy) Nicole Megow (Max-Planck-Insitut fuer Informatik, Saarbruecken, Germany) Topics: Approximation Algorithms, Number Theory, Scheduling and Resource Allocation --------------------------------------------------------------------------- We investigate the preemptive scheduling of periodic tasks with hard deadlines. We show that, even in the uniprocessor case, no polynomial time algorithm can test the feasibility of a task system within a constant speedup bound, unless P=NP. This result contrasts with recent results for sporadic task systems. For two special cases, synchronous task systems and systems with a constant number of different task types, we provide the first polynomial time constant-speedup feasibility tests for multiprocessor platforms. Furthermore, we show that the problem of testing feasibility is coNP-hard for synchronous multiprocessor tasks systems. The complexity of some of these problems has been open for a long time. We also propose a profit maximization variant of the feasibility problem, where every task has a non-negative profit, and the goal is to find a subset of tasks that can be scheduled feasibly with maximum profit. We give the first constant-speed, constant-approximation algorithm for the case of synchronous task systems, together with related hardness results. =========================================================================== Cache-Oblivious Dynamic Dictionaries with Optimal Update/Query Tradeoff --------------------------------------------------------------------------- Authors: Gerth Stølting Brodal (Aarhus University) Erik D. Demaine (MIT) Jeremy T. Fineman (MIT) John Iacono (Polytechnic Institute of NYU) Stefan Langerman (Université Libre de Bruxelles) J. Ian Munro (University of Waterloo) Topics: Data Structures --------------------------------------------------------------------------- The cache-oblivious model has emerged as the best model of a modern multilevel memory hierarchy. The dynamic dictionary--a data structure that supports insertions, deletions, and predecessor queries--is the most fundamental of data structures. Several existing cache-oblivious dynamic dictionaries achieve O(log_B N) memory transfers per operation, where N is the number of items stored and B is the block size, which matches the classic B-tree data structure. One recent structure achieves the same query bound and a sometimes-better amortized update bound of O(1/B^Theta(1/(log log B)^2) log_B N + (log^2 N)/B) memory transfers. This paper presents a new data structure, the xDict, implementing predecessor queries in O((log_B (N/M))/epsilon) worst-case memory transfers and insertions and deletions in O((log_B (N/M))/(epsilon B^(1-epsilon))) amortized memory transfers, for any constant epsilon with 0 < epsilon < 1. For example, the xDict achieves subconstant amortized update cost when N = M B^o(B^(1-epsilon)), whereas the B-tree's Theta(log_B N) is always superconstant, and the previously obtained Theta((log_B N)/B^Theta(1/(log log B)^2) + (log^2 N) is subconstant only when N = o(2^sqrt(B)). The xDict attains a provably optimal tradeoff between insertions and queries in the cache-oblivious model. =========================================================================== Testing additive integrality gaps --------------------------------------------------------------------------- Authors: Friedrich Eisenbrand (EPFL, Switzerland) Nicolai Hähnle (EPFL, Switzerland) Dömötör Pálvölgyi (EPFL, Switzerland) Gennady Shmonin (EPFL, Switzerland) Topics: Geometry, Mathematical Programming --------------------------------------------------------------------------- We consider the problem of testing whether the maximum integrality gap of a family of integer programs in standard form is bounded by a given constant. This can be viewed as a generalization of the integer rounding property, which can be tested in polynomial time if the number of constraints is fixed. It turns out that this generalization is NP-hard even if the number of constraints is fixed. However, if the objective is the all-one vector, then one can test whether the additive gap is bounded by a constant γ, in polynomial time if the number of constraints is fixed. =========================================================================== Reconstructing approximate phylogenetic trees from quartet samples --------------------------------------------------------------------------- Authors: Sagi Snir (University of Haifa) Raphael Yuster (University of Haifa) Topics: Approximation Algorithms, Bioinformatics, Graph Algorithms --------------------------------------------------------------------------- The reconstruction of evolutionary trees (also known as {\em phylogenies}) is central to many problems in Biology. Accurate phylogenetic reconstruction methods are currently limited to a maximum of few dozens of species. Therefore, in order to construct a tree over larger sets of species, a method capable of inferring accurately trees over small, overlapping sets, and subsequently merging these sets into a tree over the complete set, is required. A quartet tree is the smallest informative piece of information and quartet based methods are based on combining quartet trees into a big tree. However, even this case is NP-hard, and even when the set of quartet trees is compatible (agree on a certain tree). The general problem of approximating quartets, or {\em maximum quartet consistency} (MQC), even for compatible inputs, is open for nearly twenty years. Despite its importance, the only rigorous results for approximating quartets are the naive $1/3$ approximation that applies to the general case and a PTAS when the input is the complete set of all ${n \choose 4}$ possible quartets. Even when it is possible to determine the correct quartet induced by every four taxa, the time needed to generate the complete set of all ${n \choose 4}$ quartets may be impractical. A faster approach is to sample at random just $m \ll {n \choose 4}$ quartets, and provide this sample as an input. In this work we present the first approximation algorithm whose guaranteed approximation is strictly better than $1/3$ when the input is any random sample of $m$ quartets. The approximation ratio we obtain is $0.425$ for general $m$, and $0.468$ when $m = \tilde{\omega}(n^2)$. An important ingredient in our algorithm involves solving a weighted MaxCut in a certain graph induced by the set of input quartets. We also show an extension of the PTAS algorithm to handle dense, rather than complete, inputs. =========================================================================== Fast distance multiplication of unit-Monge matrices --------------------------------------------------------------------------- Authors: Alexander Tiskin (University of Warwick) Topics: Algebra, Algorithm Analysis, Compression, Graph Algorithms, Optimization, Pattern Matching, String Algorithms --------------------------------------------------------------------------- Monge matrices play an important role in optimisation, graph and string algorithms. Distance multiplication of two Monge matrices of size $n$ can be performed in time $O(n^2)$. Motivated by applications to string algorithms, we introduced in a previous work a subclass of Monge matrices, that we call \emph{simple unit-Monge} matrices. Our previous algorithm for distance multiplication of simple unit-Monge matrices runs in time $O(n^{1.5})$. Landau asked whether this problem can be solved in linear time. In the current work, we give an algorithm running in time $O(n \log n)$, thus approaching an answer to Landau's question within a logarithmic factor. The new algorithm implies immediate improvements in running time for a number of algorithms on strings and graphs. In particular, we obtain an algorithm for finding a maximum clique in a circle graph in time $O(n \log^2 n)$, and a surprisingly efficient algorithm for comparing compressed strings. We also point to potential applications in group theory, by making a connection between unit-Monge matrices and Coxeter monoids. We conclude that unit-Monge matrices are a fascinating object and a powerful tool, that deserves further study from both the mathematical and the algorithmic viewpoints. =========================================================================== Applications of Forbidden 0-1 Matrices to Search Trees and Path Compression-Based Data Structures --------------------------------------------------------------------------- Authors: Seth Pettie (University of Michigan) Topics: Algorithm Analysis, Combinatorics, Data Structures --------------------------------------------------------------------------- In this paper we improve, reprove, and simplify a variety of theorems concerning the performance of data structures based on path compression and search trees. We apply a technique very familiar to computational geometers but still foreign to many researchers in (non-geometric) algorithms and data structures, namely, to bound the complexity of an object via its forbidden substructures. To analyze an algorithm or data structure in the forbidden substructure framework one proceeds in three discrete steps. First, one transcribes the behavior of the algorithm as some combinatorial object $M$; for example, $M$ may be a graph, sequence, permutation, matrix, set system, or tree. (The size of $M$ should ideally be linear in the running time.) Second, one shows that $M$ excludes some forbidden substructure $P$, and third, one bounds the size of any object avoiding this substructure. The power of this framework derives from the fact that $M$ lies in a more pristine environment and that upper bounds on the size of a $P$-free object $M$ may be taken ``off the shelf.'' All of our proofs begin by transcribing the individual operations of a dynamic data structure as a 0-1 matrix $M$, where one axis of $M$ corresponds to space (objects in the data structure) and the other to time. Based on elementary properties of the data structure we observe that $M$ excludes some 0-1 submatrix $P$, which implies an upper bound on the weight (number of 1s) of $M$ and a corresponding upper bound on the running time of the data structure. Among our results, we present the first asymptotically sharp bound on the length of arbitrary path compressions on arbitrary trees, improving analyses of Tarjan, Seidel and Sharir. We reprove the linear upper bounds on postordered path compressions, due to Lucas and Loebel and Nesetril, the linear bound on deque-ordered path compressions, due to Buchsbaum, Sundar, and Tarjan, and the linearity of sequential access in splay trees, originally due to Tarjan. We disprove a conjecture of Aronov et al. related to the efficiency of their data structure for half-plane proximity queries and provide a significantly cleaner analysis of their structure. Finally, we give tight bounds on the number of ``right twists'' in a binary search tree, closing a problem of Sundar. With the exception of the sequential access theorem, all our proofs are exceptionally simple. =========================================================================== A deterministic truthful PTAS for scheduling related machines --------------------------------------------------------------------------- Authors: George Christodoulou (Max-Planck Institute for Informatics) Annamaria Kovacs (Department of Informatics, Goethe University, Frankfurt M.) Topics: Approximation Algorithms, Economics, Game Theory, Mechanism Design, Scheduling and Resource Allocation --------------------------------------------------------------------------- Scheduling on related machines ($Q||C_{\max}$) is one of the most important problems in the field of Algorithmic Mechanism Design. Each machine is controlled by a selfish agent and her valuation can be expressed via a single parameter, her {\em speed}. In contrast to other similar problems, Archer and Tardos~\cite{AT01} showed that an algorithm that minimizes the makespan can be truthfully implemented, although in exponential time. On the other hand, if we leave out the game-theoretic issues, the complexity of the problem has been completely settled --- the problem is strongly NP-hard, while there exists a PTAS~\cite{HS88,ES04}. This problem is the most well studied in single-parameter algorithmic mechanism design. It gives an excellent ground to explore the boundary between truthfulness and efficient computation. Since the work of Archer and Tardos, quite a lot of deterministic and randomized mechanisms have been suggested. Recently, a breakthrough result~\cite{DDDR08} showed that a randomized truthful PTAS exists. On the other hand, for the deterministic case, the best known approximation factor is 2.8~\cite{Kov05,Kov07}. It has been a major open question whether there exists a deterministic truthful PTAS, or whether truthfulness has an essential, negative impact on the computational complexity of the problem. In this paper we give a definitive answer to this important question by providing a truthful {\em deterministic} PTAS. =========================================================================== PTAS for maximum weight independent set problem with random weights in bounded degree graphs --------------------------------------------------------------------------- Authors: David Gamarnik (MIT) David Goldberg (MIT) Theophane Weber (MIT) Topics: Algorithm Analysis, Approximation Algorithms, Combinatorics, Complexity, Graph Algorithms, Graph Theory, Optimization, Probability, Random Structures --------------------------------------------------------------------------- Finding largest independent set in a graph is a notoriously dicult NP-complete combinato- rial optimization problem. Moreover, even for graphs with largest degree 3, no polynomial time approximation algorithm exists with 1:0071-factor approximation guarantee, unless P = NP, [BK99]. We consider the related problem of finding maximum weight independent set in bounded degree graph, when the node weights are generated i.i.d. from a common distribution. Sur- prisingly, we discover that the problem becomes tractable for certain distributions. Specifically, we construct PTAS (Polynomial-Time Approximation Scheme) for the case of exponentially distributed weights and arbitrary graphs with degree at most 3. We extend our result to graphs with larger constant degrees but for distributions which are mixtures of exponential distribu- tions. At the same time we prove that PTAS does not exist for the case of exponentially distributed weights for graphs with suciently large but bounded degree, unless P=NP. Our algorithm, cavity expansion, is new and is based on combination of several powerful ideas, in- cluding recent deterministic approximation algorithms for counting on graphs and local weak convergence/correlation decay methods. =========================================================================== Distributed Agreement with Optimal Communication Complexity --------------------------------------------------------------------------- Authors: Seth Gilbert (EPFL) Dariusz Kowalski (University of Liverpool) Topics: Distributed and Parallel Computing --------------------------------------------------------------------------- We consider the problem of fault-tolerant agreement in a crash-prone synchronous system. We present a new randomized consensus algorithm that achieves optimal communication efficiency, using only O(n) bits of communication, and terminates in (almost) optimal time O(log n), with high probability. These results also imply an efficient consensus algorithm for partially synchronous networks. Finally, the same techniques also yield a randomized gossip protocol that terminates in O(log*n) rounds using O(n) messages (with bit complexity that depends on the data being gossiped). =========================================================================== Synchrony and Asynchrony in Neural Networks --------------------------------------------------------------------------- Authors: Fabian Kuhn (MIT CSAIL) Konstantinos Panagiotou (Max-Planck-Institute for Informatics) Joel Spencer (Courant Institute, New York) Angelika Steger (ETH Zurich) Topics: Markov Chains, Probability, Random Graphs, Random Structures --------------------------------------------------------------------------- The dynamics of large networks is an important and fascinating problem. Key examples are the Internet, social networks, and the human brain. In this paper we consider a model introduced by DeVille and Peskin (Bulletin of Mathematical Biology, 2008) for a stochastic pulse-coupled neural network. The key feature and novelty in their approach is that they describe the interactions of a neuronal system as a discrete-state stochastic dynamical network. This idealization has two benefits: it captures essential features of neuronal behavior, and it allows the study of spontaneous synchronization, an important phenomenon in neuronal networks that is well-studied but unfortunately far from being well-understood. In synchronous behavior the firing of one neuron leads to the firing of other neurons, which in turn may set off a chain reaction that often involves a substantial proportion of the neurons. In this paper we analyze rigorously their model. In particular, by applying methods and tools that are frequently used in theoretical computer science and discrete mathematics, we provide a very precise picture of the dynamics and the evolution of the given system. Among other results, we answer the questions of DeVille and Peskin about the actual parameter settings resp. thresholds for which changes between synchronous and asynchronous behavior occur, and determine the conditions that trigger a ’spontaneous’ transition from one state to another. =========================================================================== Belief Propagation for Min-cost Network Flow: Convergence & Correctness --------------------------------------------------------------------------- Authors: David Gamarnik (MIT) Devavrat Shah (MIT) Yehua Wei (MIT) Topics: Algorithm Analysis, Approximation Algorithms, Graph Algorithms, Optimization --------------------------------------------------------------------------- We formulate a Belief Propagation (BP) algorithm in the context of capacitated min-cost network flow problem. Unlike most of the instances of BP studied in the past for a generic continuous optimization problem, we find that the messages of BP in the min- cost flow problem context are piecewise linear functions. We prove that BP converges to the optimal solution in pseudo-polynomial time, provided that the optimal solution is unique and the problem input is integral. Further, we present a simple modification of the BP algorithm which gives a fully polynomial-time approximation scheme (FPRAS) of min-cost flow problem. This is the first such fully-polynomial time instance of BP. We believe that this method to modify BP for obtaining fully polynomial-tiime implementation should be applicable more generally. =========================================================================== Pricing Randomized Allocations --------------------------------------------------------------------------- Authors: Patrick Briest (Cornell University) Shuchi Chawla (University of Wisconsin - Madison) Robert Kleinberg (Cornell University) S. Matthew Weinberg (Cornell University) Topics: Approximation Algorithms, Economics, Mechanism Design --------------------------------------------------------------------------- Randomized mechanisms, which map a set of bids to a probability distribution over outcomes rather than a single outcome, are an important but ill-understood area of computational mechanism design. We investigate the role of randomized outcomes (henceforth, “lotteries”) in the context of a fundamental and archetypical multi-parameter mechanism design problem: selling heterogeneous items to unit-demand bidders. To what extent can a seller improve his revenue by pricing lotteries rather than items, and does this modification of the problem affect its computational tractability? Our results show that the answers to these questions hinge on whether consumers can purchase only one lottery (the buy-one model) or purchase any set of lotteries and receive an independent sample from each (the buy-many model). In the buy-one model, there is a polynomial-time algorithm to compute the revenue-maximizing envy-free prices (thus overcoming the inapproximability of the corresponding item pricing problem) and the revenue of the optimal lottery system can exceed the revenue of the optimal item pricing by an unbounded factor as long as the number of item types exceeds 4. In the buy-many model with n item types, the profit achieved by lottery pricing can exceed item pricing by a factor of O(log n) but not more, and optimal lottery pricing cannot be approximated within a factor of O(n^eps) for some eps > 0, unless NP has subexponential-time randomized algorithms. Our lower bounds rely on a mixture of geometric and algebraic techniques, whereas the upper bounds use a novel rounding scheme to transform a mechanism with randomized outcomes into one with deterministic outcomes while losing only a bounded amount of revenue. =========================================================================== Covering a symmetric crossing supermodular function with partition constraints --------------------------------------------------------------------------- Authors: Attila Bernáth (MTA-ELTE Egerváry Research Group, Budapest, Hungary) Roland Grappe (Laboratoire G-SCOP, Grenoble, France) Zoltán Szigeti (Laboratoire G-SCOP, Grenoble, France) Topics: Combinatorics, Graph Algorithms, Graph Theory, Optimization --------------------------------------------------------------------------- Given a symmetric crossing supermodular set function $p$ on $V$ and a partition $\mathcal{P}$ of $V$, we solve the problem of finding a graph $G=(V,E)$ having edges only between the classes of $\mathcal{P}$ such that each cut $X$ contains at least as many edges of $G$ as the function value $p(X)$. The objective is to minimize the number of edges of $G$. This problem is a common generalization of the global edge-connectivity augmentation of a graph with partition constraints, which was solved by Bang-Jensen, Gabow, Jord\'an and Szigeti and the problem of covering a symmetric crossing supermodular set function solved by Bencz\'ur and Frank. Our problem can be considered as an abstract form of the problem of global edge-connectivity augmentation of a hypergraph with multipartite graph, which was earlier solved by the authors. =========================================================================== A Max-Flow/Min-Cut Algorithm for a Class of Wireless Networks --------------------------------------------------------------------------- Authors: S. M. Sadegh Tabatabaei Yazdi (Student, Texas A&M university) Serap A. Savari (Professor, Texas A&M university) Topics: Combinatorics, Information Theory, Optimization --------------------------------------------------------------------------- The linear deterministic model of relay channels is a generalization of the traditional directed network model which has become popular in the study of the flow of information over wireless communication networks. The max-flow/min-cut theorem of Ford and Fulkerson has recently been extended to this wireless relay model. This result was first proved by a random coding scheme over large blocks of transmitted signals. We demonstrate the same result with a deterministic, polynomial-time algorithm which takes as input a single transmitted signal instead of a long block of signals. The max-flow/min-cut theorem of Ford and Fulkerson is related to a number of famous results in combinatorics including Hall's marriage theorem. Hall's marriage theorem is a special case of a well-known result in matroid theory and in transversal theory named the Rado-Hall theorem. We show that that the max-flow/min-cut theorem for linear deterministic relay networks is connected to (1) an extension of the Rado-Hall theorem applied to column-partitioned matrices into a two-dimensional transversal theorem for block matrices and (2) a combinatorial result on sequences of block matrices. =========================================================================== Vertices of Degree k in Random Maps --------------------------------------------------------------------------- Authors: Daniel Johannsen (Max-Planck-Institute for Informatics) Konstantinos Panagiotou (Max-Planck-Institute for Informatics) Topics: Combinatorics, Graph Theory, Probability, Random Graphs, Random Structures --------------------------------------------------------------------------- This work is devoted to the study of the typical structure of a random map. Maps are planar graphs embedded in the plane, and are commonly used to describe the topology of geometric arrangements. In particular, the class of all 3-connected planar maps is combinatorially equivalent to the class of all 3-dimensional convex polyhedra. Since the pioneering work of Tutte (Canadian Journal of Mathematics, 1963), maps have become very popular combinatorial objects, and in the meantime a rich theory studying various aspects of maps has evolved. However, much less is known about statistical properties of random maps, i.e., maps drawn uniformly at random from the class of all maps with a given number of edges. A major achievement in this context is the precise description of the so-called core-size of a random map, which was provided by Banderier, Flajolet, Schaeffer, and Soria (Random Structures & Algorithms, 2001). Among several other results, they showed that a random map contains typically a giant (i.e., linear-size) biconnected submap. In this work we study the degree sequences of random maps from families of a certain type, which, among others, includes fundamental map classes like those of biconnected maps, 3-connected maps, and triangulations. In particular, we develop a general framework that allows us to derive relations and exact asymptotic expressions for the expected number of vertices of degree k in random maps from these classes, and also provide accompanying large deviation statements. Extending the work of Gao and Wormald (Combinatorica, 2003) on random general maps, we obtain as results of our framework precise information about the number of vertices of degree k in random biconnected, 3-connected, loopless, and bridgeless maps. =========================================================================== Bidimensionality and Kernels --------------------------------------------------------------------------- Authors: Fedor V. Fomin (Department of Informatics, University of Bergen, Norway) Daniel Lokshtanov (Department of Informatics, University of Bergen, Norway) Saket Saurabh (Department of Informatics, University of Bergen, Norway) Dimitrios M. Thilikos (Department of Mathematics, National and Kapodistrian University of Athens) Topics: Combinatorics, Graph Algorithms, Graph Theory --------------------------------------------------------------------------- Bidimensionality theory appears to be a powerful framework in the development of meta-algorithmic techniques. It was introduced by Demaine et al. [J. ACM 2005] as a tool to obtain sub-exponential time parameterized algorithms for bidimensional problems on $H$-minor free graphs. Demaine and Hajiaghayi [SODA 2005] extended the theory to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this paper, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of {\sl polynomial kernels} for parameterized problems. In parameterized complexity, each problem instance comes with a parameter $k$ and the parameterized problem is said to admit a {\it polynomial kernel} if there is a polynomial time algorithm, called a {\em kernelization} algorithm, that reduces the input instance to an equivalent instance (called {\em kernel}) with size bounded by a polynomial in $k$. We show that ``essentially'' all bidimensioanl problems not only have sub-exponential time algorithms and PTASs but they {\em also} have polynomial kernels, partially answering an open question from [J. ACM 2005] where the existence of linear kernels was conjectured for the first time. In particular, we prove that every minor (resp. contraction) bidimensional problem that satisfies the separation property and is of finite integer index, admits a quadratic kernel for classes of graphs that exclude a fixed graph (resp. an apex graph $H$) $H$ as a minor. Recently, Bodlaender et al.~[FOCS 2009] laid the foundation for obtaining meta-algorithmic results for kernelization and showed that various problems satisfying some logical and compactness properties have polynomial, even linear kernels on graphs of bounded genus. With the use of bidimensionality and hypergraph-based combinatorial arguments, we are able to extended some of these results to minor-free and apex-minor-free graphs. Our results imply that multitude of bidimensional problems, which include {\sc Dominating Set}, {\sc Feedback vertex set}, {\sc Edge Dominating set}, {\sc Vertex Cover}, {\sc $r$-Dominating Set}, {\sc Connected Dominating Set}, {\sc Cycle Packing}, {\sc connected vertex cover}, {\sc Almost Constant Treewidth}, and many other vertex covering and packing problems, admit quadratic kernels on the corresponding graph classes. For most of these problems no polynomial kernels on $H$-minor-free graphs were know prior to our work. =========================================================================== Flow-Cut Gaps for Integer and Fractional Multiflows --------------------------------------------------------------------------- Authors: Chandra Chekuri (University of Illinois, Urbana-Champaign) Bruce Shepherd (McGill University) Christophe Weibel (McGill University) Topics: Graph Theory, Optimization --------------------------------------------------------------------------- Consider a routing problem instance consisting of a demand graph H=(V,E(H)) and a supply graph G=(V,E(G)). If the pair obeys the cut condition, then the flow-cut gap for this instance is the minimum value C such that there exists a feasible multiflow for H if each edge of G is given capacity C. It is well-known that the flow-cut gap may be greater than 1 even in the case where G is the (series-parallel) graph K_{2,3}. In this paper we are primarily interested in the "integer" flow-cut gap. What is the minimum value C such that there exists a feasible integer valued multiflow for H if each edge of G is given capacity C? We formulate a conjecture that states that the integer flow-cut gap is quantitatively related to the fractional flow-cut gap. In particular this strengthens the well-known conjecture that the flow-cut gap in planar and minor-free graphs is O(1) to suggest that the integer flow-cut gap is O(1). We give several technical tools and results on non-trivial special classes of graphs to give evidence for the conjecture and further explore the "primal" method for understanding flow-cut gaps; this is in contrast to and orthogonal to the highly successful metric embeddings approach. Our results include the following: * Let G be obtained by series-parallel operations starting from an edge st, and consider orienting all edges in G in the direction from s to t. A demand is semi-compliant if its endpoints are joined by a directed path in the resulting oriented graph. We show that if the cut condition holds for a semi-compliant instance and G+H is Eulerian, then an integral routing of H exists. This result includes as a special case, routing on a ring but is not a special case of the Okamura-Seymour theorem. * Using the above result, we show that the integer flow-cut gap in series-parallel graphs is 5. We also give an explicit class of routing instances that shows via elementary calculations that the flow-cut gap in series-parallel graphs is at least 2; this is motivated by and simplifies the proof by Lee and Raghavendra. * The integer flow-cut gap in k-Outerplanar graphs is c^{O(k)} for some fixed constant c. * A very simple proof that the flow-cut gap is O(\log k^*) where k^* is the size of a vertex cover in H; this was previously shown by Günlük via a more intricate proof. =========================================================================== Testing monotone high-dimensional distributions --------------------------------------------------------------------------- Authors: Michal Adamaszek (University of Warwick) Artur Czumaj (University of Warwick) Christian Sohler (TU Dortmund) Topics: Property Testing --------------------------------------------------------------------------- We study the task of testing properties of probability distributions. We consider a scenario in which we have access to independent samples of an unknown distribution D with infinite or uncountable support. Our goal is to test whether D has a given distribution or it is \epsilon-far from it (in the statistical distance, with the L_1-distance measure). It is not difficult to see that for many natural distributions on infinite or uncountable domains, no testing algorithm can exist and the central objective of our study is to understand if there are any nontrivial distributions that can be efficiently tested. For example, it is easy to see that there is no testing algorithm that tests if a given probability distribution on [0,1] is uniform. We show however, that if some additional information about the input distribution is known, testing uniform distribution is possible. We extend the recent result about testing uniformity for monotone distributions on Boolean n-dimensional cubes by Rubinfeld and Servedio (STOC’2005) to the case of continuous [0,1]^n cubes. We show that if a distribution D on [0,1]^n is monotone, then one can test if D is uniform with the sample complexity O(n/\epsilon^2). This result is optimal up to a polylogarithmic factor. =========================================================================== The rank of diluted random graphs --------------------------------------------------------------------------- Authors: bordenave (CNRS - Univ. Toulouse) lelarge (INRIA - ENS) Topics: Graph Algorithms, Probability, Random Graphs, Random Structures --------------------------------------------------------------------------- We investigate the rank of the adjacency matrix of large diluted random graphs: for a sequence of graphs converging locally to a tree, we give new formulas for the asymptotic of the multiplicity of the eigenvalue $0$. In particular, the result depends only on the limiting tree structure, showing that the normalized rank is 'continuous at infinity'. Our work also gives a new formula for the mass at zero of the spectral measure of a Galton-Watson tree. Our techniques of proofs borrow ideas from analysis of algorithms, random matrix theory, statistical physics and analysis of Schr\"odinger operators on trees. =========================================================================== Utilitarian Mechanism Design for Multi-Objective Optimization --------------------------------------------------------------------------- Authors: Fabrizio Grandoni (Universita di Roma Tor Vergata) Piotr Krysta (University of Liverpool) Stefano Leonardi (Sapienza Universita di Roma) Carmine Ventre (University of Liverpool) Topics: Approximation Algorithms, Economics, Game Theory, Internet and Network Algorithms, Mechanism Design, Optimization --------------------------------------------------------------------------- In a classic optimization problem the complete input data is assumed to be known to the algorithm. This assumption may not be true anymore in optimization problems motivated by the Internet where part of the input data is private knowledge of independent selfish agents. The goal of algorithmic mechanism design is to provide (in polynomial time) a solution to the optimization problem and a set of incentives for the agents such that disclosing the input data is a dominant strategy for the agents. In case of NP-hard problems, the solution computed should also be a good approximation of the optimum. In this paper we focus on mechanism design for multi-objective optimization problems. In this setting we are given a main objective function, and a set of secondary objectives which are modeled via budget constraints. Multi-objective optimization is a natural setting for mechanism design as many economical choices ask for a compromise between different, partially conflicting, goals. The main contribution of this paper is showing that two of the main tools for the design of approximation algorithms for multiobjective optimization problems, namely approximate Pareto curves and Lagrangian relaxation, can lead to truthful approximation schemes. By exploiting the method of approximate Pareto curves, we devise truthful FPTASs for multiobjective optimization problems whose exact version admits a pseudo-polynomial-time algorithm, as for instance the multi-budgeted versions of minimum spanning tree, shortest path, maximum (perfect) matching, and matroid intersection. Our construction also applies to multi-dimensional knapsack and multi-unit combinatorial auctions. Our FPTASs compute a (1 + epsilon)-approximate solution violating each budget constraint by a factor (1 + epsilon). For the case of (non-perfect) matchings we also present a PTAS (not violating any constraint), which combines the approach above with a novel monotone way to guess the heaviest edges in the optimum solution. Finally, we present a universally truthful Las Vegas PTAS for minimum spanning tree with a single budget constraint. This result is based on the Lagrangian relaxation method, in combination with our monotone guessing step and with a random perturbation step (ensuring low expected running time in a way similar to the smoothed analysis of algorithms). All the mentioned results match the best known approximation ratios, which are however obtained by non-truthful algorithms. =========================================================================== Property Testing and Parameter Testing for Permutations --------------------------------------------------------------------------- Authors: Carlos Hoppen (IME, USP, São Paulo, Brazil) Yoshiharu Kohayakawa (IME, USP, São Paulo, Brazil) Carlos G. T. de A. Moreira (IMPA, Rio de Janeiro, Brazil) Rudini M. Sampaio (DC, UFC, Fortaleza, Brazil) Topics: Combinatorics, Probability, Property Testing, Random Structures, Sublinear Algorithms --------------------------------------------------------------------------- There has been great interest in deciding whether a combinatorial structure satisfies some property, or in estimating the value of some numerical function associated with this combinatorial structure, by considering only a randomly chosen substructure of sufficiently large, but constant size. These problems are called property testing and parameter testing, where a property or parameter is said to be testable if it can be estimated accurately in this way. The algorithmic appeal is evident, as this leads to reliable constant-time randomized estimators. Our paper addresses property testing and parameter testing for permutations. We give a permutation counterpart of a famous result by Alon and Shapira stating that every monotone graph property is testable. Moreover, we develop a theory of convergence of permutation sequences, which is used to characterize testable permutation parameters along the lines of the work of Borgs et al. in the case of graphs. This theory is interesting for its own sake, as it describes the closure of the set of all permutations as a special class of Lebesgue measurable functions in $[0,1]^2$, which in turn may be used to define a new model of random permutations. =========================================================================== Monotonicity in Bargaining Networks --------------------------------------------------------------------------- Authors: Yossi Azar Nikhil Devanur Kamal Jain Yuval Rabani Topics: Algorithm Analysis, Economics, Game Theory --------------------------------------------------------------------------- We study bargaining networks, discussed in a recent paper of Kleinberg and Tardos \cite{KT}, from the perspective of cooperative game theory. In particular we examine two solution concepts, the nucleolus and the core center. Both solution concepts define unique solutions, so they provide testable predictions. In general coalitional games, both solutions are weakly monotone, but they are not strongly monotone. We define a new monotonicity property that is a natural axiom of any bargaining game solution, and we prove that both the nucleolus and the core center satisfy this monotonicity property. Our proofs are based on a primal-dual argument (for the nucleolus) and on the FKG inequality (for the core center). We further observe some qualitative differences between the two solution concepts. In particular, there are cases where a strict version of our monotonicity property is a natural axiom, but only the core center satisfies it. On the other hand, the nucleolus is easy to compute, whereas computing the core center is \#P-hard (yet it can be approximated in polynomial time). =========================================================================== A Lower Bound for Succinct Rank Queries --------------------------------------------------------------------------- Authors: Mihai Patrascu (AT&T Labs) Topics: Complexity, Compression, Data Structures, Information Theory --------------------------------------------------------------------------- The rank problem in succinct data structures is to preprocess an array A[1..n] of bits into a data structure using as close to n bits as possible, and answer queries of the form rank(k) = Sum_{i=1..k} A[i]. The problem has been intensely studied, and features as a subroutine in a majority of succinct data structures. We show that in the cell probe model with w-bit cells, if rank takes t time, the space of the data structure must be at least n + n/w^O(t) bits. This redundancy/query trade-off is essentially optimal, matching our upper bound from [FOCS'08]. =========================================================================== Amplified Hardness of Approximation for VCG-Based Mechanisms --------------------------------------------------------------------------- Authors: Shaddin Dughmi (Stanford University) Hu Fu (Cornell University) Robert Kleinberg (Cornell University) Topics: Approximation Algorithms, Complexity, Economics, Game Theory, Mechanism Design --------------------------------------------------------------------------- If a two-player social welfare maximization problem does not admit a PTAS, we prove that any maximal-in-range truthful mechanism that runs in polynomial time cannot achieve an approximation factor better than 1/2. Moreover, for the k-player version of the same problem, the hardness of approximation improves to 1/k under the same two-player hardness assumption. (We note that 1/k is achievable by a trivial deterministic maximal-in-range mechanism.) This hardness result encompasses not only deterministic maximal-in-range mechanisms, but also all universally-truthful randomized maximal in range algorithms, as well as a class of strictly more powerful truthful-in-expectation randomized mechanisms recently introduced by Dobzinski and Dughmi. Our result applies to any class of valuation functions that satisfies some minimal closure properties. These properties are satisfied by the valuation functions in all well-studied APX-hard social welfare maximization problems, such as coverage, submodular, and subadditive valuations. We also prove a stronger result for universally-truthful maximal-in-range mechanisms. Namely, even for the class of budgeted additive valuations, which admits an FPTAS, no such mechanism can achieve an approximation factor better than 1/k in polynomial time. =========================================================================== On the possibility of faster SAT algorithms --------------------------------------------------------------------------- Authors: Mihai Patrascu (IBM Almaden) Ryan Williams (Institute for Advanced Study) Topics: Complexity, Geometry, Graph Algorithms --------------------------------------------------------------------------- We investigate the prospects for an algorithm for Boolean CNF satisfiability (CNF-SAT) that runs in $O^*(2^{\delta n})$ time for some $\delta < 1$. In such a case we would say CNF-SAT has an improved algorithm. We present several hypotheses which we feel are plausible, given current knowledge. We prove that if any of the hypotheses are true, then CNF SAT has an improved algorithm. For other candidate hypotheses, they imply that $k$-SAT can be solved in $2^{\delta n}$ time for a fixed $\delta < 1$ that is independent of $k$. Such results would be breakthroughs in exact algorithms. The contrapositive statements show that if we assume satisfiability does not admit improved algorithms, then many interesting lower bounds follow. Our reductions provide tight connections between satisfiability and several foundational problems in logic, graph theory, communication complexity, and computational geometry. =========================================================================== Geometric optimization and sums of algebraic functions --------------------------------------------------------------------------- Authors: Antoine Vigneron (INRA) Topics: Approximation Algorithms, Geometry, Optimization --------------------------------------------------------------------------- We present a new optimization technique that yields the first FPTAS for several geometric problems. These problems reduce to optimizing a sum of non-negative, constant description-complexity algebraic functions. We first give a FPTAS for optimizing such a sum of algebraic functions, and then we apply it to several geometric optimization problems. We obtain the first FPTAS for two fundamental geometric shape matching problems in fixed dimension: maximizing the volume of overlap of two polyhedra under rigid motions, and minimizing their symmetric difference. We obtain the first FPTAS for other problems in fixed dimension, such as computing an optimal ray in a weighted subdivision, finding the largest axially symmetric subset of a polyhedron, and computing minimum area hulls. =========================================================================== Quasirandom Load Balancing --------------------------------------------------------------------------- Authors: Tobias Friedrich (International Computer Science Institute) Martin Gairing (International Computer Science Institute) Thomas Sauerwald (International Computer Science Institute) Topics: Algorithm Analysis, Combinatorics, Distributed and Parallel Computing, Graph Algorithms, Markov Chains, Probability --------------------------------------------------------------------------- We propose a simple distributed algorithm for balancing indivisible tokens on graphs. The algorithm is completely deterministic, though it tries to imitate (and enhance) a random algorithm by keeping the accumulated rounding errors as small as possible. Our new algorithm approximates the idealized process (where the tokens are divisible) on important network topologies surprisingly closely. On $d$-dimensional torus graphs with $n$ nodes it deviates from the idealized process only by an additive constant. In contrast to that, the randomized rounding approach of Friedrich and Sauerwald [STOC '09] can deviate up to $\Omega(\polylog n)$ and the deterministic algorithm of Rabani, Sinclair and Wanka [FOCS '98] has a deviation of $\Omega(n^{1/d})$. This makes our quasirandom algorithm the first known algorithm for this setting which is optimal both in time and achieved smoothness. We can further show that also on the hypercube our algorithm has a smaller deviation from the idealized process than the previous algorithms. To prove these results, we derive several combinatorial and probabilistic results that we believe to be of independent interest. In particular, we show that first-passage probabilities of a random walk on a path with arbitrary weights can be expressed as a convolution of independent geometric probability distributions. =========================================================================== SRPT is 1.86-Competitive for Completion Time Scheduling --------------------------------------------------------------------------- Authors: Christine Chung (University of Pittsburgh) Tim Nonner (Albert-Ludwigs-University of Freiburg) Alexander Souza (Albert-Ludwigs-University of Freiburg) Topics: Algorithm Analysis, Approximation Algorithms, Online problems, Optimization, Probability, Scheduling and Resource Allocation --------------------------------------------------------------------------- We consider the classical problem of scheduling preemptible jobs, that arrive over time, on identical parallel machines. The objective function is to minimize the total completion time of the jobs. In standard scheduling notation of Graham et al.~\cite{GrahamLawlerLenstraRinnooyKan:1979}, this problem is denoted $ P | prmt, online, r_j | \sum_j c_j $. A popular algorithm called SRPT, which always schedules an unfinished job with shortest remaining processing time, is known to be $2$-competitive, see Phillips et al.~\cite{PhillipsSteinWein:1995,PhillipsSteinWein:1998}. This is also the best known competitive ratio for any deterministic online algorithm for this problem. However, it is conjectured that the competitive ratio of SRPT is significantly less than $2$. Even breaking the barrier of $2$ is considered a significant step towards the final answer of this classical online problem. We improve on this open problem by showing that SRPT is $ 1.86 $-competitive. We obtain this result using the probabilistic method: We give a randomized algorithm that transforms any schedule into an SRPT-schedule and show that the objective function increases by at most a factor of $ 1.86 $ in expectation. This implies that there is a transformation from an optimal schedule to an SRPT-schedule, yielding the claimed competitiveness. To the best of our knowledge, the approach of transforming schedules using randomness is new in the area of scheduling and may be of independent interest. Furthermore, we show a lower bound of $21/19$ for SRPT, improving on the previously best known $12/11$ due to Lu et al.~\cite{LuSittersStougie:2003}. =========================================================================== Efficient Broadcast on Random Geometric Graphs --------------------------------------------------------------------------- Authors: Milan Bradonji (Los Alamos National Laboratory) Robert Elsässer (University of Paderborn) Tobias Friedrich (International Computer Science Institute) Thomas Sauerwald (International Computer Science Institute) Alexandre Stauffer (University of California) Topics: Algorithm Analysis, Distributed and Parallel Computing, Geometry, Graph Algorithms, Random Graphs, Random Structures --------------------------------------------------------------------------- A Random Geometric Graph (RGG) in two dimensions is constructed by distributing $n$ nodes uniformly at random in $[0,\sqrt{n}]^2$ and connecting two nodes if their Euclidean distance is at most $r$, for some prescribed $r$. We analyze the following randomized broadcast algorithm on RGGs. At the beginning, there is only one informed node in the largest connected component of the RGG. Then, in each round, each informed node chooses a neighbor uniformly at random and informs it. We prove that this algorithm informs every node in the largest connected component of an RGG within $O(\sqrt{n}/r+\log n)$ rounds with probability $1-O(n^{-1})$. This holds for any value of $r$ larger than the critical value for the emergence of a connected component with $\Omega(n)$ nodes. By proving this result, we show that for any two nodes sufficiently distant from each other in $[0,\sqrt{n}]^2$, the length of the shortest path between them in the RGG, when such a path exists, has length only a constant factor larger than the optimum. This result has independent interest and, in particular, gives that the diameter of the largest component of an RGG is $\Theta(\sqrt{n}/r)$, which surprisingly has been an open problem so far. =========================================================================== Maximum Flows and Parametric Shortest Paths in Planar Graphs --------------------------------------------------------------------------- Authors: Jeff Erickson (University of Illinois, Urbana-Champaign) Topics: Graph Algorithms, Optimization, Topological Problems --------------------------------------------------------------------------- We observe that the classical maximum flow problem in any directed planar graph $G$ can be reformulated as a parametric shortest path problem in the oriented dual graph $G^*$. This reformulation immediately suggests an algorithm to compute maximum flows, which runs in $O(n\log n)$ time. As we continuously increase the parameter, each change in the shortest path tree can be effected in $O(\log n)$ time using standard dynamic tree data structures, and the special structure of the parametrization implies that each directed edge enters the evolving shortest path tree at most once. The resulting maximum-flow algorithm is identical to the recent algorithm of Borradaile and Klein [\emph{J. ACM} 2009], but our new formulation allows a simpler presentation and analysis. On the other hand, we demonstrate that for a similarly structured parametric shortest path problem on the torus, the shortest path tree can change $\Omega(n^2)$ times in the worst case, suggesting that different methods may be required to efficiently compute maximum flows in higher-genus graphs. =========================================================================== Towards the Randomized $k$-Server Conjecture: A Primal-Dual Approach --------------------------------------------------------------------------- Authors: Nikhil Bansal (IBM Research) Niv Buchbinder (Microsoft Research) Seffi Naor (Technion, Israel) Topics: Algorithm Analysis, Online problems --------------------------------------------------------------------------- Recently, Cot\'{e} et al.~\cite{CMP08} proposed an approach for solving the $k$-server problem on Hierchically Separated Trees (HSTs). In particular, they define a problem on a uniform metric, and show that if an algorithm with a certain refined guarantee exists for it, then one can obtain polylogarithmic (in diameter) competitive factors for the $k$-server problem on HSTs by solving this problem recursively. By designing such an algorithm for a two point metric, they obtained a logarithmic competitive algorithm for well-separated {\em binary} HSTs. Extending their result to uniform metrics on arbitrarily many points would imply a poly-logarithmic competitive algorithm for $k$-server on general HSTs (and hence general metrics) and thus is of major interest. Here, we design such an algorithm for any uniform metric, provided the instance satisfies a certain ``concavity" property. Even though this does not give a result for $k$-server, concavity seems to be a very natural property and we give evidence that instances arising in the Cot\'{e} et al.~\cite{CMP08} reduction from $k$-server essentially possess this property, suggesting that this might be a promising approach. Already, our setting is general enough to model the finely competitive paging problem proposed by Blum et al.~\cite{BBK}, as a possible first step towards achieving a polylog(k) competitive algorithm for $k$-server. Our result implies an $r + O(\log k)$-competitive algorithm for finely competitive paging, solving the main open problem of \cite{BBK}. Our results are based on an extension of the primal-dual framework for online algorithms developed by Buchbinder and Naor \cite{BN05}. The original approach works for problems whose offline version can be expressed as a packing or a covering LP, possibly with box constraints, and the online nature of the problem is modeled by the fact that values of variables can only be increased over time. Here, we extend the approach to include more general types of constraints, where terms could be both positive and negative. Moreover, we allow the variables to both increase and decrease. This versatility allows us to model problems like predicting with expert advice, which could not be modeled earlier. To show the simplicity and generality of this approach, we give an alternate $O(\log k)$-competitive algorithm for weighted paging with a very simple proof. We also give an alternate primal-dual approach to design regret minimization algorithms for the problem of online prediction with expert advice. We believe that our primal-dual approach will find many more applications. =========================================================================== An O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem --------------------------------------------------------------------------- Authors: Arash Asadpour (stanford) Michel X. Goemans (mit) Aleksander Madry (mit) Shayan Oveis Gharan (stanford) Amin Saberi (stanford) Topics: Approximation Algorithms, Graph Algorithms, Mathematical Programming, Random Structures --------------------------------------------------------------------------- We give an O(log n/loglog n) approximation algorithm for the asymmetric traveling salesman problem when the costs satisfy the triangle inequality. Our approach is based on constructing a ``thin'' (undirected) spanning tree from the solution of a classical linear programming relaxation of the problem and augmenting the tree to an Eulerian subgraph through min-cost flow. Our rounding method is based on sampling from a maximum entropy distribution and could be of independent interest. =========================================================================== Algorithms for ray class groups and Hilbert class fields --------------------------------------------------------------------------- Authors: Sean Hallgren (Penn State University) Kirsten Eisentraeger (Penn State University) Topics: Algebra, Algorithm Analysis --------------------------------------------------------------------------- Objects from number theory have been useful in many algorithms. For example, the number field sieve is the fastest classical algorithm known for factoring large integers. On the other hand, applications to cryptography, such as RSA and elliptic curve cryptography, are based on the difficulty of problems from number theory. This paper analyzes the complexity of problems from class field theory. Class field theory classifies all finite abelian extensions of a number field. It can be used to show the existence of families of numbers fields with properties useful for cryptography. For example, an infinite family of number fields with constant root discriminant has been proposed for lattice-based cryptography. Similar families of number fields have also been used for constructing error-correcting codes. While the existence of such families follows from class field theory, little is known about the complexity of computing them. In order to understand the complexity of these problems, we show that efficient reductions exist from these problems to known apparently difficult problems such as computing the unit group and class group of a number field, solving the principal ideal problem in a number field, factoring, and discrete log. In particular, we show that computing the ray class group and computing subfields of Hilbert class fields reduce to these problems. One consequence of our (classical) reductions is that efficient quantum algorithms exist for these problems in constant degree number fields, since quantum algorithms are known for the target problems. This gives a first step towards computing the full class field tower mentioned above in the quantum setting. =========================================================================== Road Network Reconstruction for Organizing Paths --------------------------------------------------------------------------- Authors: Daniel Chen (Stanford University) Leonidas J. Guibas (Stanford University) John Hershberger (Mentor Graphics) Jian Sun (Stanford University) Topics: Algorithm Analysis, Geometry, Pattern Matching --------------------------------------------------------------------------- We consider the problem of reconstructing a road network from a collection of path traces and provide guarantees to the accuracy of the reconstruction under reasonable assumptions. Our algorithm can be used to process a collection of polygonal paths in the plane so that shared structures (subpaths) among the paths in the collection can be discovered and the collection can be organized to allow efficient path similarity queries against new query paths on the same road network. This is a timely problem, as GPS or other location traces of both people and vehicles are becoming available in a large scale and there is a real need to create appropriate data structures and data bases for such data. =========================================================================== A Fourier space algorithm for solving quadratic assignment problems --------------------------------------------------------------------------- Authors: Risi Kondor (Gatsby Computational Neuroscience Unit, University College London) Topics: Algebra, Experimental Algorithmics, Graph Algorithms, Optimization --------------------------------------------------------------------------- The quadratic assignement problem (QAP) is a central problems in combinatorial optimization. Several classic hard problems such as graph matching, partitioning, and the traveling salesman all reduce to special cases of the QAP. In this paper we propose a new approach to the QAP based on the theory of non-commutative Fourier analysis on the symmetric group. Specifically, we present a branch--and--bound algorithm that performs both the branching and the bounding steps in Fourier space. By exploiting the band-limited nature of the QAP objective function and using FFT techniques, the algorithm runs in O(n^3) time per branch--and--bound node. Moreover, empirical results suggest that for specific natural classes of random QAPs our Fourier bounds are tighter than the bounds employed by certain other popular QAP algorithms of the same order of complexity, and consequently our algorithm needs to visit fewer nodes and is faster overall. =========================================================================== Self-improving Algorithms for Convex Hulls --------------------------------------------------------------------------- Authors: Kenneth L. Clarkson (IBM Almaden) Wolfgang Mulzer (Princeton University) C. Seshadhri (IBM Almaden) Topics: Algorithm Analysis, Geometry, Random Structures --------------------------------------------------------------------------- We give an algorithm for computing planar convex hulls in the self-improving model: Given a sequence I_1, I_2, ... of planar n-point sets, the upper convex hull conv(I) of each set I is desired. We assume that there exists a probability distribution D on sets of n points, such that the inputs I_j are drawn independently according to D. Furthermore, D is such that the individual points in I are distributed independently of each other. In other words, the i-th point is distributed according to D_i. The D_i's can be arbitrary but are independent of each other. The distribution D is not known to the algorithm in advance. After a learning phase of n^\eps rounds, the expected time to compute conv(I) is O(n + H(conv(I))). Here, H(conv(I)) is the minimum entropy of any random variable that maps I to a description of conv(I) and to a labeling scheme that proves non-extremality for every point in I not on the hull. This is a lower bound for the expected running time of _any_ algebraic computation tree that computes the convex hull. Our algorithm is therefore asymptotically optimal for D. =========================================================================== Quantum algorithms for highly non-linear Boolean functions --------------------------------------------------------------------------- Authors: Martin Roetteler (NEC Laboratories America) Topics: Cryptography, Quantum Computing --------------------------------------------------------------------------- Attempts to separate the power of classical and quantum models of computation have a long history. The ultimate goal is to find exponential separations for computational problems. However, these do not come a dime a dozen: while there were some early successes in the form of hidden subgroup problems for abelian groups--which generalize Shor's factoring algorithm perhaps most faithfully--only for a handful of non-abelian groups efficient quantum algorithms were found. Recently, problems have gotten increased attention that seek to identify hidden sub-structures of other combinatorial and algebraic objects besides groups. In this paper we provide new examples for exponential separations by considering hidden shift problems that are defined for several classes of highly non-linear Boolean functions. These so-called bent functions arise in cryptography, where their property of having perfectly flat Fourier spectra on the Boolean hypercube gives them resilience against certain types of attack. We present quantum algorithms that solve the hidden shift problems for several well-known classes of bent functions in polynomial time and with a constant number of queries, while the classical query complexity is shown to be exponential. Our approach uses a technique that exploits the duality between bent functions and their Fourier transforms. =========================================================================== Approximability of Robust Network Design --------------------------------------------------------------------------- Authors: Neil Olver (Department of Mathematics and Statistics, McGill University) F. Bruce Shepherd (Department of Mathematics and Statistics, McGill University) Topics: Algorithm Analysis, Approximation Algorithms, Internet and Network Algorithms --------------------------------------------------------------------------- We consider robust network design problems where the set of feasible demands may be given by an arbitrary polytope or convex body more generally. This model, introduced by Ben-Ameur and Kerivin, generalizes the well studied virtual private network (VPN) problem. Most research in this area has focused on finding constant factor approximations for specific polytope of demands, such as the class of hose matrices used in the definition of VPN. As pointed out in [Chekuri '07], however, the general problem was only known to be APX-hard (based on a reduction from the Steiner tree problem). We show that the general robust design is hard to approximate to within logarithmic factors. We establish this by showing a general reduction of buy-at-bulk network design to the robust network design problem. In the second part of the paper, we introduce a natural generalization of the VPN problem. In this model, the set of feasible demands is determined by a tree with edge capacities; a demand matrix is feasible if it can be routed on the tree. We give a constant factor approximation algorithm for this problem that achieves factor 8 in general, and 2 for the case where the tree has unit capacities. =========================================================================== Speeding up random walks with neighborhood exploration --------------------------------------------------------------------------- Authors: Petra Berenbrink (Simon Fraser University) Colin Cooper (King's College London) Robert Elsaesser (University of Paderborn) Tomasz Radzik (King's College London) Thomas Sauerwald (ICSI Berkeley) Topics: Graph Algorithms, Probability, Random Graphs, Random Structures --------------------------------------------------------------------------- We consider the following marking random walk (RW-MARK) process on a connected undirected graph G. Let v denote the vertex visited by the random walk in the current step. If v has not been marked before, then mark it. If v is already marked, then mark a randomly chosen unmarked neighbor of v, if any. In the next step proceed to a random neighbor, according to the random walk process. We also consider a variant RW-R-RANK process, which first assigns to each node a random integer rank, drawn from a suitably large range. Then in each step of the random walk, RW-R-RANK marks the lowest ranked unmarked neighbor of the currently visited node. These processes are well-suited to speed-up the basic random walk, which has, in general, a cover time of $\Omega(n \log n)$. Furthermore, RW-MARK and RW-R-RANK can be compared with the corresponding graph-based coupon collector processes CC-MARK and CC-R-RANK. CC-MARK picks up in each step a random node v and marks it, if unmarked, or marks a random unmarked neighbor of v, if v is already marked. Our processes RW-MARK and RW-R-RANK can be viewed as distributed implementations of CC-MARK and CC-R-RANK which avoid "jumping" in each step to a globally random node. It was shown before that CC-MARK covers all nodes of an n-node G whp in $O(n)$ steps, if G is a hypercube and in $O(n + n (log n log d)/d)$ steps, if G is a d-regular graph [Adler, Halperin, Karp, Vazirani; 2003], and in $O(n + n (log n)/d)$ steps, if G is a Ramanujan or a random d-regular graph [Alon; 2008]. CC-R-RANK covers all nodes of any d-regular graph in $O(n)$ steps, whp, if $d = \Omega(\log n)$ [Dimitrov, Plaxton; 2005]. For RW-MARK and RW-R-RANK we show the following bounds on the number of steps required to mark all nodes whp: (i) An $O((1 - \lambda_2)^{-1}(n + n (log n log d)/d))$ bound for RW-MARK on d-regular graphs, where $\lambda_2$ is the second eigenvalue of the transition matrix of the random walk. This result implies an upper bound of $O(n)$ for $\Omega(\log n \log \log n)$-regular expanders, and an upper bound of $O(n \log \log n)$ for $\Omega(\log n)$-regular expanders. (ii) An $O(n + n (log n)/d)$ bound for RW-MARK on a d-regular graph with "strong" local expansion properties. (iii) An $O(n)$ bound for RW-R-RANK on d-regular graphs with "good" local expansion properties and on (almost) Ramanujan graphs, for $d > \log n$. In particular, since the hypercube has strong local expansion properties, (ii) and (iii) imply that RW-MARK and RW-R-RANK mark whp all nodes of an n-node hypercube in $O(n)$ steps. More generally, our results imply that on many important graph classes, random walks which are allowed to mark (cover) neighbors, have the same cover time as the corresponding centralized coupon collecting process. =========================================================================== A Model of Computation for MapReduce --------------------------------------------------------------------------- Authors: Howard Karloff (AT&T Labs) Siddharth Suri (Yahoo! Research) Sergei Vassilvitskii (Yahoo! Research) Topics: Distributed and Parallel Computing, Internet and Network Algorithms --------------------------------------------------------------------------- In recent years the MapReduce framework has emerged as one of the most widely used parallel computing platforms for processing data on the terabyte and petabyte scales. Used daily at companies such Yahoo!, Google, Amazon, and Facebook and adopted more recently by several universities, it allows for easy parallelization of data intensive computations over many machines. One key feature of MapReduce that differentiates it from previous models of parallel computation is that it interleaves sequential and parallel computation. We propose a model of efficient computation using the MapReduce paradigm. Our model allows each machine to perform sequential computations in time polynomial in the size of the input that machine receives. Moreover, since MapReduce is designed for computations over massive data sets, our model limits the number of machines and the memory per machine to be (substantially) sublinear in the size of the input. We compare MapReduce to the PRAM model of computation. We prove a simulation lemma showing that a large class of PRAM algorithms can be efficiently simulated via MapReduce. The strength of MapReduce, however, lies in the fact that it uses both sequential and parallel computation. We show how algorithms can take advantage of this fact to compute an MST of a dense graph in only two rounds, as opposed to O(log(n)) rounds needed by a standard PRAM. We also show to evaluate a wide class of functions using the MapReduce framework. We conclude by applying this result to show how to compute many basic algorithmic problems such as undirected connectivity in the MapReduce framework. =========================================================================== Fast SDP Algorithms for Constraint Satisfaction Problems --------------------------------------------------------------------------- Authors: David Steurer (Princeton University) Topics: Algorithm Analysis, Approximation Algorithms, Mathematical Programming, Optimization, Probability --------------------------------------------------------------------------- The class of constraint satisfactions problems (CSPs) contains many fundamental combinatorial optimization problems such as MaxCut and Max3SAT. Recently, Raghavendra (STOC`08) showed that a certain semidefinite programming relaxation gives the best possible approximation for any CSP, assuming Khot's Unique Games Conjecture. Raghavendra and Steurer (FOCS`09) show that independent of the truth of the Unique Games Conjecture the integrality gap of this relaxation cannot be improved even by adding a large class of valid inequalities. We present an algorithm that finds an approximate solution to this relaxation in near-linear time. Combining this algorithm with a rounding scheme of Raghavendra and Steurer (FOCS`09) yields an approximation algorithm for any CSP that runs in near-linear time and has an approximation guarantee that matches the integrality gap, which is optimal assuming the Unique Games Conjecture Our algorithm employs a framework of Arora and Kale (STOC`07) for solving semidefinite programs. In this framework, the crucial step is to design an efficient width-bounded separation oracle. We show how to implement this oracle by solving a sequence of local linear programs. We also generalize the framework of Arora and Kale in order to deal with irregular instances more efficiently. =========================================================================== Lower bounds for Edit Distance and Product Metrics via Poincare-Type Inequalities --------------------------------------------------------------------------- Authors: Alexandr Andoni (MIT) T.S. Jayram (IBM Almaden) Mihai Patrascu (IBM Almaden) Topics: Complexity, Geometry, Metric Embeddings --------------------------------------------------------------------------- We prove that any sketching protocol for edit distance achieving a constant approximation requires nearly logarithmic (in the strings' length) communication complexity. This is an exponential improvement over the previous, doubly-logarithmic, lower bound of [Andoni-Krauthgamer, FOCS'07]. Our lower bound also applies to the Ulam distance (edit distance over non-repetitive strings). In this special case, it is polynomially related to the recent upper bound of [Andoni-Indyk-Krauthgamer, SODA'09]. From a technical perspective, we prove a direct-sum theorem for sketching product metrics that is of independent interest. We show that, for any metric X that requires sketch size which is a sufficiently large constant, sketching the max-product metric \ell_\infty^d(X) requires \Omega(d) bits. The conclusion, in fact, also holds for arbitrary two-way communication. The proof uses a novel technique for information complexity based on Poincar\'e inequalities and suggests an intimate connection between non-embeddability, sketching and communication complexity. =========================================================================== Shape Replication Through Self-Assembly and RNase Enzymes --------------------------------------------------------------------------- Authors: Zachary Abel (Harvard University) Nadia Benbernou (Massachusetts Institute of Technology) Mirela Damian (Villanova University) Erik Demaine (Massachusetts Institute of Technology) Robin Flatland (Siena College) Skott Kominers (Harvard University) Robert Schweller (University of Texas Pan American) Martin Demaine (Massachusetts Institute of Technology) Topics: Bioinformatics, Geometry --------------------------------------------------------------------------- We introduce the problem of shape replication in the Wang tile self-assembly model. Given an input shape, we consider the problem of designing a self-assembly system which will replicate that shape into either a specific number of copies, or an unbounded number of copies. Motivated by practical DNA implementations of Wang tiles, we consider a model in which tiles consisting of DNA or RNA can be dynamically added in a sequence of stages. We further permit the addition of RNase enzymes capable of disintegrating RNA tiles. Under this model, we show that arbitrary genus 0 shapes can be replicated infinitely many times with O(1) distinct tile types and O(1) stages. Further, we show how to replicate precisely n copies of a shape using either O(log n) stages or O(log n) tile types. =========================================================================== Universal $\epsilon$-approximators for integrals --------------------------------------------------------------------------- Authors: Michael Langberg (The Open University of Israel) Leonard J. Schulman (Caltech) Topics: Geometry, Learning --------------------------------------------------------------------------- Let $X$ be a space and $F$ a family of ${0,1}$-valued functions on $X$. Vapnik and Chervonenkis showed that if $F$ is "simple" (finite VC dimension), then for every probability measure $\mu$ on $X$ and $\e>0$ there is a finite set $S$ such that for all $f \in F$, $\sum_{x \in S} f(x)/|S| = [\int f(x) d\mu(x)] \pm \e$. Think of $S$ as a "universal $\epsilon$-approximator" for integration in $F$. $S$ can actually be obtained w.h.p. just by sampling a few points from $\mu$. This is a mainstay of computational learning theory. It was later extended by other authors to families of bounded (e.g., $[0,1]$-valued) real functions. In this work we establish similar "universal $\epsilon$-approximators" for families of unbounded nonnegative real functions --- in particular, for the families over which one optimizes when performing data classification. In this case the $\epsilon$-approximation is multiplicative. =========================================================================== A 1.4-Competitive Online Graph Edge Coloring Algorithm in the Random Order Arrival Model --------------------------------------------------------------------------- Authors: Bahman Bahmani (Stanford University) Aranyak Mehta (Google, Inc.) Rajeev Motwani (Stanford University) Topics: Algorithm Analysis, Graph Algorithms, Online problems --------------------------------------------------------------------------- A classic theorem by Vizing proves that if the maximum degree of a graph is $\Delta$, then it is possible to color its edges, in polynomial time, using at most $\Delta+1$ colors. However, this algorithm is offline, i.e., it assumes the whole graph is known in advance. A natural question then is how well we can do in the online setting, where the edges of the graph are revealed one by one, and we need to color each edge as soon as it is added to the graph. Online edge coloring has an important application in fast switch scheduling. Here, a natural model is that edges arrive online, but in a random permutation. Even in the random permutations model, the best known analysis for any algorithm is factor 2, which comes from the simple greedy algorithm (which is factor 2 even in the worst case online model). The algorithm of Aggarwal et al. (FOCS 03) provides a 1+o(1) factor algorithm, but for the case of multigraphs, when $\Delta = \Omega(n^2)$, where $n$ is the number of vertices. In this paper, we show that for graphs with $\Delta = \Omega(polylog(n))$, it is possible to color the graph with $1.4\Delta+o(\Delta)$ colors in the online random order model. Our algorithm is inspired by a 1.6 factor distributed offline algorithm of Panconesi and Srinivasan (SICOMP'97), which we extend by reusing colors online in multiple rounds. =========================================================================== Orthogonal Ham-Sandwich Theorem in R3 --------------------------------------------------------------------------- Authors: Sergey Bereg (University of Texas at Dallas) Topics: Geometry, Topological Problems --------------------------------------------------------------------------- The ham-sandwich theorem states that, given $d\ge 2$ measures in $\R^d$, it is possible to divide all of them in half with a single $(d-1)$-dimensional hyperplane. We study an orthogonal version of the ham-sandwich theorem and define an orthogonal cut using at most $d$ hyperplanes orthogonal to coordinate axes. For example, a hyperplane orthogonal to a coordinate axis is an orthogonal cut. We prove that any three measures in $\R^3$ can be divided in half each with a single orthogonal cut. Applied to point measures, it implies that any three finite sets of points in $\R^3$ can be simultaneously bisected by an orthogonal cut. We present an algorithm for computing an orthogonal ham-sandwich cut in $O(n\log n)$ time. =========================================================================== Bounding Variance and Expectation of Longest Path Length in DAGs from Variance and Expectation of Edge Lengths --------------------------------------------------------------------------- Authors: Jeff Edmonds (York University) Supratik Chakraborty (Indian Institute of Technology Bombay) Topics: Graph Algorithms, Probability --------------------------------------------------------------------------- We consider the problem of computing bounds on the variance and expectation of the longest path length in a DAG from knowledge of variance and expectation of edge lengths. We focus primarily on the case where all edge lengths are non-negative and the DAG has a single source and sink node. We present analytic bounds for various simple DAG structures, and present a new algorithm to compute bounds for more general DAG structures. Our algorithm is motivated by an analogy with balance of forces in a network of "strange" springs. We present some experimental results showing the effectiveness of this algorithm for computing bounds in variance and expectation of circuit delays from variance and expectation of gate delays