5
$\begingroup$

Given the following problem:

\begin{align} & z=\min \sum_{ij} x_{ij}\\ \text{s.t.} & \quad \sum_i d_{ij} x_{ij} \ge s_j, \quad \forall j \tag1 \\ & \quad \sum_j x_{ij} \le 1, \quad \forall i \tag2 \\ & \quad x_{ij} \in \left\{0, 1\right\}, \quad \forall i,j \tag3 \\ \end{align}

with known $d_{ij}, s_j$, is there an algorithm that solves it in polinomial time? If not, is there an approximate one?

$\endgroup$
  • $\begingroup$ It seems to me that it should be equivalent to a matching problem in bipartite graphs, where the problem is to minimize the number of edges with respect to the constraints. $\endgroup$ – Mostafa Jun 19 at 8:24
  • 1
    $\begingroup$ I first thought it might be a flow in a bipartite graph, but constraint (1) is the problem; either you take $d_{ij}$ entirely on arc $(i,j)$, or nothing, and you cannot control this in a flow $\endgroup$ – Marco Lübbecke Jun 19 at 9:12
  • $\begingroup$ I think this looks somewhat similar to an exact cover problem? $\endgroup$ – Luke599999 Jun 19 at 9:17
5
$\begingroup$

Let us get some additional insights by assuming $d_{ij} \in \{0,1\}$ and interpreting the data as a directed graph. For now we assume the number of $i$'s and $j$'s is the same, but I don't think it will be difficult to generalize that assumption. We say there is an arc from $i$ to $j$ iff $d_{ij} \neq 0$. Now for each vertex $j$ where $s_j \neq 0$, we have to select at least $\lceil s_j \rceil$ incoming arcs. Selecting an arcs that ends in $j$ can only help to cover the particular constraint of $j$, and thus if we ignore Constraints $(2)$, variables only occur in a single constraint and the optimal objective would be $\sum_{j} \lceil s_j \rceil $.

If we do consider Constraints $(2)$, we get the constraint that for every vertex at most one outgoing arc can be selected. This problem can be formulated as a min-cost flow with demands. Construct a flow graph with a source and a sink, and two intermediate layers with nodes for indices $i$ and $j$. From the source to each $i$, add an arc with capacity $1$ to impose Constraints $(2)$ and give them costs $1$ to represent the objective function. From each $i$ to $j$ add an arc with capacity $1$ and costs zero iff $d_{ij} = 1$. Finally, add arcs from $j$ to the sink with demand $s_j$ and costs zero. Computing a min-cost flow that adheres to the demands gives you an optimal solution in polynomial time for this special case.

As Luke599999 pointed out, for the general case you can easily reduce a subset sum problem to this problem, which makes it weakly NP-hard. In fact, you can even reduce from 3-Partition to prove it is strongly NP-hard. Take a 3-partition instance where $k$ partitions of size $B$ must be constructed and each number $n_i$ is between $\frac{B}{4}$ and $\frac{B}{2}$ and all numbers add up to $kB$. Define $k$ entries $s_j = B$ for each partition that must be constructed, and define $d_{ij} = n_i$ for each number $i$. Constraints $(2)$ enforces that every number will be used at most once, and Constraints $(1)$ enforce that each partition is at least $B$. Now the only feasible solution would correspond to a valid 3-partition.

In practice, it should not be too difficult to construct a useful lower bound for your problem. For each of the Constraints $(2)$, solve a subset sum problem using dynamic programming to determine the minimum number of arcs you must select to fulfill that constraint. This is a pseudo-polynomial algorithm which can be solved fast in practice if your numbers are small. If you sum this up over all these constraints you get a lower bound on the number of arcs that must be selected and thus of the objective value. Constraints $(2)$ gives you a simple upper bound: you can never select more arcs than the number of nodes.

As it is NP-hard to determine whether an instance is feasible, any approximation that guarantees to find a feasible solution is also NP-hard. The special case with $d_{ij} \in \{0,1\}$ is solvable in polynomial time. Perhaps other special cases can be solved in polynomial time, but it will require you to exploit additional structure of your input data.

| improve this answer | |
$\endgroup$
5
$\begingroup$

The problem is NP-hard because it can be used to solve the subset-sum problem:

Subset-sum: given a set of numbers $a_k\forall k\in K$ and a special number $b$ is there a subset of numbers $K' \subset K$ such that $\sum_ {k\in K'} a_k =b$

Reduction: let $j \in \{1,2\}$, and $s_1=b$ $d_{k,j} = a_k \forall k,j$ and $s_2=\sum_i a_i - b$

I don't know of any approximation algorithms.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.