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

<p>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 <em>arbitrary</em> 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).</p>

<p>You can find some relevant <a href="http://www.mpi-inf.mpg.de/departments/d1/teaching/ws09_10/Opt2/handouts/lecture9.pdf" rel="nofollow">lecture notes</a> online; some textbooks might be useful too (such as "Combinatorial Optimization" or "Hypergraph Theory: An Introduction"). </p>

CC BY-SA 3.0
2014-03-06T15:27:36.183Z
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
CC BY-SA 3.0
2014-03-06T15:37:33.460Z
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
CC BY-SA 3.0
2014-03-06T15:45:37.630Z
The problem in question can be solved in strongly polytime since it is a [combinatorial linear program](http://pubsonline.informs.org/doi/abs/10.1287/opre.34.2.250).
Austin Buchanan
CC BY-SA 3.0
2014-03-06T16:03:29.770Z
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
CC BY-SA 3.0
2014-03-06T15:14:44.497Z
2014-03-06T15:14:44.497Z
Super8
<p>I've given an optimization problem for which I want to show that it is solvable in polynomial time.</p>

<p>Now, I have two questions:</p>

<ol>
<li><p>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.</p></li>
<li><p>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.</p></li>
</ol>

<p>EDIT: I reformulated my questions and hope my request becomes clearer.</p>

CC BY-SA 3.0
2014-03-06T15:32:13.937Z
there are way too many ways to give a polynomial time algorithm for an optimization problem. voted to close at too broad
Sasho Nikolov
CC BY-SA 3.0
2014-03-06T15:32:22.550Z
1. Yes. 2. Find a simpler, faster algorithm.
Austin Buchanan
CC BY-SA 3.0
2014-03-06T17:57:48.800Z
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
<cc.complexity-theory><optimization><linear-programming><proofs><polynomial-time>
Proof-techniques for the hardness of optimization problems (esp. Polynomial time)
Benjamin
# Proof-techniques for the hardness of optimization problems (esp. Polynomial time)

(Asked by: username_0 on 2014-03-06)

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.

**Tags:** cc.complexity-theory, optimization, linear-programming, proofs, polynomial-time
> **Comments:**
> **username_1**: there are way too many ways to give a polynomial time algorithm for an optimization problem. voted to close at too broad  
> **username_2**: 1. Yes. 2. Find a simpler, faster algorithm.  
> **username_3**: 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  

---

## 1 answers

### Answer by username_4 on 2014-03-06. Score: 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](http://www.mpi-inf.mpg.de/departments/d1/teaching/ws09_10/Opt2/handouts/lecture9.pdf) online; some textbooks might be useful too (such as "Combinatorial Optimization" or "Hypergraph Theory: An Introduction").

> **Comments:**
> **username_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  
> **username_4**: 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?  
> **username_2**: The problem in question can be solved in strongly polytime since it is a [combinatorial linear program](http://pubsonline.informs.org/doi/abs/10.1287/opre.34.2.250).  
> **username_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  

---

