# A "cut" packing problem

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 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

The goal of $$\Pi$$ is to find a maximum cardinality subset $$H\subseteq D$$ such that for all $$1\le i, 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 or $$j' or $$i or $$i'. 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.

• 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? Jul 15, 2019 at 15:07