首页    期刊浏览 2024年12月02日 星期一
登录注册

文章基本信息

  • 标题:Simultaneous Approximation of Constraint Satisfaction Problems
  • 本地全文:下载
  • 作者:Amey Bhangale ; Swastik Kopparty ; Sushant Sachdeva
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Given k collections of 2SAT clauses on the same set of variables V , can we find one assignment that satisfies a large fraction of clauses from each collection? We consider such simultaneous constraint satisfaction problems, and design the first nontrivial approximation algorithms in this context.

    Our main result is that for every CSP F , for k O ( log 1 4 n ) , there is a polynomial time constant factor Pareto approximation algorithm for k simultaneous Max-F-CSP instances. Our methods are quite general, and we also use them to give an improved approximation factor for simultaneous Max-w-SAT (for k O ( log 1 3 n ) ). In contrast, for k = ( log n ) , no nonzero approximation factor for k simultaneous Max-F-CSP instances can be achieved in polynomial time (assuming the Exponential Time Hypothesis).

    These problems are a natural meeting point for the theory of constraint satisfaction problems and multiobjective optimization. We also suggest a number of interesting directions for future research.

  • 关键词:Constraint satisfaction problems ; multiobjective optimization
国家哲学社会科学文献中心版权所有