Parametric optimization
These papers concern problems in which some parameter or parameters is free, and one must explore the space of different solutions obtained for different values of these parameters. The k-set problem can be viewed in this framework as a form of parametric median-finding, in which the set of elements have values that are linear functions of a single time parameter; I have also looked at other similar parametric matroid problems as well as some parametric geometry problems.
- Visibility with a moving point of view.
M. Bern, D.P. Dobkin, D. Eppstein, and R. Grossman.
1st ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1990, pp. 107–118.
Algorithmica 11: 360–378, 1994.An investigation of 3d visibility problems in which the viewing position moves along a straight flight path, with various assumptions on the complexity of the viewed scene.
- On the number of minimal 1-Steiner trees.
B. Aronov, M. Bern, and D. Eppstein.
Disc. & Comp. Geom. 12: 29–34, 1994.Given a d-dimensional set of n points, the number of combinatorially different minimum spanning trees that can be formed by adding one more point is within a polylogarithmic factor of nd.
- Geometric lower bounds for parametric matroid optimization.
D. Eppstein.
Tech. Rep. 95-11, ICS, UCI, 1995.
27th ACM Symp. Theory of Computing, Las Vegas, 1995, pp. 662–671.
Disc. Comp. Geom. 20: 463–476, 1998.Considers graphs in which edge weights are linear functions of time. Shows nonlinear lower bounds on the number of different minimum spanning trees appearing over time by translation from geometric problem of lower envelopes of line segments. A matroid generalization has a better lower bound coming from many faces in line arrangements, and the uniform matroid problem is equivalent to the geometric k-set problem.
- The centroid of points with approximate weights.
M. Bern, D. Eppstein, L. J. Guibas, J. Hershberger, S. Suri, and J. Wolter.
3rd Eur. Symp. Algorithms, Corfu, 1995.
Springer, Lecture Notes in Comp. Sci. 979, 1995, pp. 460–472.Given a set of points with weights that are not known precisely, but are known to fall within some range, considers the possible weighted centroids arising from different choices of weights in each range. The combinatorics of this problem are closely connected with those of zonotopes.
- Choosing subsets with maximum weighted average.
D. Eppstein and D. S. Hirschberg.
Tech. Rep. 95-12, ICS, UCI, 1995.
5th MSI Worksh. on Computational Geometry, 1995, pp. 7–8.
J. Algorithms 24: 177–193, 1997.Uses geometric optimization techniques to find, among n weighted values, the k to drop so as to maximize the weighted average of the remaining values. The feasibility test for the corresponding decision problem involves k-sets in a dual line arrangement.
- Using sparsification for parametric minimum spanning tree problems.
D. Fernández-Baca, G. Slutzki, and D. Eppstein.
5th Scand. Worksh. Algorithm Theory, Reykjavik, 1996.
Springer, Lecture Notes in Comp. Sci. 1097, 1996, pp. 149–160.
Nordic J. Computing 3 (4): 352–366, 1996 (special issue for 5th SWAT).Given a graph with edge weights that are linear functions of a parameter, finds the sequence of minimum spanning trees produced as the parameter varies, in total time O(mn log n), by combining ideas from "Sparsification" and "Geometric lower bounds". Also solves various problems of optimizing the parameter value, including one closely related to that in "Choosing subsets with maximum weighted average".
- Computational geometry and parametric matroid optimization.
D. Eppstein.
Invited talk, 5th Int. Symp. Parametric Optimization, Chiba, Japan, 1997.This talk surveys some connections from computational geometry to parametric matroids: the results of my paper "Geometric lower bounds", new upper bounds from a paper by Tamal Dey, and a problem from constructive solid geometry with the potential to lead to stronger lower bounds.
- Parametric and kinetic minimum spanning trees.
P. K. Agarwal, D. Eppstein, L. J. Guibas, and M. R. Henzinger.
39th IEEE Symp. Foundations of Comp. Sci., 1998, pp. 596–605..We describe algorithms for maintaining the minimum spanning tree in a graph in which the edge weights are piecewise linear functions of time that may change unpredictably. We solve the problem in time O(n2/3 polylog n) per combinatorial change to the tree for general graphs, and in time O(n1/4 polylog n) per combinatorial change to the tree for planar graphs.
- Setting parameters by example.
D. Eppstein.
arXiv:cs.DS/9907001.
40th IEEE Symp. Foundations of Comp. Sci., 1999, pp. 309–318.
SIAM J. Computing 32 (3): 643–653, 2003.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 use low-dimensional linear programming and geometric sampling techniques to solve 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.
- The minimum expectation selection problem.
D. Eppstein and G. Lueker.
10th Int. Conf. Random Structures and Algorithms, Poznan, Poland, August 2001.
arXiv:cs.DS/0110011.
Random Structures and Algorithms 21: 278–292, 2002.We define the min-min expectation selection problem (resp. max-min expectation selection problem) to be that of selecting k out of n given discrete probability distributions, to minimize (resp. maximize) the expectation of the minimum value resulting when independent random variables are drawn from the selected distributions. Such problems can be viewed as a simple form of two-stage stochastic programming. We show that if d, the number of values in the support of the distributions, is a constant greater than 2, the min-min expectation problem is NP-complete but admits a fully polynomial time approximation scheme. For d an arbitrary integer, it is NP-hard to approximate the min-min expectation problem with any constant approximation factor. The max-min expectation problem is polynomially solvable for constant d; we leave open its complexity for variable d. We also show similar results for binary selection problems in which we must choose one distribution from each of n pairs of distributions.
- The weighted maximum-mean subtree and other bicriterion subtree problems.
J. Carlson and D. Eppstein.
arXiv:cs.CG/0503023.
Proc. 10th Scand. Worksh. Algorithm Theory (SWAT 2006).
Springer, Lecture Notes in Comp. Sci. 4059, 2006, pp. 397–408.We give a linear time algorithm for pruning a node-weighted tree to maximize the average node weight of the pruned subtree; this problem was previously studied under the less obvious name "The Fractional Prize-Collecting Steiner Tree Problem on Trees".
- Optimal embedding into star metrics.
D. Eppstein and K. Wortman.
arXiv:0905.0283.
Algorithms and Data Structures Symposium (WADS), Banff, Canada (best paper award).
Springer, Lecture Notes in Comp. Sci. 5664, 2009, pp. 290–301.We provide an O(n3 log2n) algorithm for finding a non-distance-decreasing mapping from a given metric into a star metric with as small a dilation as possible. The main idea is to reduce the problem to one of parametric shortest paths in an auxiliary graph. Specifically, we transform the problem into the parametric negative cycle detection problem: given a graph in which the edge weights are linear functions of a parameter λ, find the minimum value of λ for which the graph contains no negative cycles. We find a new strongly polynomial time algorithm for this problem, and use it to solve the star metric embedding problem.
(Slides)
- Optimal angular resolution for face-symmetric drawings.
D. Eppstein and K. Wortman.
arXiv:0907.5474.
J. Graph Algorithms and Applications 15 (4): 551–564, 2011.We consider drawings of planar partial cubes in which all interior faces are centrally symmetric convex polygons, as in my previous paper Algorithms for Drawing Media. Among all drawings of this type, we show how to find the one with optimal angular resolution. The solution involves a transformation from the problem into the parametric negative cycle detection problem: given a graph in which the edge weights are linear functions of a parameter λ, find the minimum value of λ for which the graph contains no negative cycles.
- The parametric closure problem.
D. Eppstein.
arXiv:1504.04073.
14th Algorithms and Data Structures Symp. (WADS 2015), Victoria, BC.
Springer, Lecture Notes in Comp. Sci. 9214 (2015), pp. 327–338.
ACM Trans. Algorithms 14 (1): Article 2, 2018.We consider the minimum weight closure problem for a partially ordered set whose elements have weights that vary linearly as a function of a parameter. For several important classes of partial orders the number of changes to the optimal solution as the parameter varies is near-linear, and the sequence of optimal solutions can be found in near-linear time.
(Slides)
- A stronger lower bound on parametric minimum spanning trees.
D. Eppstein.
arXiv:2105.05371.
17th Algorithms and Data Structures Symp. (WADS 2021).
Springer, Lecture Notes in Comp. Sci. 12808 (2021), pp. 343–356.
Algorithmica 85: 1738–1753, 2023 (special issue for WADS 2021).
There exist graphs with edges labeled by linear real functions, such that the number of different minimum spanning trees obtained for different choices of the function argument is \(\Omega(m\log n)\).
(Slides)