Search

Initially developed for the min-knapsack problem, the knapsack cover inequalities are used in the current best relaxations for numerous combinatorial optimization problems of covering type. In spite of their widespread use, these inequalities yield linear programming (LP) relaxations of exponential size, over which it is not known how to optimize exactly in polynomial time. In this paper we address this issue and obtain LP relaxations of quasi-polynomial size that are at least as strong as that given by the knapsack cover inequalities. For the min-knapsack cover problem, our main result can be stated formally as follows: for any ε > 0, there is a (1/ε) O(1) n O(logn) -size LP relaxation with an integrality gap of at most 2 + ε, where n is the number of items. Previously, there was no known relaxation of subexponential size with a constant upper bound on the integrality gap. Our techniques are also sufficiently versatile to give analogous results for the closely related flow cover inequalities that are used to strengthen relaxations for scheduling and facility location problems., SCOPUS: ar.j, info:eu-repo/semantics/published

We study k-means clustering in a semi-supervised setting. Given an oracle that returns whether two given points belong to the same cluster in a fixed optimal clustering, we investigate the following question: how many oracle queries are sufficient to efficiently recover a clustering that, with probability at least (1 - delta), simultaneously has a cost of at most (1 + epsilon) times the optimal cost and an accuracy of at least (1 - epsilon)? We show how to achieve such a clustering on n points with O{((k^2 log n) * m{(Q, epsilon^4, delta / (k log n))})} oracle queries, when the k clusters can be learned with an epsilon' error and a failure probability delta' using m(Q, epsilon',delta') labeled samples in the supervised setting, where Q is the set of candidate cluster centers. We show that m(Q, epsilon', delta') is small both for k-means instances in Euclidean space and for those in finite metric spaces. We further show that, for the Euclidean k-means instances, we can avoid the dependency on n in the query complexity at the expense of an increased dependency on k: specifically, we give a slightly more involved algorithm that uses O{(k^4/(epsilon^2 delta) + (k^{9}/epsilon^4) log(1/delta) + k * m{({R}^r, epsilon^4/k, delta)})} oracle queries. We also show that the number of queries needed for (1 - epsilon)-accuracy in Euclidean k-means must linearly depend on the dimension of the underlying Euclidean space, and for finite metric space k-means, we show that it must at least be logarithmic in the number of candidate centers. This shows that our query complexities capture the right dependencies on the respective parameters.

An instance of the 2-Lin(2) problem is a system of equations of the form "x(i)+x(j)= b (mod 2)." Given such a system in which it is possible to satisfy all but an epsilon fraction of the equations, we show it is NP-hard to satisfy all but a C epsilon fraction of equations, for any C < 11/8 - 1.375 (and any 0 < epsilon <= 1/8). The previous best result, standing for over 15 years, had 5/4 in place of 11/8. Our result provides the best known NP-hardness even for the Unique-Games problem, and it also holds for the special case of Max-Cut. The precise factor 11/8 is unlikely to be best possible; we also give a conjecture concerning analysis of Boolean functions which, if true, would yield a larger hardness factor of 3/2. Our proof is by a modified gadget reduction from a pairwise-independent predicate. We also show an inherent limitation to this type of gadget reduction. In particular, any such reduction can never establish a hardness factor C greater than 2.54. Previously, no such limitations on gadget reductions was known., QC 20200414

An instance of the 2-Lin(2) problem is a system of equations of the form "xi + xj = b (mod 2)". Given such a system in which it’s possible to satisfy all but an C ε fraction of the equations, we show it is NP-hard to satisfy all but a Cε fraction of the equations, for any C < 11/8 = 1.375 (and any 0 < ε ≤ 1/8). The previous best result, standing for over 15 years, had 5/4 in place of 11/8. Our result provides the best known NP-hardness even for the Unique-Games problem, and it also holds for the special case of Max-Cut. The precise factor 11 8 is unlikely to be best possible; we also give a conjecture concerning analysis of Boolean functions which, if true, would yield a larger hardness factor of 3/2. Our proof is by a modified gadget reduction from a pairwise-independent predicate. We also show an inherent limitation to this type of gadget reduction. In particular, any such reduction can never establish a hardness factor C greater than 2.54. Previously, no such limitation on gadget reductions was known., QC 20160517

An instance of the 2-Lin(2) problem is a system of equations of the form "x_i + x_j = b (mod 2)". Given such a system in which it's possible to satisfy all but an epsilon fraction of the equations, we show it is NP-hard to satisfy all but a C*epsilon fraction of the equations, for any C < 11/8 = 1.375 (and any 0 < epsilon <= 1/8). The previous best result, standing for over 15 years, had 5/4 in place of 11/8. Our result provides the best known NP-hardness even for the Unique Games problem, and it also holds for the special case of Max-Cut. The precise factor 11/8 is unlikely to be best possible; we also give a conjecture concerning analysis of Boolean functions which, if true, would yield a larger hardness factor of 3/2. Our proof is by a modified gadget reduction from a pairwise-independent predicate. We also show an inherent limitation to this type of gadget reduction. In particular, any such reduction can never establish a hardness factor C greater than 2.54. Previously, no such limitation on gadget reductions was known.

An instance of the 2-Lin(2) problem is a system of equations of the form "x_i + x_j = b (mod 2)". Given such a system in which it's possible to satisfy all but an epsilon fraction of the equations, we show it is NP-hard to satisfy all but a C*epsilon fraction of the equations, for any C < 11/8 = 1.375 (and any 0 < epsilon <= 1/8). The previous best result, standing for over 15 years, had 5/4 in place of 11/8. Our result provides the best known NP-hardness even for the Unique Games problem, and it also holds for the special case of Max-Cut. The precise factor 11/8 is unlikely to be best possible; we also give a conjecture concerning analysis of Boolean functions which, if true, would yield a larger hardness factor of 3/2. Our proof is by a modified gadget reduction from a pairwise-independent predicate. We also show an inherent limitation to this type of gadget reduction. In particular, any such reduction can never establish a hardness factor C greater than 2.54. Previously, no such limitation on gadget reductions was known.

For every integer k ≥ 3, we prove that there is a predicate P on k Boolean variables with (Formula Presented) accepting assignments that is approximation resistant even on satisfiable instances. That is, given a satisfiable CSP instance with constraint P, we cannot achieve better approximation ratio than simply picking random assignments. This improves the best previously known result by Håstad and Khot (Theory of Computing, 2005) who showed that a predicate on k variables with 2O(k1/2) accepting assignments is approximation resistant on satisfiable instances. Our construction is inspired by several recent developments. One is the idea of using direct sums to improve soundness of PCPs, developed by Siu On Chan (STOC, 2013). We also use techniques from Cenny Wenner (Theory of Computing, 2013) to construct PCPs with perfect completeness without relying on the d-to-1 Conjecture., QC 20211008

For every integer k≥ 3, we prove that there is a predicate P on k Boolean variables with 2O(k1/3) accepting assignments that is approximation resistant even on satisfiable instances. That is, given a satisfiable CSP instance with constraint P, we cannot achieve better approximation ratio than simply picking random assignments. This improves the best previously known result by Hastad and Khot where the predicate has 2 O(k1/2) accepting assignments. Our construction is inspired by several recent developments. One is the idea of using direct sums to improve soundness of PCPs, developed by Chan [5]. We also use techniques from Wenner [32] to construct PCPs with perfect completeness without relying on the d-to-1 Conjecture., QC 20130719

We explore the intricate interdependent relationship among counting problems, considered from three frameworks for such problems: Holant Problems, counting CSP and weighted H-colorings. We consider these problems for general complex valued functions that take boolean inputs. We show that results from one framework can be used to derive results in another, and this happens in both directions. Holographic reductions discover an underlying unity, which is only revealed when these counting problems are investigated in the complex domain a",. We prove three complexity dichotomy theorems, leading to a general theorem for Holant (c) problems. This is the natural class of Holant problems where one can assign constants 0 or 1. More specifically, given any signature grid on G=(V,E) over a set of symmetric functions, we completely classify the complexity to be in P or #P-hard, according to F , of Sigma Pi f(v)(sigma vertical bar E(v)), sigma:E ->{0,1}v epsilon V where f(v) epsilon F boolean OR {0, 1} (0, 1 are the unary constant 0, 1 functions). Not only is holographic reduction the main tool, but also the final dichotomy can be only naturally stated in the language of holographic transformations. The proof goes through another dichotomy theorem on Boolean complex weighted #CSP., QC 20121004

Holant is a framework of counting characterized by local constraints. It is closely related to other well-studied frameworks such as #CSP and Graph Homomorphism. An effective dichotomy for such frameworks can immediately settle the complexity of all combinatorial problems expressible in that framework. Both #CSP and Graph Homomorphism can be viewed as sub-families of Holant with the additional assumption that the equality constraints are always available. Other subfamilies of Holant such as Holant* and Holant(c) problems, in which we assume some specific sets of constraints to be freely available, were also studied. The Holant framework becomes more expressive and contains more interesting tractable cases with less or no freely available constraint functions, while, on the other hand, it also becomes more challenging to obtain a complete characterization of its time complexity. Recently, complexity dichotomy for a variety of sub-families of Holant such as #CSP, Graph Homomorphism, Holant* and Holant(c) were proved. The dichotomy for the general Holant framework, which is the most desirable, still remains open. In this paper, we prove a dichotomy for the general Holant framework where all the constraints are real symmetric functions. This setting already captures most of the interesting combinatorial problems defined by local constraints, such as (perfect) matching, independent set, vertex cover and so on. This is the first time a dichotomy is obtained for general Holant Problems without any auxiliary functions. One benefit of working with Holant framework is some powerful new reduction techniques such as Holographic reduction. Along the proof of our dichotomy, we introduce a new reduction technique, namely realizing a constraint function by approximating it. This new technique is employed in our proof in a situation where it seems that all previous reduction techniques fail, thus this new idea of reduction might also be of independent interest. Besides proving dicho, QC 20121109

We prove a complexity dichotomy theorem for counting weighted Boolean CSP modulo k for any positive integer $k>1$. This generalizes a theorem by Faben for the unweighted setting. In the weighted setting, there are new interesting tractable problems. We first prove a dichotomy theorem for the finite field case where k is a prime. It turns out that the dichotomy theorem for the finite field is very similar to the one for the complex weighted Boolean #CSP, found by [Cai, Lu and Xia, STOC 2009]. Then we further extend the result to an arbitrary integer k.