|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Optimization, Randomized Approximability, and Boolean Constraint Satisfaction Problems | | Tomoyuki Yamakami
; | | Date: |
16 Sep 2011 | | 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. | | Source: | arXiv, 1109.3651 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER