Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Janka Chlebíková:

TR06-019 | 24th November 2005
Janka Chlebíková, Miroslav Chlebik

Hardness of asymptotic approximation for orthogonal rectangle packing and covering problems

Recently Bansal and Sviridenko (Proc. of the 15th SODA'04, 189-196)
proved that for
2-dimensional Orthogonal Rectangle
Bin Packing without rotations allowed there is no asymptotic PTAS, unless P=NP. We show that similar
approximation hardness results hold for several rectangle packing and covering problems even if rotations by ninety
more >>>

TR04-101 | 28th September 2004
Miroslav Chlebik, Janka Chlebíková

Crown reductions for the Minimum Weighted Vertex Cover problem

TR03-026 | 20th February 2003
Janka Chlebíková, Miroslav Chlebik

Inapproximability results for bounded variants of optimization problems

We study small degree graph problems such as Maximum Independent Set
and Minimum Node Cover and improve approximation lower bounds for
them and for a number of related problems, like Max-B-Set Packing,
Min-B-Set Cover, Max-Matching in B-uniform 2-regular hypergraphs.
For example, we prove NP-hardness factor of 95/94
more >>>

TR02-073 | 12th December 2002
Janka Chlebíková, Miroslav Chlebik

Approximation Hardness for Small Occurrence Instances of NP-Hard Problem

The paper contributes to the systematic study (started by Berman and
Karpinski) of explicit approximability lower bounds for small occurrence optimization
problems. We present parametrized reductions for some packing and
covering problems, including 3-Dimensional Matching, and prove the best
known inapproximability results even for highly restricted versions of ... more >>>

ISSN 1433-8092 | Imprint