Search

In this paper we consider both the maximization variant Max Rep and the minimization variant Min Rep of the famous Label Cover problem, for which, till now, the best approximation ratios known were ]> . In fact, several recent papers reduced Label Cover to other problems, arguing that if better approximation algorithms for their problems existed, then a ]> -approximation algorithm for Label Cover would exist. We show, in fact, that there are a O(n1/3)-approximation algorithm for Max Rep and a O(n1/3log2/3n)-approximation algorithm for Min Rep. In addition, we also exhibit a randomized reduction from Densest k-Subgraph to Max Rep, showing that any approximation factor for Max Rep implies the same factor (up to a constant) for Densest k-Subgraph. [ABSTRACT FROM AUTHOR]

We present the fastest FPRAS for counting and randomly generating simple graphs with a given degree sequence in a certain range. For degree sequence $(d_i)_{i=1}^n$ with maximum degree $d_{\max}=O(m^{1/4-\tau})$, our algorithm generates almost uniform random graph with that degree sequence in time O(md max ) where is the number of edges in the graph and τ is any positive constant. The fastest known FPRAS for this problem [22] has running time of O(m3n2). Our method also gives an independent proof of McKay's estimate [33] for the number of such graphs. Our approach is based on sequential importance sampling (SIS) technique that has been recently successful for counting graphs [15,11,10]. Unfortunately validity of the SIS method is only known through simulations and our work together with [10] are the first results that analyze the performance of this method. Moreover, we show that for d = O(n1/2 − τ), our algorithm can generate an asymptotically uniform d-regular graph. Our results are improving the previous bound of d = O(n1/3 − τ) due to Kim and Vu [30] for regular graphs. [ABSTRACT FROM AUTHOR]

Let signify a random d-uniform hypergraph with n vertices in which each of the possible edges is present with probability p = p(n) independently, and let denote a uniformly distributed d-uniform hypergraph with n vertices and m edges. We establish a local limit theorem for the number of vertices and edges in the largest component of in the regime , thereby determining the joint distribution of these parameters precisely. As an application, we derive an asymptotic formula for the probability that is connected, thus obtaining a formula for the asymptotic number of connected hypergraphs with a given number of vertices and edges. While most prior work on this subject relies on techniques from enumerative combinatorics, we present a new, purely probabilistic approach. [ABSTRACT FROM AUTHOR]

A k-query locally decodable code (LDC) allows to probabilistically decode any bit of an encoded message by probing only k bits of its corrupted encoding. A stronger and desirable property is that of self-correction, allowing to efficiently recover not only bits of the message but also arbitrary bits of its encoding. In contrast to the initial constructions of LDCs, the recent and most efficient constructions are not known to be self-correctable. The existence of self-correctable codes of comparable efficiency remains open. A closely related problem with a very different motivation is that of private information retrieval (PIR). A k-server PIR protocol allows a user to retrieve the i-th bit of a database, which is replicated among k servers, without revealing information about i to any individual server. A natural generalization is t-private PIR, which keeps i hidden from any t colluding servers. In contrast to the initial PIR protocols, it is not known how to generalize the recent and most efficient protocols to yield t-private protocols of comparable efficiency. In this work we study both of the above questions, showing that they are in fact related. We start by presenting a general transformation of any 1-private PIR protocol (equivalently, LDC) into a t-private protocol with a similar amount of communication per server. Combined with the recent result of Yekhanin (STOC 2007), this yields a significant improvement over previous t-private PIR protocols. A major weakness of our transformation is that the number of servers in the resulting t-private protocols grows exponentially with t. We show that if the underlying LDC satisfies the stronger self-correction property, then there is a similar transformation in which the number of servers grows only linearly with t, which is the best one can hope for. Finally, we study the question of closing the current gap between the complexity of the best known LDC and that of self-correctable codes, and relate this question to a conjecture of Hamada concerning the algebraic rank of combinatorial designs. [ABSTRACT FROM AUTHOR]

We consider the problem of approximating the average distance between pairs of points in a high-dimensional Euclidean space, and more generally in any metric space. We consider two algorithmic approaches: 1Referring only to Euclidean Spaces, we randomly reduce the high-dimensional problem to a one-dimensional problem, which can be solved in time that is almost-linear in the number of points. The resulting algorithm is somewhat better than a related algorithm that can be obtained by using the known randomized embedding of Euclidean Spaces into ℓ1-metric.1An alternative approach consists of selecting a random sample of pairs of points and outputting the average distance between these pairs. It turns out that, for any metric space, it suffices to use a sample of size that is linear in the number of points. Our analysis of this method is somewhat simpler and better than the known analysis of Indyk (STOC, 1999). We also study the existence of corresponding deterministic algorithms, presenting both positive and negative results. In particular, in the Euclidean case, this approach outperforms the first approach. In general, the second approach seems superior to the first approach. [ABSTRACT FROM AUTHOR]

We show that the multi-commodity max-flow/min-cut gap for series-parallel graphs can be as bad as 2. This improves the largest known gap for planar graphs from $\frac32$ to 2. Our approach uses a technique from geometric group theory called coarse differentiation in order to lower bound the distortion for embedding a particular family of shortest-path metrics into L1. [ABSTRACT FROM AUTHOR]

We raise the question of approximating the compressibility of a string with respect to a fixed compression scheme, in sublinear time. We study this question in detail for two popular lossless compression schemes: run-length encoding (RLE) and Lempel-Ziv (LZ), and present sublinear algorithms for approximating compressibility with respect to both schemes. We also give several lower bounds that show that our algorithms for both schemes cannot be improved significantly. Our investigation of LZ yields results whose interest goes beyond the initial questions we set out to study. In particular, we prove combinatorial structural lemmas that relate the compressibility of a string with respect to Lempel-Ziv to the number of distinct short substrings contained in it. In addition, we show that approximating the compressibility with respect to LZ is related to approximating the support size of a distribution. [ABSTRACT FROM AUTHOR]

Consider a scenario where one desires to simulate the execution of some graph algorithm on huge random G(N,p) graphs, where N = 2n vertices are fixed and each edge independently appears with probability p = pn. Sampling and storing these graphs is infeasible, yet Goldreich et al.[7], and Naor et al.[12] considered emulating dense G(N,p) graphs by efficiently computable ‘random looking' graphs. We emulate sparseG(N,p) graphs - including the densities of the G(N,p) threshold for containing a giant component (p ~1 / N), and for achieving connectivity (p′ ~ln N / N). The reasonable model for accessing sparse graphs is neighborhood queries where on query-vertex v, the entire neighbor-set Γ(v) is efficiently retrieved (without sequentially deciding adjacency for each vertex). Our emulation is faithful in the sense that our graphs are indistinguishable from G(N,p) graphs from the view of any efficient algorithm that inspects the graph by neighborhood queries of its choice. In particular, the G(N,p) degree sequence is sufficiently well approximated. [ABSTRACT FROM AUTHOR]

We consider the problem of finding the most frequent elements in the data stream model; this problem has a linear lower bound in terms of the input length. In this paper we obtain sharper space lower bounds for this problem, not in terms of the length of the input as is traditionally done, but in terms of the quantitative properties (in this case, distribution of the element frequencies) of the input per se; this lower bound matches the best known upper bound for this problem. These bounds suggest the study of data stream algorithms through an instance-specific lens. [ABSTRACT FROM AUTHOR]

A fundamental goal of computational complexity (and foundations of cryptography) is to find a polynomial-time samplable distribution (e.g., the uniform distribution) and a language in NTIME(f(n)) for some polynomial function f, such that the language is hard on the average with respect to this distribution, given that NP is worst-case hard (i.e. NP ≠ P, or ${\rm NP} \not \subseteq {\rm BPP}$). Currently, no such result is known even if we relax the language to be in nondeterministic sub-exponential time. There has been a long line of research trying to explain our failure in proving such worst-case/average-case connections [FF93,Vio03,BT03,AGGM06]. The bottom line of this research is essentially that (under plausible assumptions) non-adaptive Turing reductions cannot prove such results. In this paper we revisit the problem. Our first observation is that the above mentioned negative arguments extend to a non-standard notion of average-case complexity, in which the distribution on the inputs with respect to which we measure the average-case complexity of the language, is only samplable in super-polynomial time. The significance of this result stems from the fact that in this non-standard setting,[GSTS05] did show a worst-case/average-case connection. In other words, their techniques give a way to bypass the impossibility arguments. By taking a closer look at the proof of [GSTS05], we discover that the worst-case/average-case connection is proven by a reduction that "almost" falls under the category ruled out by the negative result. This gives rise to an intriguing new notion of (almost black-box) reductions. After extending the negative results to the non-standard average-case setting of [GSTS05], we ask whether their positive result can be extended to the standard setting, to prove some new worst-case/average-case connections. While we can not do that unconditionally, we are able to show that under a mild derandomization assumption, the worst-case hardness of NP implies the average-case hardness of NTIME(f(n)) (under the uniform distribution) where f is computable in quasi-polynomial time. [ABSTRACT FROM AUTHOR]

We give a polynomial time construction of binary codes with the best currently known trade-off between rate and error-correction radius. Specifically, we obtain linear codes over fixed alphabets that can be list decoded in polynomial time up to the so called Blokh-Zyablov bound. Our work builds upon [7] where codes list decodable up to the Zyablov bound (the standard product bound on distance of concatenated codes) were constructed. Our codes are constructed via a (known) generalization of code concatenation called multilevel code concatenation. A probabilistic argument, which is also derandomized via conditional expectations, is used to show the existence of inner codes with a certain nested list decodability property that is appropriate for use in multilevel concatenated codes. A "level-by-level" decoding algorithm, which crucially uses the list recovery algorithm for folded Reed-Solomon codes from [7], enables list decoding up to the designed distance bound, aka the Blokh-Zyablov bound, for multilevel concatenated codes. [ABSTRACT FROM AUTHOR]

We show that local dynamics require exponential time for two sampling problems: independent sets on the triangular lattice (the hard-core lattice gas model) and weighted even orientations of the Cartesian lattice (the 8-vertex model). For each problem, there is a parameter λ known as the fugacity such that local Markov chains are expected to be fast when λ is small and slow when λ is large. However, establishing slow mixing for these models has been a challenge because standard contour arguments typically used to show that a chain has small conductance do not seem sufficient. We modify this approach by introducing the notion of fat contours that can have nontrivial d-dimensional volume and use these to establish slow mixing of local chains defined for these models. [ABSTRACT FROM AUTHOR]

We consider the question of whether adaptivity can improve the complexity of property testing algorithms in the dense graphs model. It is known that there can be at most a quadratic gap between adaptive and non-adaptive testers in this model, but it was not known whether any gap indeed exists. In this work we reveal such a gap. Specifically, we focus on the well studied property of bipartiteness. Bogdanov and Trevisan (IEEE Symposium on Computational Complexity, 2004) proved a lower bound of Ω(1/ε2) on the query complexity of non-adaptive testing algorithms for bipartiteness. This lower bound holds for graphs with maximum degree O(εn). Our main result is an adaptive testing algorithm for bipartiteness of graphs with maximum degree O(εn) whose query complexity is $\tilde{O}(1/\epsilon^{3/2})$. A slightly modified version of our algorithm can be used to test the combined property of being bipartite and having maximum degree O(εn). Thus we demonstrate that adaptive testers are stronger than non-adaptive testers in the dense graphs model. We note that the upper bound we obtain is tight up-to polylogarithmic factors, in view of the Ω(1/ε3/2) lower bound of Bogdanov and Trevisan for adaptive testers. In addition we show that $\tilde{O}(1/\epsilon^{3/2})$ queries also suffice when (almost) all vertices have degree $\Omega(\sqrt \epsilon \cdot n)$. In this case adaptivity is not necessary. [ABSTRACT FROM AUTHOR]

We initiate a general study of the randomness complexity of property testing, aimed at reducing the randomness complexity of testers without (significantly) increasing their query complexity. One concrete motivation for this study is provided by the observation that the product of the randomness and query complexity of a tester determine the actual query complexity of implementing a version of this tester that utilizes a weak source of randomness (through a randomness-extractor). We present rather generic upper- and lower-bounds on the randomness complexity of property testing and study in depth the special case of testing bipartiteness in two standard property testing models. [ABSTRACT FROM AUTHOR]

In the distribution-free property testing model, the distance between functions is measured with respect to an arbitrary and unknown probability distribution $\mathcal{D}$ over the input domain. We consider distribution-free testing of several basic Boolean function classes over {0,1}n, namely monotone conjunctions, general conjunctions, decision lists, and linear threshold functions. We prove that for each of these function classes, Ω((n/logn)1/5) oracle calls are required for any distribution-free testing algorithm. Since each of these function classes is known to be distribution-free properly learnable (and hence testable) using Θ(n) oracle calls, our lower bounds are within a polynomial factor of the best possible. [ABSTRACT FROM AUTHOR]

Space-economical estimation of the pth frequency moments, defined as , for p > 0, are of interest in estimating all-pairs distances in a large data matrix [14], machine learning, and in data stream computation. Random sketches formed by the inner product of the frequency vector f1..., fn with a suitably chosen random vector were pioneered by Alon, Matias and Szegedy [1], and have since played a central role in estimating Fp and for data stream computations in general. The concept of p-stable sketches formed by the inner product of the frequency vector with a random vector whose components are drawn from a p-stable distribution, was proposed by Indyk for estimating Fp, for 0 < p < 2, and has been further studied in Li [13]. In this paper, we consider the problem of estimating Fp, for 0 < p < 2. A disadvantage of the stable sketches technique and its variants is that they require $O(\frac{1}{\epsilon^2})$ inner-products of the frequency vector with dense vectors of stable (or nearly stable [14,13]) random variables to be maintained. This means that each stream update can be quite time-consuming. We present algorithms for estimating Fp, for 0 < p < 2, that does not require the use of stable sketches or its approximations. Our technique is elementary in nature, in that, it uses simple randomization in conjunction with well-known summary structures for data streams, such as the sketch [7] and the structure [5]. Our algorithms require space $\tilde{O}(\frac{1}{\epsilon^{2+p}})$ to estimate Fp to within 1 ±ε factors and requires expected time $O(\log F_1 \log \frac{1}{\delta})$ to process each update. Thus, our technique trades an $O(\frac{1}{\epsilon^p})$ factor in space for much more efficient processing of stream updates. We also present a stand-alone iterative estimator for F1. [ABSTRACT FROM AUTHOR]

We investigate the property of k-uniform k-partite (directed) hypergraphs with colored edges of being free of a fixed family of forbidden induced substructures. We show that this property is not testable with a number of queries polynomial in 1/ε, presenting proofs for the case of two colors and k = 3, as well as the case of three colors and k = 2 (edge-colored bipartite graphs). This settles an open question from [1], implying that the polynomial testability proof for two colors and k = 2 cannot be extended to these structures. [ABSTRACT FROM AUTHOR]

We prove a lower bound for swapping the order of Arthur and Merlin in two-round Merlin-Arthur games using black-box techniques. Namely, we show that any AM-game requires time Ω(t2) to black-box simulate MA-games running in time t. Thus, the known simulations of MA by AM with quadratic overhead, dating back to Babai's original paper on Arthur-Merlin games, are tight within this setting. The black-box lower bound also yields an oracle relative to which ${\rm MA-TIME}[n] \nsubseteq {\rm AM-TIME}[o(n^2)]$. Complementing our lower bounds for swapping Merlin in MA-games, we prove a time-space lower bound for simulations that drop Merlin entirely. We show that for any $c < \sqrt{2}$, there exists a positive d such that there is a language recognized by linear-time MA-games with one-sided error but not by probabilistic random-access machines with two-sided error that run in time nc and space nd. This improves recent results that give such lower bounds for problems in the second level of the polynomial-time hierarchy. [ABSTRACT FROM AUTHOR]

We initiate a systematic study of eigenvectors of random graphs. Whereas much is known about eigenvalues of graphs and how they reflect properties of the underlying graph, relatively little is known about the corresponding eigenvectors. Our main focus in this paper is on the nodal domains associated with the different eigenfunctions. In the analogous realm of Laplacians of Riemannian manifolds, nodal domains have been the subject of intensive research for well over a hundred years. Graphical nodal domains turn out to have interesting and unexpected properties. Our main theorem asserts that there is a constant c such that for almost every graph G, each eigenfunction of G has at most 2 nodal domains, together with at most c exceptional vertices falling outside these primary domains. We also discuss variations of these questions and briefly report on some numerical experiments which, in particular, suggest that there are almost surely no exceptional vertices. [ABSTRACT FROM AUTHOR]

We study the cover time of a random walk on the random digraph Dn,p when $p=\frac{d\log n}{n}, d>1$. We prove that whp the cover time is asymptotic to . [ABSTRACT FROM AUTHOR]

In this paper we compare two methods for generating finite families of random subsets according to some sequence of independent random variables ζ1..., ζn distributed uniformly over the interval [0,1]. The first method called uniform split uses ζi values straightforwardly to determine points of division of [0,1] into subintervals. The second method called binary split uses ζi only to perform subsequent divisions of already existing subintervals into exact halves. We show that the variance of lengthes of obtained intervals in the first method is approximately $\frac{1}{n^2}$ and that the variance of lengthes of obtained intervals in the second method is approximately $\frac{1}{n^2}(\frac{1}{\ln 2}-1)$. The uniform split is used in the Chord peer-to-peer protocol while the binary split is used in the CAN protocol. Therefore our analysis applies to this protocols and shows that CAN has a better probabilistic properties than Chord. We propose also a simple modification of the Chord protocol which improves its statistical properties. [ABSTRACT FROM AUTHOR]

Using the symmetric form of the Lovász Local Lemma, one can conclude that a k-uniform hypergraph $\mathcal{H}$ admits a proper 2-colouring if the maximum degree (denoted by Δ) of $\mathcal{H}$ is at most $\frac{2^k}{8k}$ independently of the size of the hypergraph. However, this argument does not give us an algorithm to find a proper 2-colouring of such hypergraphs. We call a hypergraph linear if no two hyperedges have more than one vertex in common. In this paper, we present a deterministic polynomial time algorithm for 2-colouring every k-uniform linear hypergraph with $\Delta \le 2^{k-k^{\epsilon}}$, where 1/2 < ε< 1 is any arbitrary constant and k is larger than a certain constant that depends on ε. The previous best algorithm for 2-colouring linear hypergraphs is due to Beck and Lodha [4]. They showed that for every δ> 0 there exists a c > 0 such that every linear hypergraph with Δ ≤ 2k − δkand$k > c\log\log(E(\mathcal{H}))$, can be properly 2-coloured deterministically in polynomial time. [ABSTRACT FROM AUTHOR]

We continue the study, started in [9], of property testing of graphs in the orientation model. A major question which was left open in [9] is whether the property of st-connectivity can be tested with a constant number of queries. Here we answer this question on the affirmative. To this end we construct a non-trivial reduction of the st-connectivity problem to the problem of testing languages that are decidable by branching programs, which was solved in [11]. The reduction combines combinatorial arguments with a concentration type lemma that is proven for this purpose. Unlike many other property testing results, here the resulting testing algorithm is highly non-trivial itself, and not only its analysis. [ABSTRACT FROM AUTHOR]

We study the two party problem of randomly selecting a string among all the strings of length n. We want the protocol to have the property that the output distribution has high entropy, even when one of the two parties is dishonest and deviates from the protocol. We develop protocols that achieve high, close to n, entropy. In the literature the randomness guarantee is usually expressed as being close to the uniform distribution or in terms of resiliency. The notion of entropy is not directly comparable to that of resiliency, but we establish a connection between the two that allows us to compare our protocols with the existing ones. We construct an explicit protocol that yields entropy n − O(1) and has 4log*n rounds, improving over the protocol of Goldreich et al. [3] that also achieves this entropy but needs O(n) rounds. Both these protocols need O(n2) bits of communication. Next we reduce the communication in our protocols. We show the existence, non-explicitly, of a protocol that has 6 rounds, 2n + 8logn bits of communication and yields entropy n − O(logn) and min-entropy n/2 − O(logn). Our protocol achieves the same entropy bound as the recent, also non-explicit, protocol of Gradwohl et al. [4], however achieves much higher min-entropy: n/2 − O(logn) versus O(logn). Finally we exhibit very simple explicit protocols. We connect the security parameter of these geometric protocols with the well studied Kakeya problem motivated by harmonic analysis and analytical number theory. We are only able to prove that these protocols have entropy 3n/4 but still n/2 − O(logn) min-entropy. Therefore they do not perform as well with respect to the explicit constructions of Gradwohl et al. [4] entropy-wise, but still have much better min-entropy. We conjecture that these simple protocols achieve n − o(n) entropy. Our geometric construction and its relation to the Kakeya problem follows a new and different approach to the random selection problem than any of the previously known protocols. [ABSTRACT FROM AUTHOR]

We consider the problem of derandomizing random walks in the Euclidean space . We show that for k = 2, and in some cases in higher dimensions, such walks can be simulated in Logspace using only poly-logarithmically many truly random bits. As a corollary, we show that the Dirichlet Problem can be deterministically simulated in space $O(\log n\sqrt{\log\log n})$, where 1/n is the desired precision of the simulation. [ABSTRACT FROM AUTHOR]

We study the computational complexity and algorithmic aspects of computing the least core value of supermodular cost cooperative games, and uncover some structural properties of the least core of these games. We provide motivation for studying these games by showing that a particular class of optimization problems has supermodular optimal costs. This class includes a variety of problems in combinatorial optimization, especially in machine scheduling. We show that computing the least core value of supermodular cost cooperative games is NP-hard, and design approximation algorithms based on oracles that approximately determine maximally violated constraints. We apply our results to schedule planning games, or cooperative games where the costs arise from the minimum sum of weighted completion times on a single machine. By improving upon some of the results for general supermodular cost cooperative games, we are able to give an explicit formula for an element of the least core of schedule planning games, and design a fully polynomial time approximation scheme for computing the least core value of these games. [ABSTRACT FROM AUTHOR]

This paper studies vehicle routing problems on asymmetric metrics. Our starting point is the directed k-TSP problem: given an asymmetric metric (V,d), a root r ∈ V and a target k ≤ V, compute the minimum length tour that contains r and at least k other vertices. We present a polynomial time O(log2n·logk)-approximation algorithm for this problem. We use this algorithm for directed k-TSP to obtain an O(log2n)-approximation algorithm for the directed orienteering problem. This answers positively, the question of poly-logarithmic approximability of directed orienteering, an open problem from Blum et al.[2]. The previously best known results were quasi-polynomial time algorithms with approximation guarantees of O(log2k) for directed k-TSP, and O(logn) for directed orienteering (Chekuri & Pal [4]). Using the algorithm for directed orienteering within the framework of Blum et al.[2] and Bansal et al.[1], we also obtain poly-logarithmic approximation algorithms for the directed versions of discounted-reward TSP and the vehicle routing problem with time-windows. [ABSTRACT FROM AUTHOR]

Constant-factor, polynomial-time approximation algorithms are presented for two variations of the traveling salesman problem with time windows. In the first variation, the traveling repairman problem, the goal is to find a tour that visits the maximum possible number of locations during their time windows. In the second variation, the speeding deliveryman problem, the goal is to find a tour that uses the minimum possible speed to visit all locations during their time windows. For both variations, the time windows are of unit length, and the distance metric is based on a weighted, undirected graph. Algorithms with improved approximation ratios are given for the case when the input is defined on a tree rather than a general graph. A sketch of NP-hardness is also given for the tree metric. [ABSTRACT FROM AUTHOR]

In metric asymmetric traveling salesperson problems the input is a complete directed graph in which edge weights satisfy the triangle inequality, and one is required to find a minimum weight walk that visits all vertices. In the asymmetric traveling salesperson problem (ATSP) the walk is required to be cyclic. In asymmetric traveling salesperson path problem (ATSPP), the walk is required to start at vertex s and to end at vertex t. We improve the approximation ratio for ATSP from $\frac{4}{3}\log_3 n \simeq 0.84\log_2 n$ to $\frac{2}{3}\log_2 n$. This improvement is based on a modification of the algorithm of Kaplan et al [JACM 05] that achieved the previous best approximation ratio. We also show a reduction from ATSPP to ATSP that loses a factor of at most 2 + ε in the approximation ratio, where ε> 0 can be chosen to be arbitrarily small, and the running time of the reduction is polynomial for every fixed ε. Combined with our improved approximation ratio for ATSP, this establishes an approximation ratio of $(\frac{4}{3} + \epsilon)\log_2 n$ for ATSPP, improving over the previous best ratio of 4logen ≃ 2.76log2n of Chekuri and Pal [Approx 2006]. [ABSTRACT FROM AUTHOR]

In the exact matching problem we are given a graph G, some of whose edges are colored red, and a positive integer k. The goal is to determine if G has a perfect matching, exactly k edges of which are red. More generally if the matching number of G is m = m(G), the goal is to find a matching with m edges, exactly k edges of which are red, or determine that no such matching exists. This problem is one of the few remaining problems that have efficient randomized algorithms (in fact, this problem is in RNC), but for which no polynomial time deterministic algorithm is known. Our first result shows that, in a sense, this problem is as close to being in P as one can get. We give a polynomial time deterministic algorithm that either correctly decides that no maximum matching has exactly k red edges, or exhibits a matching with m(G) − 1 edges having exactly k red edges. Hence, the additive error is one. We also present an efficient algorithm for the exact matching problem in families of graphs for which this problem is known to be tractable. We show how to count the number of exact perfect matchings in K3,3-minor free graphs (these include all planar graphs as well as many others) in O(n3.19) worst case time. Our algorithm can also count the number of perfect matchings in K3,3-minor free graphs in O(n2.19) time. [ABSTRACT FROM AUTHOR]

This paper discusses two advancements in the theory of designing truthful randomized mechanisms. Our first contribution is a new framework for developing truthful randomized mechanisms. The framework enables the construction of mechanisms with polynomially small failure probability. This is in contrast to previous mechanisms that fail with constant probability. Another appealing feature of the new framework is that bidding truthfully is a strongly dominant strategy. The power of the framework is demonstrated by an $O(\sqrt m)$-mechanism for combinatorial auctions that succeeds with probability $1-O(\frac {\log m} {\sqrt m})$. The other major result of this paper is an O(logmloglogm) randomized truthful mechanism for combinatorial auction with subadditive bidders. The best previously-known truthful mechanism for this setting guaranteed an approximation ratio of $O(\sqrt m)$. En route, the new mechanism also provides the best approximation ratio for combinatorial auctions with submodular bidders currently achieved by truthful mechanisms. [ABSTRACT FROM AUTHOR]

Let (X,dX) be an n-point metric space. We show that there exists a distribution over non-contractive embeddings into trees f:X→T such that for every x ∈ X, where C is a universal constant. Conversely we show that the above quadratic dependence on logn cannot be improved in general. Such embeddings, which we call maximum gradient embeddings, yield a framework for the design of approximation algorithms for a wide range of clustering problems with monotone costs, including fault-tolerant versions of k-median and facility location. [ABSTRACT FROM AUTHOR]

We study the problem embedding an n-point metric space into another n-point metric space while minimizing distortion. We show that there is no polynomial time algorithm to approximate the minimum distortion within a factor of Ω((logn)1/4 − δ) for any constant δ> 0, unless $\textnormal{NP} \subseteq \textnormal{DTIME}(n^{\textnormal{poly}(\log n))})$. We give a simple reduction from the METRIC LABELING problem which was shown to be inapproximable by Chuzhoy and Naor [10]. [ABSTRACT FROM AUTHOR]

We consider the following channel assignment problem arising in wireless networks. We are given a graph G = (V, E), and the number of wireless cards Cv for all v, which limit the number of colors that edges incident to v can use. We also have the total number of channels CG available in the network. For a pair of edges incident to a vertex, they are said to be conflicting if the colors assigned to them are the same. Our goal is to color edges (assign channels) so that the number of conflicts is minimized. We first consider the homogeneous network where Cv = k and CG ≥ Cv for all nodes v. The problem is NP-hard by a reduction from Edge coloring and we present two combinatorial algorithms for this case. The first algorithm is a distributed greedy method, which gives a solution with at most $(1 - \frac{1}{k})E$ more conflicts than the optimal solution. We also present an algorithm yielding at most V more conflicts than the optimal solution. The algorithm generalizes Vizing's algorithm in the sense that it gives the same result as Vizing's algorithm when k = Δ + 1. Moreover, we show that this approximation result is best possible unless P = NP. For the case where Cv = 1 or k, we show that the problem is NP-hard even when Cv = 1 or 2, and CG = 2, and present two algorithms. The first algorithm is completely combinatorial and produces a solution with at most $(2-\frac{1}{k}) OPT + (1 - \frac{1}{k}) E$ conflicts. We also develop an SDP-based algorithm, producing a solution with at most 1.122 OPT + 0.122 E conflicts for k = 2, and $(2-\Theta(\frac{\ln k}{k})) OPT + (1 - \Theta(\frac{\ln k}{k}))E$ conflicts in general. [ABSTRACT FROM AUTHOR]

The Max-Min allocation problem is to distribute indivisible goods to people so as to maximize the minimum utility of the people. We show a (2k − 1)-approximation algorithm for Max-Min when there are k people with subadditive utility functions. We also give a k/α-approximation algorithm (for α ≤ k/2) if the utility functions are additive and the utility of an item for a person is restricted to 0, 1 or U for some U > 1. The running time of this algorithm depends exponentially on the parameter α. Both the algorithms are combinatorial, simple and easy to analyze. [ABSTRACT FROM AUTHOR]

We consider the metric uncapacitated facility location problem(UFL). In this paper we modify the (1 + 2/e)-approximation algorithm of Chudak and Shmoys to obtain a new (1.6774,1.3738)- approximation algorithm for the UFL problem. Our linear programing rounding algorithm is the first one that touches the approximability limit curve $(\gamma_f, 1+2e^{-\gamma_f})$ established by Jain et al. As a consequence, we obtain the first optimal approximation algorithm for instances dominated by connection costs. Our new algorithm - when combined with a (1.11,1.7764)-approxima- tion algorithm proposed by Jain, Mahdian and Saberi, and later analyzed by Mahdian, Ye and Zhang - gives a 1.5-approximation algorithm for the metric UFL problem. This algorithm improves over the previously best known 1.52-approximation algorithm by Mahdian, Ye and Zhang, and it cuts the gap with the approximability lower bound by 1/3. The algorithm is also used to improve the approximation ratio for the 3-level version of the problem. [ABSTRACT FROM AUTHOR]

It is known that online knapsack is not competitive. This negative result remains true even if the items are removable. In this paper we consider online removable knapsack with resource augmentation, in which we hold a knapsack of capacity R ≥ 1.0 and aim at maintaining a feasible packing to maximize the total weight of the items packed. Accepted items can be removed to leave room for newly arriving items. Once an item is rejected/removed it can not be considered again. We evaluate an online algorithm by comparing the resulting packing to an optimal packing that uses a knapsack of capacity one. Optimal online algorithms are derived for both the weighted case (items have arbitrary weights) and the un-weighted case (the weight of an item is equal to its size). [ABSTRACT FROM AUTHOR]

We study various SDP formulations for Vertex Cover by adding different constraints to the standard formulation. We rule out approximations better than $2-O(\sqrt{\log \log n / \log n})$ even when we add the so-called pentagonal inequality constraints to the standard SDP formulation, and thus almost meet the best upper bound known due to Karakostas, of $2-\Omega(\sqrt{1 / \log n})$. We further show the surprising fact that by strengthening the SDP with the (intractable) requirement that the metric interpretation of the solution embeds into ℓ1 with no distortion, we get an exact relaxation (integrality gap is 1), and on the other hand if the solution is arbitrarily close to being ℓ1 embeddable, the integrality gap is 2 − o(1). Finally, inspired by the above findings, we use ideas from the integrality gap construction of Charikar to provide a family of simple examples for negative type metrics that cannot be embedded into ℓ1 with distortion better than 8/7 − ε. To this end we prove a new isoperimetric inequality for the hypercube. [ABSTRACT FROM AUTHOR]

A predicate is approximation resistant if no probabilistic polynomial time approximation algorithm can do significantly better then the naive algorithm that picks an assignment uniformly at random. Assuming that the Unique Games Conjecture is true we prove that most Boolean predicates are approximation resistant. [ABSTRACT FROM AUTHOR]

We study the Steiner Tree problem in the model of two-stage stochastic optimization with non-uniform inflation factors, and give a poly-logarithmic approximation factor for this problem. In this problem, we are given a graph G = (V,E), with each edge having two costs cM and cT (the costs for Monday and Tuesday, respectively). We are also given a probability distribution π: 2V →[0,1] over subsets of V, and will be given a client setS drawn from this distribution on Tuesday. The algorithm has to buy a set of edges EM on Monday, and after the client set S is revealed on Tuesday, it has to buy a (possibly empty) set of edges ET(S) so that the edges in EM ∪ ET(S) connect all the nodes in S. The goal is to minimize the cM(EM) + ES ←π[ cT( ET(S) ) ]. We give the first poly-logarithmic approximation algorithm for this problem. Our algorithm builds on the recent techniques developed by Chekuri et al. (FOCS 2006) for multi-commodity Cost-Distance. Previously, the problem had been studied for the cases when cT = σ×cM for some constant σ ≥ 1 (i.e., the uniform case), or for the case when the goal was to find a tree spanning all the vertices but Tuesday's costs were drawn from a given distribution $\widehat{\pi}$ (the so-called "stochastic MST case"). We complement our results by showing that our problem is at least as hard as the single-sink Cost-Distance problem (which is known to be Ω(loglogn) hard). Moreover, the requirement that Tuesday's costs are fixed seems essential: if we allow Tuesday's costs to dependent on the scenario as in stochastic MST, the problem becomes as hard as Label Cover (which is $\Omega(2^{\log^{1-\varepsilon} n})$-hard). As an aside, we also give an LP-rounding algorithm for the multi-commodity Cost-Distance problem, matching the O(log4n) approximation guarantee given by Chekuri et al. (FOCS 2006). [ABSTRACT FROM AUTHOR]

We investigate the problem of computing a minimum set of solutions that approximates within a specified accuracy ε the Pareto curve of a multiobjective optimization problem. We show that for a broad class of bi-objective problems (containing many important widely studied problems such as shortest paths, spanning tree, and many others), we can compute in polynomial time an ε-Pareto set that contains at most twice as many solutions as the minimum such set. Furthermore we show that the factor of 2 is tight for these problems, i.e., it is NP-hard to do better. We present further results for three or more objectives, as well as for the dual problem of computing a specified number k of solutions which provide a good approximation to the Pareto curve. [ABSTRACT FROM AUTHOR]

We consider the problem of covering and packing subsets of δ-hyperbolic metric spaces and graphs by balls. These spaces, defined via a combinatorial Gromov condition, have recently become of interest in several domains of computer science. Specifically, given a subset S of a δ-hyperbolic graph G and a positive number R, let γ(S,R) be the minimum number of balls of radius R covering S. It is known that computing γ(S,R) or approximating this number within a constant factor is hard even for 2-hyperbolic graphs. In this paper, using a primal-dual approach, we show how to construct in polynomial time a covering of S with at most γ(S,R) balls of (slightly larger) radius R + δ. This result is established in the general framework of δ-hyperbolic geodesic metric spaces and is extended to some other set families derived from balls. The covering algorithm is used to design better approximation algorithms for the augmentation problem with diameter constraints and for the k-center problem in δ-hyperbolic graphs. [ABSTRACT FROM AUTHOR]

A star graph is a tree of diameter at most two. A star forest is a graph that consists of node-disjoint star graphs. In the spanning star forest problem, given an unweighted graph G, the objective is to find a star forest that contains all the vertices of G and has the maximum number of edges. This problem is the complement of the dominating set problem in the following sense: On a graph with n vertices, the size of the maximum spanning star forest is equal to n minus the size of the minimum dominating set. We present a 0.71-approximation algorithm for this problem, improving upon the approximation factor of 0.6 of Nguyen et al. [9]. We also present a 0.64-approximation algorithm for the problem on node-weighted graphs. Finally, we present improved hardness of approximation results for the weighted versions of the problem. [ABSTRACT FROM AUTHOR]

We consider situations in which a decision-maker with a fixed budget faces a sequence of options, each with a cost and a value, and must select a subset of them online so as to maximize the total value. Such situations arise in many contexts, e.g., hiring workers, scheduling jobs, and bidding in sponsored search auctions. This problem, often called the online knapsack problem, is known to be inapproximable. Therefore, we make the enabling assumption that elements arrive in a random order. Hence our problem can be thought of as a weighted version of the classical secretary problem, which we call the knapsack secretary problem. Using the random-order assumption, we design a constant-competitive algorithm for arbitrary weights and values, as well as a e-competitive algorithm for the special case when all weights are equal (i.e., the multiple-choice secretary problem). In contrast to previous work on online knapsack problems, we do not assume any knowledge regarding the distribution of weights and values beyond the fact that the order is random. [ABSTRACT FROM AUTHOR]

The power dominating set (PDS) problem is the following extension of the well-known dominating set problem: find a smallest-size set of nodes S that power dominates all the nodes, where a node v is power dominated if (1) v is in S or v has a neighbor in S, or (2) v has a neighbor w such that w and all of its neighbors except v are power dominated. Note that rule (1) is the same as for the dominating set problem, and that rule (2) is a type of propagation rule that applies iteratively. We use n to denote the number of nodes. We show a hardness of approximation threshold of $2^{\log^{1-\epsilon}{n}}$ in contrast to the logarithmic hardness for dominating set. This is the first result separating these two problem. We give an $O(\sqrt{n})$ approximation algorithm for planar graphs, and show that our methods cannot improve on this approximation guarantee. We introduce an extension of PDS called ℓ-round PDS; for ℓ= 1 this is the dominating set problem, and for ℓ ≥ n − 1 this is the PDS problem. Our hardness threshold for PDS also holds for ℓ-round PDS for all ℓ ≥ 4. We give a PTAS for the ℓ-round PDS problem on planar graphs, for $\ell=O(\frac{\log{n}}{\log{\log{n}}})$. We study variants of the greedy algorithm, which is known to work well on covering problems, and show that the approximation guarantees can be Θ(n), even on planar graphs. Finally, we initiate the study of PDS on directed graphs, and show the same hardness threshold of $2^{\log^{1-\epsilon}{n}}$ for directed acyclic graphs. [ABSTRACT FROM AUTHOR]