5
$\begingroup$

Reference Request

I've found a natural greedy algorithm for the problem below. My question is: what is already known about fast algorithms for this problem (faster than general linear programming, especially greedy algorithms)? An ideal answer would include citations to relevant publications (articles or texts). Thanks.

Problem: Fractional Interval Covering

input: A positive integer $n$, and, for every pair of integers $(i, j)$ in $I=\{(i,j) : 1\le i \le j \le n\}$, a capacity $c_{ij} \in [0,1]$.

output: A minimum-size fractional interval covering $x$. That is, a solution to the following linear program:

$~~~~~$ minimize $\sum_{(i,j)\in I} x_{ij}$ subject to

$~~~~~$$\sum_{(i,j)\in I, t\in[i,j]} x_{ij} \ge 1$ for all $t\in\{1,2,\ldots,n\}$,

$~~~~~$and $x_{ij}\in [0, c_{ij}]$ for all $(i,j)\in I$.

Greedy algorithm. Briefly, the algorithm I've found starts with $x=\mathbf 0$, then repeatedly chooses some $t$ with unmet demand (subject to some restrictions on $t$), and increases $x_{ij}$ by some amount, for some $(i,j)\in I$ maximizing $j$ subject to $t\in [i,j]$ and $x_{ij} < c_{ij}$.

For the special case of $c_{ij}\in \{0,1\}$, giving a greedy algorithm for the problem is a common introductory algorithms exercise. It can be solved by choosing an interval containing 1 with latest end-time $j$, then recursing on $[j+1,n]$. The algorithm I have in mind is a generalization of this.

EDIT: To clarify, I am interested in algorithms that compute an exact optimum. The algorithm I have in mind is a greedy algorithm that can be implemented in linear time. The dual LP is

$~~~~$ maximize $\sum_{t=1}^n \alpha_t - \sum_{ij} c_{ij}\beta_{ij}$ subject to

$~~~~~\alpha_t, \beta_{ij} \ge 0~~~(t, i, j)$

$~~~~~\sum_{t\in[i,j]} \alpha_t \le 1 + \beta_{ij}~~~((i,j)\in I)$

It always has an optimal solution with each $\alpha_t\in\{0,1\}$ and integer $\beta_{ij}$. Thus, the dual problem is equivalent to the following:

input: As described above.

output: A subset $T\subseteq \{1,2,\ldots,n\}$ maximizing $|T|$ minus, for every integer interval $[i,j]\subseteq [1,n]$ such that $|[i,j]\cap T|$ is greater than 1, a penalty of $c_{ij}\times |[i,j]\cap T|$.

$\endgroup$
  • $\begingroup$ For the record, the following article is close (studies some similar problems), but I don't think any of them apply to this problem. Dorit S. Hochbaum and Asaf Levin. Optimizing over Consecutive 1's and Circular 1's Constraints. SIAM J. Optim., 17(2), 311–330. (20 pages) doi.org/10.1137/040603048 $\endgroup$ – Neal Young Aug 10 at 20:08
  • $\begingroup$ Are you looking for exact algorithms? $\endgroup$ – Chandra Chekuri Aug 11 at 1:13
  • $\begingroup$ I assume you are mainly interested in the setting with the size and value of the intervals being equal. If you are interested in the general case here are two refs that may be helpful. Arkin and Silverberg used a reduction to flow for the interval scheduling (which is a packing problem) which I think would generalize with lower-bounded flow for the covering problem you have. sciencedirect.com/science/article/pii/0166218X87900370. One can of course also solve the LP approximately using various techniques, especially via data structures for intervals. $\endgroup$ – Chandra Chekuri Aug 11 at 3:52
  • $\begingroup$ @ChandraChekuri: yes, exact algorithms. The intervals $[i,j]$ have all sizes (where size is $j-i+1$). Intervals have no associated values. The goal is to select a minimum (fractional) number of intervals to cover all the times. The algorithm I have in mind is å greedy algorithm that gives an exact solution, and can be implemented in linear time. Thanks for the reference, I will take a look. $\endgroup$ – Neal Young Aug 11 at 12:07
  • $\begingroup$ Consider the problem where we are given $n$ points on the real line with integer coverage requirements $d_1,d_2,\ldots,d_n$. We are given a collection of $m$ intervals $I_1,I_2, \ldots,I_m$ and want to pick fewest number to cover each point $i$ by $d_i$ intervals (here we are assuming intervals can only be taken once). A simple greedy algorithm is easily seen to work, generalizing the case of unit coverage requirements: This, via scaling, should generalize to fractional setting. Assume this is what you have in mind. Clearly relies on unweighted nature so perhaps less investigated. $\endgroup$ – Chandra Chekuri Aug 11 at 15:44

Your Answer

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

Browse other questions tagged or ask your own question.