What is the fastest polynomial time algorithm known for solving a totally unimodular integer LP?

 1 What is the fastest known algorithm which solves an integer linear program with a totally unimodular coeffient matrix? Could you point me to some references? I tried googling, but failed at finding a good answer and reference for this. asked 21 Jan '11, 09:32 gphilip 13●3 accept rate: 0%

 2 The problem specified over at Theoretical Computer Science can be formulated as a transportation problem. If we ignore the second (greater than) constraint, it is clearly a transportation (Hitchcock) problem, where source i has supply n_i, sink j has some arbitrarily large demand (the sum of the n_i being an obvious candidate), and we use an extra dummy source node whose supply balances total supply with total demand and which has a zero-cost arc to every sink. To accommodate the second constraint (minimum flow of w into every sink), split each sink node into two nodes. The first one (I'll call it the original) has demand w and the second one (which I'll call the clone) has the original demand less w. Clone the arcs as well, but remove the arc from the dummy source to the original node (leave the arc from the dummy source to the clone). Although this jacks up the size of the network, my guess is that a special-purpose algorithm for the transportation problem will be fastest. answered 22 Jan '11, 19:32 Paul Rubin ♦♦ 14.6k●4●12 accept rate: 19% @Paul : Thank you, let me check this out. (23 Jan '11, 02:32) gphilip
 3 Many specialized problems that can be formulated as LPs with TU matrices have specialized algorithms that are more efficient than algorithms for general problems. Min-cost network flow problems and special cases such as max flow, circulation, shortest path all fall in this class. For general TU problems, I don't know of anything faster than algorithms for general LPs, though. Anyone else know better? For network flow problems, start with Ahuja, Magnanti, and Orlin's Network Flows book. Advances have almost surely been made since then, but that will give you an entry. answered 21 Jan '11, 14:33 Matthew Salt... ♦ 4.7k●3●10 accept rate: 17% I believe you are right, I am no expert in complexity for general TU either, but I am reasonable sure you end up in same result as standard LP. Special cases of TU is of course a different result. (21 Jan '11, 21:32) Bo Jensen ♦ @Matthew : Thank you. I asked the same question over at the Theoretical CS place [1], and got a couple of answers that give more information. [1] http://cstheory.stackexchange.com/q/4454/148 (22 Jan '11, 15:53) gphilip
 2 All problems with TU constraint matrix can, in principle, be reduced to network problems (i.e. linear programs where the constraint matrix is the incidence matrix of a diagraph or its transpose). This is done via Seymour's decomposition theorem for TU matrices (i.e. all TU matrices can be constructed from network matrices using 1-sums,2-sums, and 3-sums). It is known that using this decomposition approach yields polytime algorithms (with network algorithms as subroutine), but I am not sure if the running time is better than just solving the problem with standard LP mehods. Schrijver's blue book has more on this. answered 28 Jan '11, 17:31 Anonymous 21●1 accept rate: 0%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: