Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > COMBINATORIAL OPTIMIZATION:
Reports tagged with Combinatorial Optimization:
TR95-053 | 15th October 1995
Petr Slavik

Improved Performance of the Greedy Algorithm for the Minimum Set Cover and Minimum Partial Cover Problems

We establish significantly improved bounds on the performance of the greedy
algorithm for approximating MINIMUM SET COVER and MINIMUM PARTIAL COVER. Our
improvements result from a new approach to both problems. In particular,
(a) we improve the known bound on the performance ratio of the greedy ... more >>>


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 >>>


TR00-054 | 5th May 2000
Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri

On the power assignment problem in radio networks

Given a finite set $S$ of points (i.e. the stations of a radio
network) on a $d$-dimensional Euclidean space and a positive integer
$1\le h \le |S|-1$, the \minrangeh{d} problem
consists of assigning transmission ranges to the stations so as
to minimize the total power consumption, provided ... more >>>


TR07-011 | 19th December 2006
Bodo Manthey

On Approximating Restricted Cycle Covers

A cycle cover of a graph is a set of cycles such that every vertex is
part of exactly one cycle. An L-cycle cover is a cycle cover in which
the length of every cycle is in the set L. The weight of a cycle cover
of an edge-weighted graph ... more >>>


TR07-027 | 2nd February 2007
Tobias Friedrich, Jun He, Nils Hebbinghaus, Frank Neumann, Carsten Witt

Approximating Covering Problems by Randomized Search Heuristics Using Multi-Objective Models

The main aim of randomized search heuristics is to produce good approximations of optimal solutions within a small amount of time. In contrast to numerous experimental results, there are only a few theoretical results on this subject.
We consider the approximation ability of randomized search for the class of ... more >>>


TR23-063 | 2nd May 2023
Jacobo Toran, Florian Wörz

Cutting Planes Width and the Complexity of Graph Isomorphism Refutations

The width complexity measure plays a central role in Resolution and other propositional proof systems like Polynomial Calculus (under the name of degree). The study of width lower bounds is the most extended method for proving size lower bounds, and it is known that for these systems, proofs with small ... more >>>




ISSN 1433-8092 | Imprint