<p><strong>Reference Request</strong></p>
<p>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.</p>
<blockquote>
<p><strong>Problem: Fractional Interval Covering</strong></p>
<p><strong>input:</strong> <em>A positive integer <span class="math-container">$n$</span>, and, for every pair of integers <span class="math-container">$(i, j)$</span> in <span class="math-container">$I=\{(i,j) : 1\le i \le j \le n\}$</span>, a capacity <span class="math-container">$c_{ij} \in [0,1]$</span>.</em></p>
<p><strong>output:</strong> <em>A minimum-size fractional interval covering <span class="math-container">$x$</span>. That is, a solution to the following linear program:</em></p>
<p><span class="math-container">$~~~~~$</span> <em>minimize <span class="math-container">$\sum_{(i,j)\in I} x_{ij}$</span> subject to</em></p>
<p><em><span class="math-container">$~~~~~$$\sum_{(i,j)\in I, t\in[i,j]} x_{ij} \ge 1$</span> for all <span class="math-container">$t\in\{1,2,\ldots,n\}$</span>,</em></p>
<p><em><span class="math-container">$~~~~~$</span>and <span class="math-container">$x_{ij}\in [0, c_{ij}]$</span> for all <span class="math-container">$(i,j)\in I$</span></em>.</p>
</blockquote>
<p><strong>Greedy algorithm.</strong> Briefly, the algorithm I've found starts with <span class="math-container">$x=\mathbf 0$</span>, then repeatedly chooses some <span class="math-container">$t$</span> with unmet demand (subject to some restrictions on <span class="math-container">$t$</span>), and increases <span class="math-container">$x_{ij}$</span> by some amount, for some <span class="math-container">$(i,j)\in I$</span> maximizing <span class="math-container">$j$</span> subject to <span class="math-container">$t\in [i,j]$</span> and <span class="math-container">$x_{ij} &lt; c_{ij}$</span>.</p>
<p>For the special case of <span class="math-container">$c_{ij}\in \{0,1\}$</span>, 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 <span class="math-container">$j$</span>, then recursing on <span class="math-container">$[j+1,n]$</span>.  The algorithm I have in mind is a generalization of this.</p>
<p><strong>EDIT:</strong> 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</p>
<p><em><span class="math-container">$~~~~$</span> maximize  <span class="math-container">$\sum_{t=1}^n \alpha_t - \sum_{ij} c_{ij}\beta_{ij}$</span> subject to</em></p>
<p><span class="math-container">$~~~~~\alpha_t, \beta_{ij} \ge 0~~~(t, i, j)$</span></p>
<p><span class="math-container">$~~~~~\sum_{t\in[i,j]} \alpha_t \le 1 + \beta_{ij}~~~((i,j)\in I)$</span></p>
<p>It always has an optimal solution with each <span class="math-container">$\alpha_t\in\{0,1\}$</span> and integer <span class="math-container">$\beta_{ij}$</span>.  Thus, the dual problem is equivalent to the following:</p>
<blockquote>
<p><strong>input:</strong> <em>As described above.</em></p>
<p><strong>output:</strong> <em>A subset <span class="math-container">$T\subseteq \{1,2,\ldots,n\}$</span> maximizing <span class="math-container">$|T|$</span> minus, for every integer interval <span class="math-container">$[i,j]\subseteq [1,n]$</span> such that <span class="math-container">$|[i,j]\cap T|$</span> is greater than 1, a penalty of <span class="math-container">$c_{ij}\times |[i,j]\cap T|$</span>.</em></p>
</blockquote>

CC BY-SA 4.0
2020-08-10T20:08:40.800Z
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)  https://doi.org/10.1137/040603048*
Neal Young
CC BY-SA 4.0
2020-08-11T01:13:14.473Z
Are  you looking for exact algorithms?
Chandra Chekuri
CC BY-SA 4.0
2020-08-11T03:52:53.767Z
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. https://www.sciencedirect.com/science/article/pii/0166218X87900370. One can of course also solve the LP approximately using various techniques, especially via data structures for intervals.
Chandra Chekuri
CC BY-SA 4.0
2020-08-11T12:07:34.510Z
@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.
Neal Young
CC BY-SA 4.0
2020-08-11T15:44:35.337Z
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.
Chandra Chekuri
CC BY-SA 4.0
2020-08-11T17:18:57.760Z
@ChandraChekuri, yes, that (with the restriction $d_i=d_j$ for $i\ne j$) is essentially equivalent.  The algorithm can take any point $i$ with $d_i > \max_{j<i} d_j$, add a latest-ending interval containing point $i$, and recurse on the appropriate residual problem.  As you say it is not hard to prove correctness.. (I'm using this for something else, and looking for any citation to avoid reinventing the wheel.)  Thanks.
Neal Young
<reference-request><linear-programming><greedy-algorithms>
reference request: greedy algorithm for fractional interval covering
Neal Young
# reference request: greedy algorithm for fractional interval covering

(Asked by: username_0 on 2020-08-10)

**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|$.*

**Tags:** reference-request, linear-programming, greedy-algorithms

> **Comments:**
> **username_0**: 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)  https://doi.org/10.1137/040603048*  
> **username_1**: Are  you looking for exact algorithms?  
> **username_1**: 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. https://www.sciencedirect.com/science/article/pii/0166218X87900370. One can of course also solve the LP approximately using various techniques, especially via data structures for intervals.  
> **username_0**: @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.  
> **username_1**: 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.  
> **username_0**: @ChandraChekuri, yes, that (with the restriction $d_i=d_j$ for $i\ne j$) is essentially equivalent.  The algorithm can take any point $i$ with $d_i > \max_{j<i} d_j$, add a latest-ending interval containing point $i$, and recurse on the appropriate residual problem.  As you say it is not hard to prove correctness.. (I'm using this for something else, and looking for any citation to avoid reinventing the wheel.)  Thanks.  

---

## 0 answers

