Succinct approximate convex pareto curves

ABSTRACT

We study the succinct approximation of convex Pareto curves of multiobjective optimization problems. We propose the concept of ε-convex Pareto (ε-CP) set as the appropriate one for the convex setting, and observe that it can offer arbitrarily more compact representations than ε-Pareto sets in this context. We characterize when an ε-CP can be constructed in polynomial time in terms of an efficient routine Comb for optimizing (exactly or approximately) monotone linear combinations of the objectives. We investigate the problem of computing minimum size ε-convex Pareto sets, both for discrete (combinatorial) and continuous (convex) problems, and present general algorithms using a Comb routine. For bi-objective problems, we show that if we have an exact Comb optimization routine, then we can compute the minimum ε-CP for continuous problems (this applies for example to bi-objective Linear Programming and Markov Decision Processes), and factor 2 approximation to the minimum ε-CP for discrete problems (this applies for example to bi-objective versions of polynomial-time solvable combinatorial problems such as Shortest Paths, Spanning Tree, etc.). If we have an approximate Comb routine, then we can compute factor 3 and 6 approximations respectively to the minimum ε-CP for continuous and discrete bi-objective problems. We consider also the case of three and more objectives and present some upper and lower bounds.

REFERENCES

• 1: A. Aggarwal , H. Booth , J. O'Rourke , S. Suri, Finding minimal convex nested polygons, Information and Computation, v.83 n.1, p.98-110, Oct. 1989 [doi>10.1016/0890-5401(89)90049-7]
• 2: {BG} H. Brönnimann, M. T. Goodrich Almost Optimal Set Covers in Finite VC-Dimension. Discrete and Computational Geometry, 14(4): 463--479 (1995).
• 3: Patricia June Carstensen, The complexity of some problems in parametric linear and combinatorial programming, University of Michigan, Ann Arbor, MI, 1983
• 4: {Chan} R. Chandrasekaran. Minimal ratio spanning tree. Networks 7, pp. 335--342, 1977.
• 5: {CHSB} D. L. Craft, T. F. Halabi, H. A. Shih, T. R. Bortfeld. Approximating convex Pareto surfaces in multiobjective radiotherapy planning. Med. Phys., 33, pp. 3399--3407, 2006.
• 6: {Cli} J. Climacao, Ed. Multicriteria Analysis. Springer-Verlag, 1997.
• 7: Kenneth L. Clarkson, Algorithms for Polytope Covering and Approximation, Proceedings of the Third Workshop on Algorithms and Data Structures, p.246-252, August 11-13, 1993
• 8: {CMH} K. Chatterjee, R. Majumdar, T. A. Henzinger. Markov Decision Processes with Multiple Objectives. STACS, 325--336, 2006.
• 9: {DY} I. Diakonikolas, M. Yannakakis. Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems. In Proc. APPROX, 2007.
• 10: Matthias Ehrgott, Multicriteria Optimization, Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 11: {EG} M. Ehrgott, X. Gandibleux. An annotated bibliography of multiobjective combinatorial optimization problems. OR Spectrum 42, pp. 425--460, 2000.
• 12: {EKVY} K. Etessami, M. Kwiatkowska, M. Y. Vardi, and M. Yannakakis. Multi-Objective Model Checking of Markov Decision Processes. In Proc. TACAS, 2007.
• 13: {FGE} J. Figueira, S. Greco, M. Ehrgott, eds. Multiple Criteria Decision Analysis: State of the Art Surveys, Springer, 2005.
• 14: Daniel Mier Gusfield, Sensitivity analysis for combinatorial optimization, University of California, Berkeley, 1980
• 15: {Han} P. Hansen. Bicriterion Path Problems. Proc. 3rd Conf. Multiple Criteria Decision Making Theory and Application, pp. 109--127, Springer Verlag LNEMS 177, 1979.
• 16: Vladlen Koltun , Christos H. Papadimitriou, Approximately dominating representatives, Theoretical Computer Science, v.371 n.3, p.148-154, March, 2007 [doi>10.1016/j.tcs.2006.11.003]
• 17: {Meg1} N. Meggido. Combinatorial Optimization with Rational Objective Functions. Math of OR, pp. 414--424, 1979.
• 18: 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]
• 19: {Miet} K. M. Miettinen. Nonlinear Multiobjective Optimization, Kluwer, 1999.
• 20: Joseph S. B. Mitchell , Subhash Suri, Separation and approximation of polyhedral objects, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.296-306, September 1992, Orlando, Florida, United States
• 21: Jiří Matoušek , Raimund Seidel , E. Welzl, How to net a lot with little: small &egr;-nets for disks and halfspaces, Proceedings of the sixth annual symposium on Computational geometry, p.16-22, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98530]
• 22: C. H. Papadimitriou , M. Yannakakis, On the approximability of trade-offs and optimal access of Web sources, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.86, November 12-14, 2000
• 23: Christos H. Papadimitriou , Mihalis Yannakakis, Multiobjective query optimization, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.52-59, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375560]
• 24: G. Ruhe , Bernd Fruhwirth, &egr;-optimality for bicriteria programs and its application to minimum cost flows, Computing, v.44 n.1, p.21-34, March 1990 [doi>10.1007/BF02247962]
• 25: {Ru} G. Ruhe. Complexity results for multicriteria and parametric network flows using a pathological graph of Zadeh. Zeitschrift fur Operations Research, 32, pp. 9--27, 1988.
• 26: {RW} S. Ruzika, M. M. Wiecek. Approximation Methods in Multiobjective Programming (Survey paper). J. Opt. Th. and Appl., 126(3), pp. 473--501, 2005.
• 27: {VV} P. Van Mieghen, L. Vandenberghe. Trade-off Curves for QoS Routing. In Proc. INFOCOM, 2006.
• 28: Sergei Vassilvitskii , Mihalis Yannakakis, Efficiently computing succinct trade-off curves, Theoretical Computer Science, v.348 n.2, p.334-356, 8 December 2005 [doi>10.1016/j.tcs.2005.09.022]
• 29: A. Warburton, Approximation of Pareto optima in multiple-objective, shortest-path problems, Operations Research, v.35 n.1, p.70-79, Jan.-Feb. 1987 [doi>10.1287/opre.35.1.70]
• 30: {Ze} M. Zeleny. Linear Multiobjective Programming, Springer, 1974.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Approximation of surfaces and contours

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

General Terms:
Algorithms, Design, Theory