IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v179y2007i2p281-290.html
   My bibliography  Save this article

Approximation of min-max and min-max regret versions of some combinatorial optimization problems

Author

Listed:
  • Aissi, Hassene
  • Bazgan, Cristina
  • Vanderpooten, Daniel

Abstract

No abstract is available for this item.

Suggested Citation

  • Aissi, Hassene & Bazgan, Cristina & Vanderpooten, Daniel, 2007. "Approximation of min-max and min-max regret versions of some combinatorial optimization problems," European Journal of Operational Research, Elsevier, vol. 179(2), pages 281-290, June.
  • Handle: RePEc:eee:ejores:v:179:y:2007:i:2:p:281-290
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(06)00190-1
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Thomas Erlebach & Hans Kellerer & Ulrich Pferschy, 2002. "Approximating Multiobjective Knapsack Problems," Management Science, INFORMS, vol. 48(12), pages 1603-1612, December.
    2. Safer, Hershel M. & Orlin, James B., 1953-, 1995. "Fast approximation schemes for multi-criteria combinatorial optimization," Working papers 3756-95., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    3. Sartaj Sahni, 1977. "General Techniques for Combinatorial Approximation," Operations Research, INFORMS, vol. 25(6), pages 920-936, December.
    4. Safer, Hershel M. & Orlin, James B., 1953-, 1995. "Fast approximation schemes for multi-criteria flow, knapsack, and scheduling problems," Working papers 3757-95., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Choi, Byung-Cheon & Chung, Kwanghun, 2016. "Min–max regret version of a scheduling problem with outsourcing decisions under processing time uncertainty," European Journal of Operational Research, Elsevier, vol. 252(2), pages 367-375.
    2. Alireza Amirteimoori & Simin Masrouri, 2021. "DEA-based competition strategy in the presence of undesirable products: An application to paper mills," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 31(2), pages 5-21.
    3. Chassein, André B. & Goerigk, Marc, 2015. "A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem," European Journal of Operational Research, Elsevier, vol. 244(3), pages 739-747.
    4. Chassein, André & Goerigk, Marc, 2017. "Minmax regret combinatorial optimization problems with ellipsoidal uncertainty sets," European Journal of Operational Research, Elsevier, vol. 258(1), pages 58-69.
    5. Baldo, Alessandro & Boffa, Matteo & Cascioli, Lorenzo & Fadda, Edoardo & Lanza, Chiara & Ravera, Arianna, 2023. "The polynomial robust knapsack problem," European Journal of Operational Research, Elsevier, vol. 305(3), pages 1424-1434.
    6. Shashi Mittal & Andreas S. Schulz, 2013. "A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One," Operations Research, INFORMS, vol. 61(2), pages 386-397, April.
    7. Fabrice Talla Nobibon & Roel Leus, 2014. "Complexity Results and Exact Algorithms for Robust Knapsack Problems," Journal of Optimization Theory and Applications, Springer, vol. 161(2), pages 533-552, May.
    8. Büsing, Christina & Goetzmann, Kai-Simon & Matuschke, Jannik & Stiller, Sebastian, 2017. "Reference points and approximation algorithms in multicriteria discrete optimization," European Journal of Operational Research, Elsevier, vol. 260(3), pages 829-840.
    9. Roy, Bernard, 2010. "Robustness in operational research and decision aiding: A multi-faceted issue," European Journal of Operational Research, Elsevier, vol. 200(3), pages 629-638, February.
    10. Klamroth, Kathrin & Köbis, Elisabeth & Schöbel, Anita & Tammer, Christiane, 2017. "A unified approach to uncertain optimization," European Journal of Operational Research, Elsevier, vol. 260(2), pages 403-420.
    11. Botte, Marco & Schöbel, Anita, 2019. "Dominance for multi-objective robust optimization concepts," European Journal of Operational Research, Elsevier, vol. 273(2), pages 430-440.
    12. Adam Kasperski & Paweł Zieliński, 2009. "A randomized algorithm for the min-max selecting items problem with uncertain weights," Annals of Operations Research, Springer, vol. 172(1), pages 221-230, November.
    13. Aissi, Hassene & Bazgan, Cristina & Vanderpooten, Daniel, 2009. "Min-max and min-max regret versions of combinatorial optimization problems: A survey," European Journal of Operational Research, Elsevier, vol. 197(2), pages 427-438, September.
    14. Mikita Hradovich & Adam Kasperski & Paweł Zieliński, 2017. "Recoverable robust spanning tree problem under interval uncertainty representations," Journal of Combinatorial Optimization, Springer, vol. 34(2), pages 554-573, August.
    15. J. Puerto & A. M. Rodríguez-Chía & A. Tamir, 2009. "Minimax Regret Single-Facility Ordered Median Location Problems on Networks," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 77-87, February.
    16. Kalaı¨, Rim & Lamboray, Claude & Vanderpooten, Daniel, 2012. "Lexicographic α-robustness: An alternative to min–max criteria," European Journal of Operational Research, Elsevier, vol. 220(3), pages 722-728.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Bazgan, Cristina & Hugot, Hadrien & Vanderpooten, Daniel, 2009. "Implementing an efficient fptas for the 0-1 multi-objective knapsack problem," European Journal of Operational Research, Elsevier, vol. 198(1), pages 47-56, October.
    2. Laumanns, Marco & Zenklusen, Rico, 2011. "Stochastic convergence of random search methods to fixed size Pareto front approximations," European Journal of Operational Research, Elsevier, vol. 213(2), pages 414-421, September.
    3. Nir Halman & Mikhail Y. Kovalyov & Alain Quilliot & Dvir Shabtay & Moshe Zofi, 2019. "Bi-criteria path problem with minimum length and maximum survival probability," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(2), pages 469-489, June.
    4. Lakmali Weerasena, 2022. "Advancing local search approximations for multiobjective combinatorial optimization problems," Journal of Combinatorial Optimization, Springer, vol. 43(3), pages 589-612, April.
    5. Arne Herzel & Stefan Ruzika & Clemens Thielen, 2021. "Approximation Methods for Multiobjective Optimization Problems: A Survey," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1284-1299, October.
    6. Aissi, Hassene & Bazgan, Cristina & Vanderpooten, Daniel, 2009. "Min-max and min-max regret versions of combinatorial optimization problems: A survey," European Journal of Operational Research, Elsevier, vol. 197(2), pages 427-438, September.
    7. Fritz Bökler & Markus Chimani & Mirko H. Wagner, 2022. "On the rectangular knapsack problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 96(1), pages 149-160, August.
    8. George Kozanidis, 2009. "Solving the linear multiple choice knapsack problem with two objectives: profit and equity," Computational Optimization and Applications, Springer, vol. 43(2), pages 261-294, June.
    9. Luis Paquete & Tommaso Schiavinotto & Thomas Stützle, 2007. "On local optima in multiobjective combinatorial optimization problems," Annals of Operations Research, Springer, vol. 156(1), pages 83-97, December.
    10. Mancini, Simona & Triki, Chefi & Piya, Sujan, 2022. "Optimal selection of touristic packages based on user preferences during sports mega-events," European Journal of Operational Research, Elsevier, vol. 302(3), pages 819-830.
    11. Imed Kacem & Hans Kellerer & Yann Lanuel, 2015. "Approximation algorithms for maximizing the weighted number of early jobs on a single machine with non-availability intervals," Journal of Combinatorial Optimization, Springer, vol. 30(3), pages 403-412, October.
    12. Tomášek, M. & Mikoláš, V., 1979. "Remarks on the density functional approach to the inhomogeneous electron gas," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 95(3), pages 547-560.
    13. Liesio, Juuso & Mild, Pekka & Salo, Ahti, 2007. "Preference programming for robust portfolio modeling and project selection," European Journal of Operational Research, Elsevier, vol. 181(3), pages 1488-1505, September.
    14. Perrot, F., 1979. "Zero-temperature equation of state of metals in the statistical model with density gradient correction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 98(3), pages 555-565.
    15. Matthias Ehrgott & Xavier Gandibleux, 2004. "Approximative solution methods for multiobjective combinatorial optimization," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 12(1), pages 1-63, June.
    16. José Figueira & Luís Paquete & Marco Simões & Daniel Vanderpooten, 2013. "Algorithmic improvements on dynamic programming for the bi-objective {0,1} knapsack problem," Computational Optimization and Applications, Springer, vol. 56(1), pages 97-111, September.
    17. Mavrotas, George & Florios, Kostas, 2013. "An improved version of the augmented epsilon-constraint method (AUGMECON2) for finding the exact Pareto set in Multi-Objective Integer Programming problems," MPRA Paper 105034, University Library of Munich, Germany.
    18. Safer, Hershel M. & Orlin, James B., 1953-, 1995. "Fast approximation schemes for multi-criteria combinatorial optimization," Working papers 3756-95., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    19. Halman, Nir & Kellerer, Hans & Strusevich, Vitaly A., 2018. "Approximation schemes for non-separable non-linear boolean programming problems under nested knapsack constraints," European Journal of Operational Research, Elsevier, vol. 270(2), pages 435-447.
    20. Dolgui, Alexandre & Kovalev, Sergey & Pesch, Erwin, 2015. "Approximate solution of a profit maximization constrained virtual business planning problem," Omega, Elsevier, vol. 57(PB), pages 212-216.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:179:y:2007:i:2:p:281-290. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.