Minimax parametric optimization problems and multi-dimensional parametric searching

ABSTRACT

The parametric minimax problem, which finds the parameter value minimizing the weight of a solution of a combinatorial maximization problem, is a fundamental problem in sensitivity analysis. Moreover, several problems in computational geometry can be formulated as parametric minimax problems. The parametric search paradigm gives an efficient sequential algorithm for a convex parametric minimax problem with one parameter if the original non-parametric problem has an efficient parallel algorithm. We consider the parametric minimax problem with d parameters for a constant d, and solve it by using multidimensional version of the parametric search paradigm. As a new feature, we give a feasible region in the parameter space in which the parameter vector must be located.Typical results obtained as applications are: (1) Efficient solutions for some geometric problems, including theoretically efficient solutions for the minimum diameter bridging problem in d-dimensional space between convex polytopes. (2) Parametric polymatroid optimization, for example, O(n log n) time algorithm to compute the parameter vector minimizing k-largest linear parametric elements with d dimensions.

REFERENCES

• 1: Robert E. Bixby , William H. Cunningham, Matroid optimization and algorithms, Handbook of combinatorics (vol. 1), MIT Press, Cambridge, MA, 1996
• 2: Bernard Chazelle, Cutting hyperplanes for divide-and-conquer, Discrete & Computational Geometry, v.9 n.2, p.145-158, 1993 [doi>10.1007/BF02189314]
• 3: Otfried Chong, private communication.
• 4: Richard Cole, Slowing down sorting networks to obtain faster sorting algorithms, Journal of the ACM (JACM), v.34 n.1, p.200-208, Jan. 1987 [doi>10.1145/7531.7537]
• 5: E. Cohen , N. Megiddo, Strongly polynomial-time and NC algorithms for detecting cycles in dynamic graphs, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.523-534, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73057]
• 6: Martin Dyer , Nimrod Megiddo, Linear programming in low dimensions, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 7: David Eppstein, Geometric lower bounds for parametric matroid optimization, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.662-671, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225284]
• 8: B. G.artner, A subexponential algorithm for abstract optimization problems, Proc. 33rd IEEE Symposium on Foundations of Computer Science (1992) 464-472.
• 9: D. Gusfield, Sensitivity Analysis for Combinatorial Optimization, Memorandum No. UCB/ERL M80/22, U.C. Berkeley, 1980.
• 10: K. Imai , S. Sumino , H. Imai, Minimax geometric fitting of two corresponding sets of points, Proceedings of the fifth annual symposium on Computational geometry, p.206-275, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73863]
• 11: David R. Karger, Minimum cuts in near-linear time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.56-63, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237829]
• 12: Naoki Katoh , Hisao Tamaki , Takeshi Tokuyama, Parametric polymatroid optimization and its geometric applications, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.517-526, January 17-19, 1999, Baltimore, Maryland, United States
• 13: S. K. Kim and C. S. Shin, Computing the optimal bridge between two polygons, HKUST Research Report TCSC-99-14 (1999) to appear in IPL.
• 14: Jiří Matoušek, Efficient partition trees, Proceedings of the seventh annual symposium on Computational geometry, p.1-9, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109649]
• 15: Jiří Matoušek , Otfried Schwarzkopf, Linear optimization queries, Proceedings of the eighth annual symposium on Computational geometry, p.16-25, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142683]
• 16: Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
• 17: Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, Journal of the ACM (JACM), v.31 n.1, p.114-127, Jan. 1984 [doi>10.1145/2422.322418]
• 18: K. Mulmuley, Computational Geometry, an Introduction Through Randomized Algorithms, Princeton Hall, 1994.
• 19: Ketan Mulmuley, Is there an algebraic proof for P ≠ NC? (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.210-219, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258586]
• 20: Carolyn Habit Norton , Serge A. Plotkin , Éva Tardos, Using separation algorithms in fixed dimension, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.377-387, January 22-24, 1990, San Francisco, California, United States
• 21: Jeffrey S. Salowe, Parametric search, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 22: Micha Sharir , Emo Welzl, A Combinatorial Bound for Linear Programming and Related Problems, Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, p.569-579, February 13-15, 1992
• 23: Xuehou Tan, On optimal bridges between two convex regions, Information Processing Letters, v.76 n.4-6, p.163-168, Dec.31 2000 [doi>10.1016/S0020-0190(00)00143-5]
• 24: Takeshi Tokuyama, Efficient Algorithms for the Minimum Diameter Bridge Problem, Revised Papers from the Japanese Conference on Discrete and Computational Geometry, p.362-369, November 22-25, 2000

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations; Sorting and searching

General Terms:
Algorithms, Performance, Theory, Verification