A Faster Primal Network Simplex Algorithm

Please use this identifier to cite or link to this item: http://dspace.mediu.edu.my:8181/xmlui/handle/1721.1/5266

Full metadata record

DC Field	Value	Language
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	-
Appears in Collections:	MIT Items

Files in This Item:

There are no files associated with this item.

DSpace JSPUI