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 algorithmapproximation-preserving reducibilityAPXconstraint satisfaction problemoptimization problemPO

Mathematics Subject Classification ID

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

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

(10)

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

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)