IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

We study the approximability of (Finite-)Valued Constraint Satisfaction Problems (VCSPs) with a fixed finite constraint language Γ consisting of finitary functions on a fixed finite domain. Ene et al. have shown that, under a mild technical condition, the basic LP relaxation is optimal for constant-factor approximation for VCSP(Γ) unless the Unique Games Conjecture fails. Using the algebraic approach to the CSP, we give new natural algebraic conditions for the finiteness of the integrality gap for the basic LP relaxation of VCSP(Γ) and show how this leads to efficient constant-factor approximation algorithms for several examples that cover all previously known cases that are NP-hard to solve to optimality but admit constant-factor approximation. Finally, we show that the absence of another algebraic condition leads to NP-hardness of constant-factor approximation. Thus, our results indicate where the boundary of constant-factor approximability for VCSPs lies. © 2018 Elsevier Inc.

Department of Computer Science and Engineering

Fulltext

Journal of Computer and System Sciences

Towards a characterization of constant-factor approximable finite-valued CSPs

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 &lt; 11/8 = 1.375 (and any 0 &lt; ε ≤ 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. © Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, and John Wright.

Leibniz International Proceedings in Informatics, LIPIcs

Improved NP-inapproximability for 2-variable linear equations

We show improved NPNP-hardness of approximating Ordering-Constraint Satisfaction Problems (OCSPs). For the two most well-studied OCSPs, Maximum Acyclic Subgraph and Maximum Betweenness, we prove NPNP-hard approximation factors of 14/15+ε14/15+ε and 1/2+ε1/2+ε. When it is hard to approximate an OCSP by a constant better than taking a uniformly-at-random ordering, then the OCSP is said to be approximation resistant. We show that the Maximum Non-Betweenness Problem is approximation resistant and that there are width-mm approximation-resistant OCSPs accepting only a fraction 1/(m/2)! of assignments. These results provide the first examples of approximation-resistant OCSPs subject only to P≠NP. © 2015 Per Austrin, Rajsekar Manokaran, and Cenny Wenner.

World University root node

Theory of Computing

On the NP-hardness of approximating ordering-constraint satisfaction problems

We show that for every positive ε &gt; 0, unless NP ∪ BPQP, it is impossible to approximate the maximum quadratic assignment problem within a factor better than 2log1?ε n by a reduction from the maximum label cover problem. Our result also implies that Approximate Graph Isomorphism is not robust and is, in fact, 1 ? ε versus ε hard assuming the Unique Games Conjecture. Then, we present an O(√n)- approximation algorithm for the problem based on rounding of the linear programming relaxation often used in state-of-the-art exact algorithms. © 2014 ACM.

ACM Transactions on Algorithms

Maximum quadratic assignment problem: Reduction from maximum label cover and LP-based approximation algorithm

We show improved NP-hardness of approximating Ordering Constraint Satisfaction Problems (OCSPs). For the two most well-studied OCSPs, Maximum Acyclic Subgraph and Maximum Betweenness, we prove inapproximability of 14/15 + ε and 1/2 + ε. An OCSP is said to be approximation resistant if it is hard to approximate better than taking a uniformly random ordering. We prove that the Maximum Non- Betweenness Problem is approximation resistant and that there are width-m approximation-resistant OCSPs accepting only a fraction 1/(m/2)! of assignments. These results provide the first examples of approximation-resistant OCSPs subject only to P ≠ NP. Our reductions from Label Cover differ from previous works in two ways. First, we establish a somewhat general bucketing lemma permitting us to reduce the analysis of ordering predicates to that of classical predicates. Second, instead of "folding", which is not available for ordering predicates, we employ permuted instantiations of the predicates to limit the value of poorly correlated strategies. © 2013 Springer-Verlag.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

On the NP-hardness of approximating ordering constraint satisfaction problems

Quadratic Programming (QP) is the well-studied problem of maximizing over {-1,1} values the quadratic form ∑i≠j aij x i xj. QP captures many known combinatorial optimization problems, and assuming the Unique Games conjecture, Semidefinite Programming (SDP) techniques give optimal approximation algorithms. We extend this body of work by initiating the study of Quadratic Programming problems where the variables take values in the domain {-1,0,1}. The specific problem we study is (Formula Presented) This is a natural relative of several well studied problems (in fact Trevisan introduced a normalized variant as a stepping stone towards a spectral algorithm for Max Cut Gain). Quadratic ratio problems are good testbeds for both algorithms and complexity because the techniques used for quadratic problems for the {-1,1} and {0,1} domains do not seem to carry over to the {-1,0,1} domain. We give approximation algorithms and evidence for the hardness of approximating these problems. We consider an SDP relaxation obtained by adding constraints to the natural eigenvalue (or SDP) relaxation for this problem. Using this, we obtain an Õ(n1/3) approximation algorithm for QP-ratio. We also give a approximation for bipartite graphs, and better algorithms for special cases. As with other problems with ratio objectives (e.g. uniform sparsest cut), it seems difficult to obtain inapproximability results based on P ≠ NP. We give two results that indicate that QP-Ratio is hard to approximate to within any constant factor: one is based on the assumption that random instances of Max k-AND are hard to approximate, and the other makes a connection to a ratio version of Unique Games. We also give a natural distribution on instances of QP-Ratio for which an n ε approximation (for ε roughly 1/10) seems out of reach of current techniques. © 2012 Springer-Verlag.

On quadratic programming with a ratio objective

Suppose we are given an oracle that claims to approximate the permanent for most matrices X, where X is chosen from the Gaussian ensemble (the matrix entries are i.i.d. univariate complex Gaussians). Can we test that the oracle satisfies this claim? This paper gives a polynomial-time algorithm for the task. The oracle-testing problem is of interest because a recent paper of Aaronson and Arkhipov showed that if there is a polynomial-time algorithm for simulating boson-boson interactions in quantum mechanics, then an approximation oracle for the permanent (of the type described above) exists in BPP NP. Since computing the permanent of even 0/1 matrices is #P-complete, this seems to demonstrate more computational power in quantum mechanics than Shor's factoring algorithm does. However, unlike factoring, which is in NP, it was unclear previously how to test the correctness of an approximation oracle for the permanent, and this is the contribution of the paper. The technical difficulty overcome here is that univariate polynomial self-correction, which underlies similar oracle-testing algorithms for permanent over -and whose discovery led to a revolution in complexity theory-does not seem to generalize to complex (or even, real) numbers. We believe that this tester will motivate further progress on understanding the permanent of Gaussian matrices. © 2012 Springer-Verlag.

Testing permanent oracles - Revisited

We prove that, assuming the Unique Games conjecture (UGC), every problem in the class of ordering constraint satisfaction problems (OCSPs) where each constraint has constant arity is approximation resistant. In other words, we show that if ρ is the expected fraction of constraints satisfied by a random ordering, then obtaining a p′ approximation for any p′ &gt; ρ is UG-hard. For the simplest OCSP, the Maximum Acyclic Subgraph (MAS) problem, this implies that obtaining a ρ-approximation for any constant ρ &gt; 1/2 is UG-hard. Specifically, for every constant ε &gt; 0 the following holds: given a directed graph G that has an acyclic subgraph consisting of a fraction (1ρε) of its edges, it is UG-hard to find one with more than (1/2 + ε) of its edges. Note that it is trivial to find an acyclic subgraph with 1/2 the edges by taking either the forward or backward edges in an arbitrary ordering of the vertices of G. The MAS problem has been well studied, and beating the random ordering for MAS has been a basic open problem. An OCSP of arity k is specified by a subset π ⊆ Sk of permutations on {1, 2, ⋯ , k}. An instance of such an OCSP is a set V and a collection of constraints, each of which is an ordered k-tuple of V . The objective is to find a global linear ordering of V while maximizing the number of constraints ordered as in ρ. A random ordering of V is expected to satisfy a ρ = \π\k! fraction. We show that, for any fixed k, it is hard to obtain a p′-approximation for π-OCSP for any p′ ρ. The result is in fact stronger: we show that for every λ ⊆ π ⊆ Sk, and an arbitrarily small ε, it is hard to distinguish instances where a (1 - ε) fraction of the constraints can be ordered according to λ from instances where at most a (1 + ε) fraction can be ordered as in π. A special case of our result is that the Betweenness problem is hard to approximate beyond a factor 1/3. The results naturally generalize to OCSPs which assign a payoff to the different permutations. Finally, our results imply (unconditionally) that a simple semidefinite relaxation for MAS does not suffice to obtain a better approximation. © 2011 Society for Industrial and Applied Mathematics.

SIAM Journal on Computing

Beating the random ordering is hard: Every ordering csp is approximation resistant

In a beautiful result, Raghavendra established optimal Unique Games Conjecture (UGC)-based inapproximability for a large class of constraint satisfaction problems (CSPs). In the class of CSPs he considers, of which Maximum Cut is a prominent example, the goal is to find an assignment which maximizes a weighted fraction of constraints satisfied. He gave a generic semi-definite program (SDP) for this class of problems and showed how the approximability of each problem is determined by the corresponding SDP (upto an arbitrarily small additive error) assuming the UGC. He noted that his techniques do no apply to CSPs with strict constraints (all of which must be satisfied) such as Vertex Cover. In this paper we address the approximability of these strict-CSPs. In the class of CSPs we consider, one is given a set of constraints over a set of variables, and a cost function over the assignments, the goal is to find an assignment to the variables of minimum cost which satisfies all the constraints. We present a generic linear program (LP) for a large class of strict-CSPs and give a systematic way to convert integrality gaps for this LP into UGC-based inapproximability results. Some important problems whose approximability our framework captures are VERTEX COVER, HYPERGRAPH VERTEX COVER, &k-partite-HYPERGRAPH VERTEX COVER, INDEPENDENT SET and other covering and packing problems over q-ary alphabets, and a scheduling problem. For the covering and packing problems, which occur quite commonly in practice as well, we provide a matching rounding algorithm, thus settling their approximability upto an arbitrarily small additive error.

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

On LP-based Approximability for strict CSPs

A permutation constraint satisfaction problem (permCSP) of arity k is specified by a subset Λ ⊆ S k of permutations on {1, 2, . . ., k}. An instance of such a permCSP consists of a set of variables V and a collection of constraints each of which is an ordered k-tuple of V . The objective is to find a global ordering σ of the variables that maximizes the number of constraint tuples whose ordering (under σ) follows a permutation in Λ. This is just the natural extension of constraint satisfaction problems over finite domains (such as Boolean CSPs) to the world of ordering problems. The simplest permCSP corresponds to the case when Λ consists of the identity permutation on two variables. This is just the Maximum Acyclic Subgraph (MAS) problem. It was recently shown that the MAS problem is Unique-Games hard to approximate within a factor better than the trivial 1/2 achieved by a random ordering [6]. Building on this work, in this paper we show that for every permCSP of arity 3, beating the random ordering is Unique-Games hard. The result is in fact stronger: we show that for every Λ ⊆ Π ⊆ S 3, given an instance of permCSP(Λ) that is almost-satisfiable, it is hard to find an ordering that satisfies more than |Π|/6 + ε of the constraints even under the relaxed constraint Π (for arbitrary ε &gt; 0). A special case of our result is that the Betweenness problem is hard to approximate beyond a factor 1/3. Interestingly, for satisfiable instances of Betweenness, a factor 1/2 approximation algorithm is known. Thus, every permutation CSP of arity up to 3 resists approximation beyond the trivial random ordering threshold. In contrast, for Boolean CSPs, there are both approximation resistant and non-trivially approximable CSPs of arity 3. © 2009 IEEE.

Proceedings of the Annual IEEE Conference on Computational Complexity

Every permutation CSP of arity 3 is approximation resistant

We prove that approximating the MAX ACYCLIC SUBGRAPH problem within a factor better than 1/2 is Unique Games hard. Specifically, for every constant ε > 0 the following holds: given a directed graph G that has an acyclic subgraph consisting of a fraction (1 - ε) of its edges, if one can efficiently find an acyclic subgraph of G with more than (1/2 + ε) of its edges, then the UGC is false. Note that it is trivial to find an acyclic subgraph with 1/2 the edges, by taking either the forward or backward edges in an arbitrary ordering of the vertices of G. The existence of a p-approximation algorithm for ρ > 1/2 has been a basic open problem for a while. Our result is the first tight inapproximability result for an ordering problem. The starting point of our reduction is a directed acyclic subgraph (DAG) in which every cut is nearly-balanced in the sense that the number of forward and backward edges crossing the cut are nearly equal; such DAGs were constructed in [2]. Using this, we are able to study MAX ACYCLIC SUBGRAPH, which is a constraint satisfaction problem (CSP) over an unbounded domain, by relating it to a proxy CSP over a bounded domain. The latter is then amenable to powerful techniques based on the invariance principle [12,17]. Our results also give a super-constant factor inapproximability result for the MIN FEEDBACK ARC SET problem. Using our reductions, we also obtain SDP integrality gaps for both the problems. © 2008 IEEE.

Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

Beating the random ordering is hard: inapproximability of maximum acyclic subgraph

The connection between integrality gaps and computational hardness of discrete optimization problems is an intriguing question. In recent years, this connection has prominently figured in several tight UGG-based hardness results. We show in this paper a direct way of turning integrality gaps into hardness results for several fundamental classification problems. Specifically, we convert linear programming integrality gaps for the Multiway Cut, O-Extension and Metric Labeling problems into UGC-based hardness results. Qualitatively, our result suggests that if the unique games conjecture is true then a linear relaxation of the latter problems studied in several papers (so-called earthrnover linear program) yields the best possible approximation. Taking this a step further, we also obtain integrality gaps for a semi-definite programming relaxation matching the integrality gaps of the earthrnover linear program. Prior to this work, there was an intriguing possibility of obtaining better approximation factors for labeling problems via semi-definite programming. Copyright 2008 ACM.

Proceedings of the Annual ACM Symposium on Theory of Computing

SDP gaps and UGC hardness for multiway cut, O-extension, and metric labeling

Consider a network in which a collection of source nodes maintain and periodically update data objects for a collection of sink nodes, each of which periodically accesses the data originating from some specified subset of the source nodes. We consider the task of efficiently relaying the dynamically changing data objects to the sinks from their sources of interest. Our focus is on the following "push-pull" approach for this data dissemination problem. Whenever a data object is updated, its source relays the update to a designated subset of nodes, its push set; similarly, whenever a sink requires an update, it propagates its query to a designated subset of nodes, its pull set. The push and pull sets need to be chosen such that every pull set of a sink intersects the push sets of all its sources of interest. We study the problem of choosing push sets and pull sets to minimize total global communication while satisfying all communication requirements. We formulate and study several variants of the above data dissemination problem, that take into account different paradigms for routing between sources (resp., sinks) and their push sets (resp., pull sets) - multicast, unicast, and controlled broadcast - as well as the aggregability of the data objects. Under the multicast model, we present an optimal polynomial time algorithm for tree networks, which yields a randomized O(log n)-approximation algorithm for n-node general networks, for which the problem is hard to approximate within a constant factor. Under the unicast model, we present a randomized O(log n)-approximation algorithm for non-metric costs and a matching hardness result. For metric costs, we present an O(1)-approximation and matching hardness result for the case where the interests of any two sinks are either disjoint or identical. Finally, under the controlled broadcast model, we present optimal polynomial-time algorithms. While our optimization problems have been formulated in the context of data communication in networks, our problems also have applications to network design and multicommodity facility location and are of independent interest. Copyright 2006 ACM.