An \(O(n^ 2)\) simplex algorithm for a class of linear programs with tree structure (Q1073717)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: An \(O(n^ 2)\) simplex algorithm for a class of linear programs with tree structure |
scientific article; zbMATH DE number 3945869
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An \(O(n^ 2)\) simplex algorithm for a class of linear programs with tree structure |
scientific article; zbMATH DE number 3945869 |
Statements
An \(O(n^ 2)\) simplex algorithm for a class of linear programs with tree structure (English)
0 references
1985
0 references
The authors consider a special linear programming problem. Constraints of the problem are in natural correspondence with paths from the root to leaves in a tree. For solving the problem they propose an algorithm with runs in time \(O(n^ 2)\), where n is the number of leaves in the tree. The algorithm has run time O(n log n) for balanced trees.
0 references
simplex algorithm
0 references
tree structure
0 references
0.8233740925788879
0 references
0.8053209185600281
0 references
0.7829599380493164
0 references
