2
$\begingroup$

I've given an optimization problem for which I want to show that it is solvable in polynomial time.

Now, I have two questions:

  1. Can this be done by formulating a mixed-integer linear program such that the coefficient matrix A has only values of -1, 0 or +1 and show that A is total unimodular? Because solving the relaxation of this problem with appropriate LP-techniques delivers an optimal solution in polynomial time.

  2. What alternatives do I have to show that an optimization problem is solvable in polynomial time? I'm searching for an elegant proof for writing down this result.

EDIT: I reformulated my questions and hope my request becomes clearer.

Improve this question
$\endgroup$
3
  • $\begingroup$ there are way too many ways to give a polynomial time algorithm for an optimization problem. voted to close at too broad $\endgroup$
    – Sasho Nikolov
    Commented Mar 6, 2014 at 15:32
  • 2
    $\begingroup$ 1. Yes. 2. Find a simpler, faster algorithm. $\endgroup$
    – Austin Buchanan
    Commented Mar 6, 2014 at 15:32
  • $\begingroup$ I'm also confused. You've solved your problem already, so Q1 is moot. And Q2 is very broad. There are many many ways to show that a problem can be solved in polynomial time. If you restrict yourself to problems formulated via ILPs, then this question has some answers you might find useful: cstheory.stackexchange.com/questions/4409/… $\endgroup$
    – Suresh Venkat
    Commented Mar 6, 2014 at 17:57

1 Answer 1

Reset to default
3
$\begingroup$

Regarding question 2, there are at least two other classes of matrices that give integral polehydra: the balanced and totally balanced matrices. When available, these properties are simpler to establish than total unimodularity.

I'm not sure about question 1: your first paragraph seems to contain the answer, but after closer inspection I realize that total unimodularity yields integral polyhedras for arbitrary budget vectors. As Linear Programming is not known to be strongly polynomial, I suspect that you won't get polynomial time with an arbitrary integral budget that is binary-encoded (but it works say for a 0,1-budget vector).

You can find some relevant lecture notes online; some textbooks might be useful too (such as "Combinatorial Optimization" or "Hypergraph Theory: An Introduction").

Improve this answer
$\endgroup$
4
  • $\begingroup$ linear programming is not strongly polynomial, but it does run in time polynomial in the bitlength of the input. also it is not clear to me what "budget" means $\endgroup$
    – Sasho Nikolov
    Commented Mar 6, 2014 at 15:27
  • $\begingroup$ My understanding was that "strongly polynomial" = polynomial in the bit complexity while "pseudo-polynomial" = polynomial in the magnitude. Also, I had the impression that it was an open question whether LP was strongly polynomial, but what does it mean exactly in that case? $\endgroup$
    – Super8
    Commented Mar 6, 2014 at 15:37
  • $\begingroup$ The problem in question can be solved in strongly polytime since it is a combinatorial linear program. $\endgroup$
    – Austin Buchanan
    Commented Mar 6, 2014 at 15:45
  • 1
    $\begingroup$ I meant that LP is not known to be solvable in strongly polynomial time, but it is solvable in polynomial time in the bit length of the input. Strongly polynomial time means that when the input is $N$ numbers, the algorithm performs polynomial in $N$ number of arithmetic operations on these numbers, irrespective of their magnitude. en.wikipedia.org/wiki/… $\endgroup$
    – Sasho Nikolov
    Commented Mar 6, 2014 at 16:03

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.