Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Wednesday, June 28, 2006, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Yoshio Okamoto (Toyohashi University of Technology)
Multi-criteria optimization essentially deals with enumeration (or listing) problems, but the field has not obtained much benefit from the recent advance in enumeration algorithmics. This work triggers the connection of multi-criteria optimization and enumeration algorithmics. As a thorough case study, we consider the multi-criteria minimum-cost spanning tree problem: Given a connected undirected graph and several edge-cost functions, we have to find all spanning trees which minimize some convex combinations of the cost functions. We compare two enumeration methods: The binary partition method and the reverse search method. We prove that a subproblem arising from a natural binary partition approach is NP-complete. This implies that an approach by the binary partition method seems difficult. On the other hand, we provide an efficient algorithm via the reverse search method. We generalize the method to the multi-criteria version of linear programming, and give the first polynomial-time-delay polynomial-space algorithm for the non-degenerated case of that problem.
Joint work with Takeaki Uno.
Automatic MiSe System Software Version 1.4803M | admin login