Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ABSOLUTE APPROXIMATION:
Reports tagged with Absolute Approximation:
TR05-080 | 21st July 2005
Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider

#### Proving NP-hardness for clique-width I: non-approximability of sequential clique-width

Revisions: 1

Clique-width is a graph parameter, defined by a composition mechanism
for vertex-labeled graphs, which measures in a certain sense the
complexity of a graph. Hard graph problems (e.g., problems
expressible in Monadic Second Order Logic, that includes NP-hard
problems) can be solved efficiently for graphs of certified small
clique-width. It ... more >>>

TR05-081 | 21st July 2005
Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider

#### Proving NP-hardness for clique-width II: non-approximability of clique-width

Revisions: 1

Clique-width is a graph parameter that measures in a certain sense the
complexity of a graph. Hard graph problems (e.g., problems
expressible in Monadic Second Order Logic with second-order
quantification on vertex sets, that includes NP-hard problems) can be
solved efficiently for graphs of certified small clique-width. It is
widely ... more >>>

TR06-104 | 25th August 2006
Wenceslas Fernandez de la Vega, Marek Karpinski

#### On the Sample Complexity of MAX-CUT

We give a simple proof for the sample complexity bound $O~(1/\epsilon^4)$ of absolute approximation of MAX-CUT. The proof depends on a new analysis method for linear programs (LPs) underlying MAX-CUT which could be also of independent interest.

more >>>

ISSN 1433-8092 | Imprint