Robust algorithms with polynomial loss for near-unanimity CSPs
- Submitting institution
-
University of Durham
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 125030
- Type
- D - Journal article
- DOI
-
10.1137/18M1163932
- Title of journal
- SIAM Journal on Computing
- Article number
- -
- First page
- 1763
- Volume
- 48
- Issue
- 6
- ISSN
- 00975397
- Open access status
- Compliant
- Month of publication
- -
- Year of publication
- 2019
- URL
-
https://doi.org/10.1137/18M1163932
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
5
- Research group(s)
-
B - Algorithms and Complexity
- Citation count
- 0
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The conference version appeared in SODA. The paper presents an approximation algorithm for CSPs that finds an almost satisfying solution for any almost satisfiable CSP instance, where the possible loss in satisfaction of the produced solution is well-behaved. Our algorithm works for all CSPs satisfying a certain sufficient structural condition, which is very close to a known necessary condition for the existence (modulo complexity theoretic assumptions) of algorithms with such loss.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -