Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

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)

Enumeration Algorithmics for Multi-Criteria Optimization

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login