6
$\begingroup$

Consider the following integer linear program (where $A$ is an integer matrix, $b$ an integer vector, and $c$ a positive integer vector): $$ \text{minimize}~~~ c\cdot x \\ \text{subject to}~~~ A\cdot x \geq b, ~~~ x\geq 0, ~~~ x~\text{is an integer vector.} $$ Denote its optimal value by $OPT(A,b,c)$. Computing $OPT(A,b,c)$ is NP-hard in general. We are interested in computing an upper bound on $OPT(A,b,c)$, that is, a number $M = MAX(A,b,c)$ such that $OPT(A,b,c) \leq M$, and the size of $M$ (in bits) is polynomial in the size of $A,b,c$.

Is there an algorithm that, given $A,b,c$, computes such an upper bound $MAX(A,b,c)$ in time polynomial in the size of $A,b,c$?

$\endgroup$
13
  • $\begingroup$ I thought about it, but as far as I know, duality gives me a lower bound for my problem, not an upper bound. Maybe you have an idea how to get an upper bound for a minimization problem using duality? $\endgroup$ May 3, 2023 at 6:23
  • 1
    $\begingroup$ What would you want such M to be if the ILP is infeasible? $\endgroup$
    – JimN
    May 4, 2023 at 17:07
  • 2
    $\begingroup$ @SamuelBismuth, can't you consider the relaxation of the dual of your problem? Since the dual is a maximization problem (and the optimums coincide), when you relax the constraints you are going to find an upper bound on the optimum of the original minimization problem. $\endgroup$
    – Steven
    May 4, 2023 at 18:03
  • 1
    $\begingroup$ @Steven The maximum of the fractional dual problem (maximization) is equal to the minimum of the fractional primal problem (minimization), which is smaller than the minimum of the integral primal problem. Therefore, it is a lower bound and not an upper bound. $\endgroup$ May 12, 2023 at 8:53
  • 1
    $\begingroup$ @BernardoSubercaseaux yes, this special case could be interesting. $\endgroup$ Sep 28, 2023 at 10:13

1 Answer 1

0
$\begingroup$

While The bound given by @SilvioM in comments has polynomial size in A,b,c as requested, one cannot expect a polynomial time approximation for ILPs (see the second paragraph), and hence, probably also not an an upperbound polynomial in OPT. So this is probably as good as it gets.

The reason for this is that the well-known formulation of TSP as ILP is clearly a reduction from TSP to ILP. Since the general TSP does not admit a constant factor approximation, even when all weights are inegers (try to find a gap-reduction from Hamiltonian Cycle as a homework), and since this reduction clearly preserves approximation (since any feasible solution of one of them is a feasible solution of the other having the same target value), this excludes a constant factor approximation unless P=NP.

$\endgroup$
1
  • $\begingroup$ You mentioned a constant factor approximation, but the question is about a polynomial-size upper bound. $\endgroup$ Sep 1, 2023 at 1:20

Your Answer

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

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