NDLI: On LP-based approximability for strict CSPs

Please wait, while we are loading the content...

Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with sub-constant error

The streaming complexity of cycle counting, sorting by reversals, and other problems

Streaming k-means on well-clusterable data

Efficient sketches for the set query problem

Exponential time improvement for min-wise based algorithms

A simple and fast 2-approximation algorithm for the one-warehouse multi-retailers problem

Generalized machine activation problems

An online scalable algorithm for minimizing $l_{k}-norms$ of weighted flow time on unrelated machines

Online scalable scheduling for the $l_{k}-norms$ of flow time without conservation of work

Online scheduling on identical machines using SRPT

A complete resolution of the Keller maximum clique problem

On independent sets in random graphs

Coloring random graphs online without creating monochromatic subgraphs

The maximum size of a Sidon set contained in a sparse random set of integers

On Buffon machines and numbers

Graph coloring via the probabilistic method

An almost optimal unrestricted fast Johnson-Lindenstrauss transform

A Stackelberg strategy for routing flow over time

A subexponential lower bound for the random facet algorithm for parity games

On minmax theorems for multiplayer games

Near-optimal no-regret algorithms for zero-sum games

Local smoothness and the price of anarchy in atomic splittable congestion games

I/O-efficient contour queries on terrains

Implicit flow routing on terrains with applications to surface networks and drainage structures

Shortest non-crossing walks in the plane

Computing shortest paths amid pseudodisks

On the complexity of time-dependent shortest paths

A master theorem for discrete divide and conquer recurrences

Optimal pattern matching in LZW compressed strings

Random access to grammar-compressed strings

Ordered and unordered top-K range reporting in large data sets

Top-K color queries for document retrieval

Mobile geometric graphs: detection, coverage and percolation

Randomized diffusion for indivisible loads

Fast information spreading in graphs with large weak conductance

On the randomness requirements of rumor spreading

Rumor spreading and vertex expansion on regular graphs

Bin packing via discrepancy of permutations

Algorithms and hardness for subspace approximation

Approximating matrix p-norms

Subsampling mathematical relaxations and average-case complexity

Towards an SDP-based approach to spectral methods: a nearly-linear-time algorithm for graph partitioning and decomposition

Faster quantum algorithm for evaluating game trees

Reflections for quantum query algorithms

Temperature 1 self-assembly: deterministic assembly in 3D and probabilistic assembly in 2D

The power of nondeterminism in self-assembly

Algorithms for implicit hitting set problems

An algorithmic decomposition of claw-free graphs leading to an $O(n^{3})-algorithm$ for the weighted stable set problem

Randomized greedy: new variants of some classic approximation algorithms

Randomized variants of Johnson's algorithm for MAX SAT

The local lemma is tight for SAT

Pricing on paths: a PTAS for the highway problem

On the approximability of budget feasible mechanisms

Welfare guarantees for combinatorial auctions with item bidding

Mechanism design via correlation gap

Bayesian incentive compatibility via fractional assignments

Bayesian incentive compatibility via matchings

Bidimensionality and EPTAS

Slightly superexponential parameterized problems

Known algorithms on graphs of bounded treewidth are probably optimal

Continuous local search

Range selection and median: tight cell probe lower bounds and adaptive data structures

Where computer vision needs help from computer science

An optimal-time construction of sparse Euclidean spanners with tiny diameter

Fast, precise and dynamic distance queries

Approximate nearest neighbor search for low dimensional queries

Dimensionality reduction: beyond the Johnson-Lindenstrauss bound

A nonlinear approach to dimension reduction

Hitting time results for Maker-Breaker games: extended abstract

Packing tight Hamilton cycles in 3-uniform hypergraphs

Networks of random cycles

Phase transition for Glauber dynamics for independent sets on regular trees

On belief propagation guided decimation for random k-SAT

The asymmetric traveling salesman problem on graphs with bounded genus

Capacitated Metric Labeling

Multicommodity facility location under group Steiner access cost

Survivable network design problems in wireless networks

Prize-collecting Steiner problems on planar graphs

On graph crossing number and edge planarization

Ranking with submodular valuations

Multi-budgeted matchings and matroid intersection via dependent rounding

Submodular maximization by simulated annealing

The matroid median problem

Persistent predecessor search and orthogonal point location on the word RAM

New approximation algorithms for minimum enclosing convex shapes

Computing the independence number of intersection graphs

Minimum cuts and shortest non-separating cycles via homology covers

Embedding stacked polytopes on a polynomial-size grid

Overlap properties of geometric expanders: extended abstract

On the degree distribution of random planar graphs

Component structure of the vacant set induced by a random walk on a random graph

The multiple-orientability thresholds for random hypergraphs

The rigidity transition in random graphs

Online vertex-weighted bipartite matching and single-bid budgeted allocations

Secretary problems: laminar matroid and interval scheduling

Matroid secretary problem in the random assignment model

Online stochastic matching: online actions based on offline statistics

An optimal lower bound for buffer management in multi-queue switches

An intersection model for multitolerance graphs: efficient algorithms and hierarchy

Faster and dynamic algorithms for maximal end-component decomposition and related graph problems in probabilistic verification

Faster replacement paths

Computing replacement paths in surface embedded graphs

Improved dynamic algorithms for maintaining approximate shortest paths under deletions

Algebraic algorithms for linear matroid parity problems

On parity check (0, 1)-matrix over $Z_{p}$

Code equivalence and group isomorphism

Efficient algorithms for some special cases of the polynomial equivalence problem

Low rank matrix-valued chernoff bounds and approximate matrix multiplication

Computational geometry for non-geometers: recent developments on some classical problems

Improved deterministic algorithms for decremental transitive closure and strongly connected components

Approximating the girth

Approximating the statistics of various properties in randomly weighted graphs

Counting and detecting small subgraphs via equations and matrix multiplication

On succinct convex greedy drawing of 3-connected plane graphs

Distributed selfish load balancing on networks

On the complexity of approximating a Nash equilibrium

Fast convergence of natural bargaining dynamics in exchange networks

Wireless capacity with oblivious power in general metrics

A constant-factor approximation for wireless capacity maximization with power control in the SINR model

On LP-based approximability for strict CSPs

Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set

Hardness results for agnostically learning low-degree polynomial threshold functions

Tight hardness results for minimizing discrepancy

The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number

Risk-averse stochastic optimization: probabilistically-constrained models and algorithms for black-box distributions

Improved approximation results for stochastic knapsack problems

The stubborn problem is stubborn no more: a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem

Approximate dynamic programming using halfspace queries and multiscale Monge decomposition

Nearly tight bounds for testing function isomorphism

The dichotomy of list homomorphisms for digraphs

Dichotomy for Holant problems of Boolean domain

Bounding the randomized decision tree complexity of read-once Boolean functions

Improved space bounds for cache-oblivious range reporting

Triangulating the square and squaring the triangle: quadtrees and Delaunay triangulations are equivalent

Improved bound for the union of fat triangles

On LP-based approximability for strict CSPs

Content Provider	ACM Digital Library
Author	Tulsiani, Madhur Manokaran, Rajsekar Kumar, Amit Vishnoi, Nisheeth K.
Abstract	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.
Starting Page	1560
Ending Page	1573
Page Count	14
File Format	PDF
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-01-23
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in