Geometric methods for non-geometric problems
Sparse dynamic programming.
D. Eppstein, Z. Galil, R. Giancarlo, and G.F. Italiano.
1st ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1990, pp. 513–522.
"Sparse dynamic programming I: linear cost functions", J. ACM 39: 519–545, 1992.
"Sparse dynamic programming II: convex and concave cost functions", J. ACM 39: 546–567, 1992.Considers sequence alignment and RNA structure problems in which the solution is constructed by piecing together some initial set of fragments (e.g. short sequences that match exactly). The method is to consider a planar point set formed by the fragment positions in the two input sequences, and use plane sweep to construct a cellular decomposition of the plane similar to the rectilinear Voronoi diagram.
Clustering for faster network simplex pivots.
D. Eppstein.
Tech. Rep. 93-19, ICS, UCI, 1993.
5th ACM-SIAM Symp. Discrete Algorithms, Arlington, 1994, pp. 160–166.
Networks 35 (3): 173–180, 2000.Speeds up the worst case time per pivot for various versions of the network simplex algorithm for minimum cost flow problems. Uses techniques from dynamic graph algorithms as well as some simple geometric data structures.
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.
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.
Internet packet filter management and rectangle geometry.
D. Eppstein and S. Muthukrishnan.
arXiv:cs.CG/0010018.
12th ACM-SIAM Symp. Discrete Algorithms, Washington, 2001, pp. 827–835.Rule sets for internet routers and firewalls can be represented as sets of prioritized rectangles; the rule to use for a packet is the maximum priority rectangle containing its (source,destination) address pair. We develop efficient data structures for performing these queries, and find an O(n3/2) time algorithm for testing whether a rule set contains any ambiguities.
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.