0
$\begingroup$

Input: A set $N = \{1, \dots, n\}$, subsets/consecutive pairs $S_1 = \{1,2\}, \dots, S_n = \{n,1\}$ with associated costs $c_1, \dots, c_n \in \mathbb{N} \cup \{0\}$, and a subset $B \subseteq N$.

Output: A collection $\mathcal{S} \subseteq \{ S_1, \dots, S_n \}$ that minimizes $\sum_{S_i \in \mathcal{S}} c_i$ and covers $B$, that is, $$ B \subseteq \bigcup_{S_i \in \mathcal{S}} S_i. $$

Questions: Is there an efficient alternative to solving this as an integer program? If so, is the problem much harder if $x$ covers more consecutive elements (like $x$, $x+1$, and $x+2$)?

I guess that this is related to the consecutive-ones property and total unimodularity, and the integer program is efficient. But I am still interesting in alternative algorithms.

$\endgroup$
  • $\begingroup$ Doesn't dynamic programming work in the binary case? $\endgroup$ – David Richerby Apr 18 '17 at 22:53
  • 1
    $\begingroup$ Hint: Suppose you somehow already know the cost of the optimal solution to the subproblem consisting of pairs $S_1, \dots, S_i$, and the cost of the optimal solution to the subproblem consisting of pairs $S_2, \dots, S_i$, for some $i < n-1$. Can you use these to quickly compute the costs of the optimal solutions to the two subproblems consisting of pairs $S_1, \dots, S_{i+1}$, and of pairs $S_2, \dots, S_{i+1}$? What small change is required for $i=n-1$? $\endgroup$ – j_random_hacker Apr 19 '17 at 0:53

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.