ICS 269, Fall 1999: Theory Seminar
15 October 1999:
"Setting Parameters by Example"
Speaker: David
Eppstein, ICS, UC Irvine
Abstract: We introduce a class of "inverse parametric optimization"
problems, in which one is given both a parametric optimization
problem and a desired optimal solution; the task is to determine
parameter values that lead to the given solution. We describe
algorithms for solving such problems for minimum spanning trees,
shortest paths, and other "optimal subgraph" problems, and discuss
applications in multicast routing, vehicle path planning, resource
allocation, and board game programming.