Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SET COVER:
Reports tagged with set cover:
TR97-003 | 29th January 1997

#### Improved low-degree testing and its applications

NP = PCP(log n, 1) and related results crucially depend upon
the close connection between the probability with which a
function passes a low degree test'' and the distance of
this function to the nearest degree d polynomial. In this
paper we study a test ... more >>>

TR97-004 | 19th February 1997
Marek Karpinski, Alexander Zelikovsky

#### Approximating Dense Cases of Covering Problems

We study dense instances of several covering problems. An instance of
the set cover problem with $m$ sets is dense if there is $\epsilon>0$
such that any element belongs to at least $\epsilon m$ sets. We show
that the dense set cover problem can be approximated with ... more >>>

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

TR07-105 | 21st September 2007
Jelani Nelson

#### A Note on Set Cover Inapproximability Independent of Universe Size

Revisions: 1

In the set cover problem we are given a collection of $m$ sets whose union covers $[n] = \{1,\ldots,n\}$ and must find a minimum-sized subcollection whose union still covers $[n]$. We investigate the approximability of set cover by an approximation ratio that depends only on $m$ and observe that, for ... more >>>

TR11-019 | 5th February 2011
Valentin Brimkov, Andrew Leach, Jimmy Wu, Michael Mastroianni

#### On the Approximability of a Geometric Set Cover Problem

Given a finite set of straight line segments $S$ in $R^{2}$ and some $k\in N$, is there a subset $V$ of points on segments in $S$ with $\vert V \vert \leq k$ such that each segment of $S$ contains at least one point in $V$? This is a special case ... more >>>

TR11-112 | 10th August 2011
Dana Moshkovitz

#### The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover

In this paper we put forward a conjecture: an instantiation of the Sliding Scale Conjecture of Bellare, Goldwasser, Lund and Russell to projection games. We refer to this conjecture as the Projection Games Conjecture.

We further suggest the research agenda of establishing new hardness of approximation results based on the ... more >>>

TR15-113 | 9th July 2015
Amit Chakrabarti, Tony Wirth

#### Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover

Set cover, over a universe of size $n$, may be modelled as a
data-streaming problem, where the $m$ sets that comprise the instance
are to be read one by one. A semi-streaming algorithm is allowed only
$O(n \text{ poly}\{\log n, \log m\})$ space to process this ... more >>>

TR20-167 | 9th November 2020
Venkatesan Guruswami, Sai Sandeep

#### Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture

A famous conjecture of Tuza states that the minimum number of edges needed to cover all the triangles in a graph is at most twice the maximum number of edge-disjoint triangles. This conjecture was couched in a broader setting by Aharoni and Zerbib who proposed a hypergraph version of this ... more >>>

TR21-177 | 22nd November 2021
#### Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in $\ell_p$-metrics
k-median and k-means are the two most popular objectives for clustering algorithms. Despite intensive effort, a good understanding of the approximability of these objectives, particularly in $\ell_p$-metrics, remains a major open problem. In this paper, we significantly improve upon the hardness of approximation factors known in literature for these objectives ... more >>>