Setting Parameters by Example

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.

13 pages, 3 figures. To be presented at 40th IEEE Symp. Foundations of Computer Science (FOCS '99)

References in corpus (1)

• Faster Parametric Shortest Path and Minimum Balance Algorithms

Cited by in corpus (3)

• A Realistic Model under which the Genetic Code is Optimal
• Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Edge Crossings
• Optimal Moebius Transformations for Information Visualization and Meshing