Conference item icon

Conference item

Treewidth-pliability and PTAS for Max-CSPs

Abstract:

We identify a sufficient condition, treewidth-pliability, that gives a polynomial-time approximation scheme (PTAS) for a large class of Max-2-CSPs parametrised by the class of allowed constraint graphs (with arbitrary constraints on an unbounded alphabet). Our result applies more generally to the maximum homomorphism problem between two rational-valued structures. The condition unifies the two main approaches for designing PTASes. One is Baker’s layering technique, which applies to sparse gra...

Expand abstract
Publication status:
Accepted
Peer review status:
Peer reviewed

Actions


Authors


Wrochna, M More by this author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author, Depositor
ORCID:
0000-0002-0263-159X
Publisher:
Society for Industrial and Applied Mathematics Publisher's website
Journal:
ACM-SIAM Symposium on Discrete Algorithms (SODA21) Journal website
Acceptance date:
2020-09-30
Event title:
ACM-SIAM Symposium on Discrete Algorithms (SODA21)
Pubs id:
1136443
Local pid:
pubs:1136443
Language:
English
Keywords:

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP