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 '19 at 15:07

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.