Robust Approximation of Temporal CSP

DOI10.4230/LIPICS.APPROX-RANDOM.2014.419MaRDI QIDQ2969636zbMATH OpenOpenAlexFDO

Authors Suguru Tamaki, Yuichi Yoshida

Publication date 22 March 2017

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2014/4713/pdf/30.pdf

zbMATH Keywords

approximation algorithmconstraint satisfactionhardness of approximationinfinite domainmaximum satisfiability

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• Tractable combinations of temporal CSPs
• scientific article; zbMATH DE number 4185056
• The complexity of temporal constraint satisfaction problems
• Efficient Temporal Satisfiability
• scientific article; zbMATH DE number 2202277
• STCSP -- structured temporal constraint satisfaction problems
• Tractable approximations for temporal constraint handling
• scientific article; zbMATH DE number 2089861

Cited in

(2)

• Robust algorithms with polynomial loss for near-unanimity CSPs
• Robust algorithms with polynomial loss for near-unanimity CSPs

This page was built for publication: Robust Approximation of Temporal CSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2969636)