| dc.creator |
Aggarwal, Charu C. |
|
| dc.creator |
Kaplan, Haim |
|
| dc.creator |
Tarjan, Robert E., 1948- |
|
| dc.date |
2004-05-28T19:30:51Z |
|
| dc.date |
2004-05-28T19:30:51Z |
|
| dc.date |
1996-03 |
|
| dc.date.accessioned |
2013-10-09T02:38:41Z |
|
| dc.date.available |
2013-10-09T02:38:41Z |
|
| dc.date.issued |
2013-10-09 |
|
| dc.identifier |
http://hdl.handle.net/1721.1/5266 |
|
| dc.identifier.uri |
http://koha.mediu.edu.my:8181/xmlui/handle/1721 |
|
| dc.description |
We present a faster implementation of the polynomial time primal simplex algorithm due to Orlin [23]. His algorithm requires O(nm min{log(nC), m log n}) pivots and O(n2 m ??n{log nC, m log n}) time. The bottleneck operations in his algorithm are performing the relabeling operations on nodes, selecting entering arcs for pivots, and performing the pivots. We show how to speed up these operations so as to yield an algorithm whose running time is O(nm. log n) per scaling phase. We show how to extend the dynamic-tree data-structure in order to implement these algorithms. The extension may possibly have other applications as well. |
|
| dc.format |
974941 bytes |
|
| dc.format |
application/pdf |
|
| dc.language |
en_US |
|
| dc.publisher |
Massachusetts Institute of Technology, Operations Research Center |
|
| dc.relation |
Operations Research Center Working Paper;OR 315-96 |
|
| dc.subject |
Network Flows, Simplex algorithm, polynomial time, premultipliers. |
|
| dc.title |
A Faster Primal Network Simplex Algorithm |
|
| dc.type |
Working Paper |
|