A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One

References

• Ackermann H, Newman A, Röglin H, Vöcking B. Decision-making based on approximate and smoothed Pareto curves. Theoret. Comput. Sci. (2007) 378(3):253–270Crossref, Google Scholar
• Aissi H, Bazgan C, Vanderpooten D. Approximation of min-max and min-max regret versions of some combinatorial optimization problems. Eur. J. Oper. Res. (2007) 179(2):281–290Crossref, Google Scholar
• Asadpour A, Saberi A, Johnson DS, Feige U. An approximation algorithm for max-min fair allocation of indivisible goods. Proc. 39th Annual ACM Sympos. Theory Comput. (2007) (ACM, New York) 114–121Crossref, Google Scholar
• Azar Y, Epstein L, Richter Y, Woeginger GJ. All-norm approximation algorithms. J. Algorithms (2004) 52(1):120–133Crossref, Google Scholar
• Barahona F, Pulleyblank W. Exact arborescences, matchings and cycles. Discrete Appl. Math. (1987) 16(2):91–99Crossref, Google Scholar
• Billionnet A. Approximation algorithms for fractional knapsack problems. Oper. Res. Lett. (2002) 30(5):336–342Crossref, Google Scholar
• Chekuri C, Khanna S. On multidimensional packing problems. SIAM J. Comput. (2004) 33(4):837–851Crossref, Google Scholar
• Correa JR, Fernandes CG, Wakabayashi Y. Approximating a class of combinatorial problems with rational objective function. Math. Programming B (2010) 124(1–2):255–269Crossref, Google Scholar
• Diakonikolas I, Yannakakis M. Small approximate Pareto sets for biobjective shortest paths and other problems. SIAM J. Comput. (2009) 39(4):1340–1371Crossref, Google Scholar
• Garofalakis MN, Ioannidis YE, Jagadish HV, Mumick IS. Multi-dimensional resource scheduling for parallel queries. Proc. ACM SIGMOD Internat. Conf. Management of Data (1996) (ACM, New York) 365–376Crossref, Google Scholar
• Goyal V, Genc-Kaya L, Ravi R. An FPTAS for minimizing the product of two non-negative linear cost functions. Math. Programming (2011) 126(2):401–405Crossref, Google Scholar
• Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG. Optimization and approximation in determinstic sequencing and scheduling: A survey. Ann. Discrete Math. (1979) 5:287–326Crossref, Google Scholar
• Halman N, Klabjan D, Mostagir M, Orlin JB, Simchi-Levi D. A fully polynomial-time approximation scheme for single-item stochastic inventory control with discrete demand. Math. Oper. Res. (2009) 34(3):674–685Link, Google Scholar
• Hashizume S, Fukushima M, Katoh N, Ibaraki T. Approximation algorithms for combinatorial fractional programming problems. Math. Programming (1987) 37(3):255–267Crossref, Google Scholar
• Hochbaum DS, Shmoys DB. Using dual approximation algorithms for scheduling problems: Theoretical and practical results. J. Assoc. Comput. Machinery (1987) 34(1):144–162Crossref, Google Scholar
• Horowitz E, Sahni S. Exact and approximate algorithms for scheduling nonidentical processors. J. Assoc. Comput. Machinery (1976) 23(2):317–327Crossref, Google Scholar
• Hu J, Mehrotra S. Robust and stochastically weighted multi-objective optimization models and reformulations. (2010) . Technical report, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, ILGoogle Scholar
• Ibarra OH, Kim CE. Fast approximation algorithms for the knapsack and sum of subset problems. J. Assoc. Comput. Machinery (1975) 22(4):463–468Crossref, Google Scholar
• Kasperski A, Zielinski P. On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data. Oper. Res. Lett. (2007) 35(4):525–532Crossref, Google Scholar
• Kern W, Woeginger GJ. Quadratic programming and combinatorial minimum weight product problems. Math. Programming (2007) 110(3):641–649Crossref, Google Scholar
• Kök AG, Fisher ML, Vaidyanathan R, Agrawal N, Smith SA. Assortment planning: Review of literature and industry practice. Retail Supply Chain Management (2009) 122(Springer, New York) 99–153International Series in Operations Research and Management ScienceGoogle Scholar
• Koltun V, Papadimitriou CH. Approximately dominating representatives. Theoret. Comput. Sci. (2007) 371(3):148–154Crossref, Google Scholar
• Kouvelis P, Yu G. Robust Discrete Optimization and Its Applications (1997) (Kluwer Academic Publishers, Boston) Crossref, Google Scholar
• Kuno T. Polynomial algorithms for a class of minimum rank-two cost path problems. J. Global Optim. (1999) 15(4):405–417Crossref, Google Scholar
• Lenstra JK, Shmoys DB, Tardos É. Approximation algorithms for scheduling unrelated parallel machines. Math. Programming (1990) 46:259–271Crossref, Google Scholar
• Megiddo N. Combinatorial optimization with rational objective functions. Math. Oper. Res. (1979) 4(4):414–424Link, Google Scholar
• Papadimitriou CH, Yannakakis M, Blum A. On the approximability of trade-offs and optimal access of Web sources. Proc. 41st Annual IEEE Sympos. Foundations Comput. Sci. (2000) (IEEE, Piscataway, NJ) 86–92Crossref, Google Scholar
• Radzik T. Newton's method for fractional combinatorial optimization. Proc. 33rd Annual IEEE Sympos. Foundations Comput. Sci. (1992) (IEEE, Piscataway, NJ) 659–669Crossref, Google Scholar
• Rusmevichientong P, Shen Z-JM, Shmoys DB. A PTAS for capacitated sum-of-ratios optimization. Oper. Res. Lett. (2009) 37(4):230–238Crossref, Google Scholar
• Rusmevichientong P, Shmoys DB, Topaloglu H. Assortment optimization with mixtures of logits. (2010) . Technical report, School of Operations Research and Information Engineering, Cornell University, Ithaca, NYGoogle Scholar
• Safer HM, Orlin JB. Fast approximation schemes for multi-criteria combinatorial optimization. (1995a) . Technical report, Operations Research Center, Massachusetts Institute of Technology, Cambridge, MAGoogle Scholar
• Safer HM, Orlin JB. Fast approximation schemes for multi-criteria flow, knapsack, and scheduling problems. (1995b) . Technical report, Operations Research Center, Massachusetts Institute of Technology, Cambridge, MAGoogle Scholar
• Safer HM, Orlin JB, Dror M. Fully polynomial approximation in multi-criteria combinatorial optimization. (2004) . Technical report, Operations Research Center, Massachusetts Institute of Technology, Cambridge, MAGoogle Scholar
• Sahni S. Algorithms for scheduling independent tasks. J. Assoc. Comput. Machinery (1976) 23(1):116–127Crossref, Google Scholar
• Vassilvitskii S, Yannakakis M. Efficiently computing succinct trade-off curves. Theoret. Comput. Sci. (2005) 348(2–3):334–356Crossref, Google Scholar
• Warburton A. Approximation of Pareto optima in multiple-objective, shortest-path problems. Oper. Res. (1987) 35(1):70–79Link, Google Scholar
• Woeginger GJ. When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)? INFORMS J. Comput. (2000) 12(1):57–74Link, Google Scholar