Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > BETWEENNESS:
Reports tagged with Betweenness:
TR12-074 | 12th June 2012
Venkatesan Guruswami, Yuan Zhou

Approximating Bounded Occurrence Ordering CSPs

A theorem of HÃ¥stad shows that for every constraint satisfaction problem (CSP) over a fixed size domain, instances where each variable appears in at most $O(1)$ constraints admit a non-trivial approximation algorithm, in the sense that one can beat (by an additive constant) the approximation ratio achieved by the naive ... more >>>


TR21-064 | 5th May 2021
Noah Singer, Madhu Sudan, Santhoshini Velusamy

Streaming approximation resistance of every ordering CSP

An ordering constraint satisfaction problem (OCSP) is given by a positive integer $k$ and a constraint predicate $\Pi$ mapping permutations on $\{1,\ldots,k\}$ to $\{0,1\}$. Given an instance of OCSP$(\Pi)$ on $n$ variables and $m$ constraints, the goal is to find an ordering of the $n$ variables that maximizes the number ... more >>>




ISSN 1433-8092 | Imprint