Consider the following problem $Q$: We are given an integer $n$, and $k$ intervals $[l_i,r_i]$ with $1\leq l_i\leq r_i\leq 2n$. We are also given $2n$ integers $d_1,…,d_{2n}\geq 0$. The task is to select a minimum number of intervals $[l_i,r_i]$ such that for every $i=1,…,2n$, at least $d_i$ intervals containing the integer $i$ are selected.

It is not hard to see that $Q$ can be solved in polynomial time (see below).

Now consider the following slightly modified problem $Q’$: The input of the problem is the same as before. However, the task now is to select a minimum number of intervals such that for every $i=1,…,n$, at least $d_{2i-1}$ intervals containing the integer $2i-1$ or at least $d_{2i}$ intervals containing the integer $2i$ are selected (with “or” we mean the usual logical or).

My question: Can $Q’$ be solved in polynomial time?

Here are two ways to solve $Q$ efficiently:

A simple greedy algorithm: Sweep through the intervals from left-to-right and select only as few intervals as are necessary to “satisfy” the numbers $d_i$. Whenever there is a choice between different intervals, choose the one(s) with maximal right endpoint.

An integer program: For each interval $[l_i,r_i]$ introduce a decision variable $x_i\in\{0,1\}$ with $x_i=1$ iff the interval is selected. The objective is to minimize $ x_1+…+x_k$, subject to the constraints $\sum_{j:i\in[l_j,r_j]} x_j\geq d_i$. The constraint matrix of this integer program has the consecutive ones property and therefore the linear programming relaxation of this program has an integer optimal solution.

Thanks for any hints, and also for references!


Every instance of Q can be transformed into an instance of the Multiple Set Cover Problem, where the locations are the intervals $[l_i,r_i]$, covering a consecutive sequence of demand points (=integers $d_i$).

| cite | improve this answer | |
  • 3
    $\begingroup$ Can you improve the answer adding the definition of Multiple Set Cover Problem (MSCP) and more details about the reduction ? In particular, an instance of MSCP (at least the "version" I know) is a bipartite graph $G = (V_1,V_2,E)$ and only $V_1$ is a union of disjoint sets; in which way the reduction maps the edges from $V_1$ to $V_2$? $\endgroup$ – Marzio De Biasi May 7 '14 at 9:51
  • $\begingroup$ I don't understand the point of this answer. Reducing the given problem to an NP-hard problem doesn't show the given problem is hard. (Nor does it show the given problem is in P, of course.) $\endgroup$ – Neal Young Apr 27 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.