Proof-techniques for the hardness of optimization problems (esp. Polynomial time)

Question

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

Now, I have two questions:

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

there are way too many ways to give a polynomial time algorithm for an optimization problem. voted to close at too broad — Sasho Nikolov, Mar 06 '14 at 15:32
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: http://cstheory.stackexchange.com/questions/4409/which-integer-linear-programs-are-easy/4410#4410 — Suresh Venkat, Mar 06 '14 at 17:57

score 3 · Answer 1 · answered Mar 06 '14 at 15:14

3

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").

answered Mar 06 '14 at 15:14

Super8

51
1

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 – Sasho Nikolov Mar 06 '14 at 15:27
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? – Super8 Mar 06 '14 at 15:37
The problem in question can be solved in strongly polytime since it is a combinatorial linear program. – Austin Buchanan Mar 06 '14 at 15:45
1

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. http://en.wikipedia.org/wiki/Time_complexity#Strongly_and_weakly_polynomial_time – Sasho Nikolov Mar 06 '14 at 16:03

Proof-techniques for the hardness of optimization problems (esp. Polynomial time)

1 Answers1