Paper Info
Title
A Polynomial-Time-Delay and Polynomial-Space Algorithm for Enumeration Problems in Multi-criteria Optimization
Abstract
We propose a polynomial-time-delay polynomial-space al- gorithm to enumerate all e-cient extreme solutions of a multi-criteria minimum-cost spanning tree problem, while only the bi-criteria case was studied in the literature. The algorithm is based on the reverse search framework due to Avis & Fukuda. We also show that the same technique can be applied to the multi-criteria version of the minimum-cost basis problem in a (possibly degenerated) submodular system. As an ultimate generalization, we propose an algorithm to enumerate all e-cient ex- treme solutions of a multi-criteria linear program. When the given linear program has no degeneracy, the algorithm runs in polynomial-time de- lay and polynomial space. To best of our knowledge, they are the flrst polynomial-time delay and polynomial-space algorithms for the prob- lems.
Year
DOI
Venue
2011
10.1007/978-3-540-77120-3_53
European Journal of Operational Research
Keywords
Field
DocType
linear programming,polynomial time,spanning tree,linear program,combinatorial optimization
Computer science,PSPACE,Linear programming,Spanning tree,Time complexity,Criss-cross algorithm,Discrete mathematics,Combinatorics,Mathematical optimization,Enumeration,Algorithm,Submodular set function,Degeneracy (mathematics)
Journal
Volume
Issue
ISSN
210
1
0302-9743
ISBN
Citations 
PageRank 
3-540-77118-2
1
0.37
References 
Authors
5
2
Name
Order
Citations
PageRank
Yoshio Okamoto117028.50
Takeaki Uno21319107.99