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

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.

• 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 6 '14 at 15:32
• 1. Yes. 2. Find a simpler, faster algorithm. – Austin Buchanan Mar 6 '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: cstheory.stackexchange.com/questions/4409/… – Suresh Venkat Mar 6 '14 at 17:57

• 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/… – Sasho Nikolov Mar 6 '14 at 16:03