Home > Search Results: Borgwardt, Steffen
Search:
Search Tips :: Advanced Search
Search collections:
Sort by: Display results: Output format:
National Repository of Grey Literature 1 records found  Search took 0.00 seconds. 
Experimental analysis of the simplex method for the multicommodity flow problem
 Kubek, Dávid ; Koutecký, Martin (advisor) ; Borgwardt, Steffen (referee)
This thesis investigates the multicommodity min-cost flow (MMCF) prob- lem. We aim to contribute to the search for a combinatorial algorithm for MMCF. The simplex method is employed to examine the vertices of the poly- hedron of feasible solutions using experimental analysis on a set of publicly available MMCF instances. To achieve this, we develop a solver capable of tracing solutions in each iteration of the algorithm in exact arithmetic, which was not available in existing solvers. Our investigation focuses on the frac- tionality of MMCF problems and the impact of different pivoting rules, par- ticularly whether the fractionality is exponential or polynomial with respect to increasing dimension. Our findings suggest that fractionality exhibits ex- ponential behavior.
Detailed record

Interested in being notified about new results for this query?
Subscribe to the RSS feed.
Digital Repository :: Search :: Submit :: Personalize :: Help
Powered by Invenio v1.1.2
Maintained by admin.invenio@techlib.cz
This site is also available in the following languages:
Česky  English