Optimization, randomized approximability, and Boolean constraint satisfaction problems

DOI10.1007/978-3-642-25591-5_47MaRDI QIDQ3104640zbMATH OpenOpenAlexFDO

Authors Tomoyuki Yamakami

Publication date 16 December 2011

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.3651

zbMATH Keywords

approximation algorithmconstraint satisfaction problemoptimization problemAPXapproximation-preserving reducibilityPO

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Analysis of algorithms and problem complexity (68Q25)

Abstract: We give a unified treatment to optimization problems that can be expressed in the form of nonnegative-real-weighted Boolean constraint satisfaction problems. Creignou, Khanna, Sudan, Trevisan, and Williamson studied the complexity of approximating their optimal solutions whose optimality is measured by the sums of outcomes of constraints. To explore a wider range of optimization constraint satisfaction problems, following an early work of Marchetti-Spaccamela and Romano, we study the case where the optimality is measured by products of constraints' outcomes. We completely classify those problems into three categories: PO problems, NPO-hard problems, and intermediate problems that lie between the former two categories. To prove this trichotomy theorem, we analyze characteristics of nonnegative-real-weighted constraints using a variant of the notion of T-constructibility developed earlier for complex-weighted counting constraint satisfaction problems.

Recommendations

• The approximability of constraint satisfaction problems
• scientific article; zbMATH DE number 1303558
• scientific article; zbMATH DE number 1559517
• Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights

Cited in

(9)

• Fixed-parameter Approximability of Boolean MinCSPs
• Boolean query optimization and the 0-1 hyperbolic sum problem
• Branch-and-bound solves random binary IPs in poly(n)-time
• Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems
• scientific article; zbMATH DE number 5999718 (Why is no real title available?)
• Improving Unsatisfiability-Based Algorithms for Boolean Optimization
• Mathematical Foundations of Computer Science 2004
• Randomized Post-optimization for t-Restrictions
• Principles and Practice of Constraint Programming – CP 2004

This page was built for publication: Optimization, randomized approximability, and Boolean constraint satisfaction problems

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