Setting Parameters by Example

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.

Authors

• David Eppstein

Keywords

• Routing
• Path planning
• Network servers
• Multicast algorithms
• Software algorithms
• Application software
• Vehicles
• Resource management
• Roads
• Web pages
• Optimization Problem
• Optimal Parameters
• Shortest Path
• Board Games
• Spanning Tree
• Parametric Optimization Problem
• Linear Function
• Evaluation Of Function
• Combination Of Parameters
• Linear Programming
• Hyperplane
• Edge Weights
• Inverse Problem
• Linear Time
• Test Suite
• Binary Tree
• Single Path
• Graph Size
• Lowest Common Ancestor
• Shortest Path Problem
• N Log N
• Tree Edges
• Vertical Segments
• Bipartite Matching
• Incident Edges
• Vehicle Routing
• Polynomial Number
• Correct Solution