# Tagged Questions

The tag has no usage guidance.

38 views

### Reference request: Multi-hitting set problem

Suppose we are given a finite universe $U = \{e_1, e_2, ..., e_n\}$ of elements and a collection of sets $\mathbb{S} = \{S_1, S_2, ..., S_m\}$. The standard hitting set problem states asks for a ...
171 views

### Partial cover approximation

We have a set of elements $E=\{e_1, e_2, \ldots, e_m\}$, and $n$ subsets of $E$: $S_1, S_2, \ldots, S_n$ The union of those subsets is $E$, and each subset $S_i$ has a non-negative weight $w_i$. The ...
175 views

### What is the reverse of greedy algorithm for setcover?

A common approach to approximating SETCOVER is the greedy algorithm (Algorithm 2.2 Vazirani). This algorithm greedily picks the most cost-effective subset at each iteration, removes covered elements, ...
225 views

### Is there an approximation algorithm for MAX k DOUBLE SET COVER?

Given a set system $(X,\mathcal S)$, let us say that a subset $\mathcal C\subseteq \mathcal S$ doubly covers a vertex $x$ in $X$ if $x$ is contained in at least two sets of $\mathcal C$. Let us define ...
147 views

### Counting distinct set covers

I'm given a universal set $N = \{1, 2, \dots, n\}$, a family of sets $\mathcal{F} = \{ S_1, S_2, \dots, S_m \}$, $S_i \subseteq N$, and I need to count the number of distinct ways to cover the ...
148 views

### Bipartite Graphs - Maximum subset of one partition with at most n neighbours - NP-hard?

Given: A bipartite graph G=(U,V,E) Integers n and k. Decision Problem: Is there a subset of U of size k that has at most n neighbours? I am trying to figure out whether this problem is NP-...
22 views

I want to run $k$ programs distributed on $N$ machines. Because of resource constraints, a machine can have at most $p$ of the $k$ programs installed. To have a balanced system, I can install each of ...
74 views

237 views

67 views

### Combinatorial algorithm for load balancing

I have a problem that can be solved with linear programming, but I'm hoping there's a combinatorial algorithm for this (even approximation is fine). This is basically a load balancing problem using ...
264 views

### Set Cover with bounded intersection size

So, the set cover problem is trivial if none of the candidate sets intersect eachother. However, what if the size of the intersection for any pair of candidate sets was at most 1? Is this problem NP-...
151 views

976 views

### Is the following problem NP hard?

Consider a collection of sets $F=\{F_1,F_2,\dotsc,F_n\}$ over a base set $U=\{e_1,e_2,\dotsc,e_n\}$ where $|F_i|$ $\ll$ $n$ and $e_i \in F_i$, and let $k$ be a positive integer. The goal is to find ...
295 views

### Facility location problem with a cost function

I'm struggling with a facility location problem. In its original form the problem is quite straightforward: Given a matrix of distances between cities, I have to pick a minimal number of centers from ...
562 views

### Why the reduction from MINIMUM SET COVER to MINIMUM DOMINATING SET means $c \log n$-inapproximability for MINIMUM DOMINATING SET

There is a well-known reduction from MINIMUM SET COVER to MINIMUM DOMINATING SET provided at http://en.wikipedia.org/wiki/Dominating_set#L-reductions (attributed there to Kann 1992, but seen, for ...
860 views

### Worst-case asymptotic-complexity of the Set-cover problem?

What's the worst-case asymptotic-complexity of the Set-cover problem in Big O notation? I've been developing some novel techniques to try and solve this problem but am having trouble finding the ...
158 views

### Can we achieve a better kernel for the Vertex Cover problem on planar graphs?

We have known how to get a $2k$ kernel for the Vertex Cover problem for thirty years, and it is not expected to be improved assuming UGC. My question is, can we do better for planar graphs? It is ...
543 views

### Hardness of Approximation results for Special Set Packing Problem Wanted

Is there any inapproximability result for the following NP-hard problem, which is a special case of the weighted Set Packing Problem? The general Set Packing Problem would be: Given A Collection of ...