Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > POLYNOMIAL REDUCTIONS:
Reports tagged with polynomial reductions:
TR96-062 | 3rd December 1996
Sanjeev Khanna, Madhu Sudan, David P. Williamson

#### A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction

In this paper we study the approximability of boolean constraint
satisfaction problems. A problem in this class consists of some
collection of constraints'' (i.e., functions
$f:\{0,1\}^k \rightarrow \{0,1\}$); an instance of a problem is a set
of constraints applied to specified subsets of $n$ boolean
variables. Schaefer earlier ... more >>>

TR96-064 | 11th December 1996
Sanjeev Khanna, Madhu Sudan, Luca Trevisan

#### Constraint satisfaction: The approximability of minimization problems.

This paper continues the work initiated by Creignou [Cre95] and
Khanna, Sudan and Williamson [KSW96] who classify maximization
problems derived from boolean constraint satisfaction. Here we
study the approximability of {\em minimization} problems derived
thence. A problem in this framework is characterized by a
collection F ... more >>>

ISSN 1433-8092 | Imprint