Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Approximation Ratios:
TR97-024 | 9th June 1997
Marek Karpinski

Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems

We survey recent results on the existence of polynomial time
approximation schemes for some dense instances of NP-hard
optimization problems. We indicate further some inherent limits
for existence of such schemes for some other dense instances of
the optimization problems.

more >>>

TR00-021 | 19th April 2000
Uriel Feige, Marek Karpinski, Michael Langberg

Improved Approximation of MAX-CUT on Graphs of Bounded Degree

We analyze the addition of a simple local improvement step to various known
randomized approximation algorithms.
Let $\alpha \simeq 0.87856$ denote the best approximation ratio currently
known for the Max Cut problem on general graphs~\cite{GW95}.
We consider a semidefinite relaxation of the Max Cut problem,
round it using the ... more >>>

TR00-043 | 21st June 2000
Uriel Feige, Marek Karpinski, Michael Langberg

A Note on Approximating MAX-BISECTION on Regular Graphs

We design a $0.795$ approximation algorithm for the Max-Bisection problem
restricted to regular graphs. In the case of three regular graphs our
results imply an approximation ratio of $0.834$.

more >>>

TR00-051 | 14th July 2000
Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas

Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs and Planar Graphs

The max-bisection problem is to find a partition of the vertices of a
graph into two equal size subsets that maximizes the number of edges with
endpoints in both subsets.
We obtain new improved approximation ratios for the max-bisection problem on
the low degree $k$-regular graphs for ... more >>>

TR00-064 | 29th August 2000
Klaus Jansen, Marek Karpinski, Andrzej Lingas

A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs

The Max-Bisection and Min-Bisection are the problems of finding
partitions of the vertices of a given graph into two equal size subsets so as
to maximize or minimize, respectively, the number of edges with exactly one
endpoint in each subset.
In this paper we design the first ... more >>>

TR00-089 | 1st December 2000
Lars Engebretsen, Marek Karpinski

Approximation Hardness of TSP with Bounded Metrics

Revisions: 1

The general asymmetric (and metric) TSP is known to be approximable
only to within an O(log n) factor, and is also known to be
approximable within a constant factor as soon as the metric is
bounded. In this paper we study the asymmetric and symmetric TSP
problems with bounded metrics ... more >>>

TR01-026 | 3rd April 2001
Piotr Berman, Marek Karpinski

Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION

We consider bounded occurrence (degree) instances of a minimum
constraint satisfaction problem MIN-LIN2 and a MIN-BISECTION problem for
graphs. MIN-LIN2 is an optimization problem for a given system of linear
equations mod 2 to construct a solution that satisfies the minimum number
of them. E3-OCC-MIN-E3-LIN2 ... more >>>

TR01-034 | 30th April 2001
Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski

Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction

It is known that large fragments of the class of dense
Minimum Constraint Satisfaction (MIN-CSP) problems do not have
polynomial time approximation schemes (PTASs) contrary to their
Maximum Constraint Satisfaction analogs. In this paper we prove,
somewhat surprisingly, that the minimum satisfaction of dense
instances of kSAT-formulas, ... more >>>

TR01-042 | 31st May 2001
Marek Karpinski

Approximating Bounded Degree Instances of NP-Hard Problems

We present some of the recent results on computational complexity
of approximating bounded degree combinatorial optimization problems. In
particular, we present the best up to now known explicit nonapproximability
bounds on the very small degree optimization problems which are of
particular importance on the intermediate stages ... more >>>

TR01-047 | 3rd July 2001
Piotr Berman, Sridhar Hannenhalli, Marek Karpinski

1.375-Approximation Algorithm for Sorting by Reversals

Analysis of genomes evolving by inversions leads to a general
combinatorial problem of {\em Sorting by Reversals}, MIN-SBR, the problem of
sorting a permutation by a minimum number of reversals.
This combinatorial problem has a long history, and a number of other
motivations. It was studied in a great ... more >>>

TR02-041 | 2nd July 2002
Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon

A Polynomial Time Approximation Scheme for Metric MIN-BISECTION

We design a polynomial time approximation scheme (PTAS) for
the problem of Metric MIN-BISECTION of dividing a given finite metric
space into two halves so as to minimize the sum of distances across
that partition. The method of solution depends on a new metric placement
partitioning ... more >>>

TR03-056 | 29th July 2003
Piotr Berman, Marek Karpinski

Approximability of Hypergraph Minimum Bisection

We prove that the problems of minimum bisection on k-uniform
hypergraphs are almost exactly as hard to approximate,
up to the factor k/3, as the problem of minimum bisection
on graphs. On a positive side, our argument gives also the
first approximation ... more >>>

ISSN 1433-8092 | Imprint