IDEAS home Printed from https://ideas.repec.org/a/spr/aqjoor/v20y2022i2d10.1007_s10288-021-00474-1.html
   My bibliography  Save this article

Approximation issues of fractional knapsack with penalties: a note

Author

Listed:
  • Sergey Kovalev

    (INSEEC U. Research Center)

Abstract

Malaguti et al. introduce (Eur J Oper Res 273:874–888, 2019) the Fractional Knapsack Problem with Penalties, which is similar to the classical 0-1 Knapsack problem, except that each of the n variables associated with one of the n items can take any value from the interval [0, 1], and values other than 0 and 1 are penalized. They state that the problem is NP-hard in the ordinary sense as a generalization of the classical 0-1 knapsack problem and develop a fully polynomial-time approximation scheme for the case of non-negative non-decreasing profit functions. It is demonstrated that, unless $$\mathcal P=NP$$ P = N P , no polynomial-time approximation algorithm with any approximation ratio exists for the case of polynomially defined, polynomially computable, discontinuous and non-monotone penalty functions even if there is a single item. A fully polynomial-time approximation scheme which is roughly n times faster than the one of Malaguti et al. for the same case is also presented.

Suggested Citation

  • Sergey Kovalev, 2022. "Approximation issues of fractional knapsack with penalties: a note," 4OR, Springer, vol. 20(2), pages 209-216, June.
    • Handle: RePEc:spr:aqjoor:v:20:y:2022:i:2:d:10.1007_s10288-021-00474-1
    DOI: 10.1007/s10288-021-00474-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10288-021-00474-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10288-021-00474-1?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    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. Malaguti, Enrico & Monaci, Michele & Paronuzzi, Paolo & Pferschy, Ulrich, 2019. "Integer optimization with penalized fractional values: The Knapsack case," European Journal of Operational Research, Elsevier, vol. 273(3), pages 874-888.
    2. Malaguti, Enrico & Medina Durán, Rosa & Toth, Paolo, 2014. "Approaches to real world two-dimensional cutting problems," Omega, Elsevier, vol. 47(C), pages 99-115.
    3. Andrea Lodi & Silvano Martello & Michele Monaci & Claudio Cicconetti & Luciano Lenzini & Enzo Mingozzi & Carl Eklund & Jani Moilanen, 2011. "Efficient Two-Dimensional Packing Algorithms for Mobile WiMAX," Management Science, INFORMS, vol. 57(12), pages 2130-2144, December.
    Full references (including those not matched with items on IDEAS)

    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. Fabio Furini & Enrico Malaguti & Dimitri Thomopulos, 2016. "Modeling Two-Dimensional Guillotine Cutting Problems via Integer Programming," INFORMS Journal on Computing, INFORMS, vol. 28(4), pages 736-751, November.
    2. Malaguti, Enrico & Monaci, Michele & Paronuzzi, Paolo & Pferschy, Ulrich, 2019. "Integer optimization with penalized fractional values: The Knapsack case," European Journal of Operational Research, Elsevier, vol. 273(3), pages 874-888.
    3. Malaguti, Enrico & Monaci, Michele & Paronuzzi, Paolo & Pferschy, Ulrich, 2023. "Corrigendum to: ‘Integer optimization with penalized fractional values: The Knapsack case’ [European Journal of Operational Research (2019) 874–888]," European Journal of Operational Research, Elsevier, vol. 307(2), pages 990-990.
    4. Wuttke, David A. & Heese, H. Sebastian, 2018. "Two-dimensional cutting stock problem with sequence dependent setup times," European Journal of Operational Research, Elsevier, vol. 265(1), pages 303-315.
    5. Michele Monaci & André Gustavo Santos, 2018. "Minimum tiling of a rectangle by squares," Annals of Operations Research, Springer, vol. 271(2), pages 831-851, December.
    6. Hu, Qian & Lim, Andrew & Zhu, Wenbin, 2015. "The two-dimensional vector packing problem with piecewise linear cost function," Omega, Elsevier, vol. 50(C), pages 43-53.
    7. Arbib, Claudio & Marinelli, Fabrizio & Pizzuti, Andrea, 2021. "Number of bins and maximum lateness minimization in two-dimensional bin packing," European Journal of Operational Research, Elsevier, vol. 291(1), pages 101-113.
    8. Martinez-Sykora, Antonio & Alvarez-Valdes, Ramon & Bennell, Julia & Tamarit, Jose Manuel, 2015. "Constructive procedures to solve 2-dimensional bin packing problems with irregular pieces and guillotine cuts," Omega, Elsevier, vol. 52(C), pages 15-32.
    9. Evgeny Gurevsky & Dmitry Kopelevich & Sergey Kovalev & Mikhail Y. Kovalyov, 2023. "Integer knapsack problems with profit functions of the same value range," 4OR, Springer, vol. 21(3), pages 405-419, September.
    10. Rapine, Christophe & Pedroso, Joao Pedro & Akbalik, Ayse, 2022. "The two-dimensional knapsack problem with splittable items in stacks," Omega, Elsevier, vol. 112(C).
    11. Fukasawa, Ricardo & Naoum-Sawaya, Joe & Oliveira, Daniel, 2024. "The price-elastic knapsack problem," Omega, Elsevier, vol. 124(C).
    12. Wang, Danni & Xiao, Fan & Zhou, Lei & Liang, Zhe, 2020. "Two-dimensional skiving and cutting stock problem with setup cost based on column-and-row generation," European Journal of Operational Research, Elsevier, vol. 286(2), pages 547-563.
    13. Katrin Heßler & Stefan Irnich & Tobias Kreiter & Ulrich Pferschy, 2022. "Bin packing with lexicographic objectives for loading weight- and volume-constrained trucks in a direct-shipping system," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(2), pages 1-43, June.
    14. Bennell, J.A. & Cabo, M. & Martínez-Sykora, A., 2018. "A beam search approach to solve the convex irregular bin packing problem with guillotine guts," European Journal of Operational Research, Elsevier, vol. 270(1), pages 89-102.
    15. Silva, Elsa & Oliveira, José Fernando & Silveira, Tiago & Mundim, Leandro & Carravilla, Maria Antónia, 2023. "The Floating-Cuts model: a general and flexible mixed-integer programming model for non-guillotine and guillotine rectangular cutting problems," Omega, Elsevier, vol. 114(C).
    16. Katrin Heßler & Stefan Irnich & Tobias Kreiter & Ulrich Pferschy, 2020. "Lexicographic Bin-Packing Optimization for Loading Trucks in a Direct-Shipping System," Working Papers 2009, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    17. Iori, Manuel & de Lima, Vinícius L. & Martello, Silvano & Miyazawa, Flávio K. & Monaci, Michele, 2021. "Exact solution techniques for two-dimensional cutting and packing," European Journal of Operational Research, Elsevier, vol. 289(2), pages 399-415.
    18. Hadj Salem, Khadija & Silva, Elsa & Oliveira, José Fernando & Carravilla, Maria Antónia, 2023. "Mathematical models for the two-dimensional variable-sized cutting stock problem in the home textile industry," European Journal of Operational Research, Elsevier, vol. 306(2), pages 549-566.
    19. Alonso, M.T. & Alvarez-Valdes, R. & Iori, M. & Parreño, F. & Tamarit, J.M., 2017. "Mathematical models for multicontainer loading problems," Omega, Elsevier, vol. 66(PA), pages 106-117.
    20. Alyne Toscano & Socorro Rangel & Horacio Hideki Yanasse, 2017. "A heuristic approach to minimize the number of saw cycles in small-scale furniture factories," Annals of Operations Research, Springer, vol. 258(2), pages 719-746, November.

    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:spr:aqjoor:v:20:y:2022:i:2:d:10.1007_s10288-021-00474-1. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.