Consider the following maximisation problem.

Given a path $P=\{1,2,\dots,n\}$ over $n$ vertices, a set $D\subseteq P\times P$ of "edges" and a set of positive integers capacities $\mathcal{C}=\{c_{i,j} \mid 1\le i<j \le n\}$ for each subpath, we define the cut of the subpath $\{i,\dots,j\}$ by $H\subseteq D$, written $d_{i,j}(H)$ as the number of edges in $H$ with exactly one endpoint between $i$ and $j$: $$ d_{i,j}(H):=\vert\{(x,y)\in H \mid x<i\le y \le j \text{ or } i\le x \le j < y\}\vert $$

The goal of $\Pi$ is to find a maximum cardinality subset $H\subseteq D$ such that for all $1\le i<j\le n: d_{i,j}(H)\le c_{i,j}$, which means that any cut must not exceed the given capacity.

This problem is a special case of Set-packing by considering $D$ as the ground set and subpaths as sets. I would be interested in any thought that could suggest that this problem admit a strictly better approximation that classic Set-packing.

Further, another version that is of interest is the one where the additional "non-crossing" property is requiered: a solution $H\subseteq D$ is feasible if the capacities are respected and for any two edges $(i,j)$ and $(i',j')$ in $H$, either $j<i'$ or $j'<i$ or $i<i'<j'<j$ or $i'<i<j<j'$. Can this additional constraint allows us to find a constant approximation ? For this particular case, one can find a $O(\log n)$-approximation with dynamic programming.

  • 2
    $\begingroup$ Is it the case that the special case with all $c_{i,i} = 1$ and $c_{i,j} =\infty$ for $i\ne j$ is equivalent to maximum matching, while the special case with all $c_{ij} = 2$ is activity selection? $\endgroup$
    – Neal Young
    Jul 15, 2019 at 15:07


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.