IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v68y2017i4d10.1007_s10898-017-0514-0.html
   My bibliography  Save this article

A new fully polynomial time approximation scheme for the interval subset sum problem

Author

Listed:
  • Rui Diao

    (Chinese Academy of Sciences)

  • Ya-Feng Liu

    (Chinese Academy of Sciences)

  • Yu-Hong Dai

    (Chinese Academy of Sciences)

Abstract

The interval subset sum problem (ISSP) is a generalization of the well-known subset sum problem. Given a set of intervals $$\left\{ [a_{i,1},a_{i,2}]\right\} _{i=1}^n$$ [ a i , 1 , a i , 2 ] i = 1 n and a target integer T, the ISSP is to find a set of integers, at most one from each interval, such that their sum best approximates the target T but cannot exceed it. In this paper, we first study the computational complexity of the ISSP. We show that the ISSP is relatively easy to solve compared to the 0–1 knapsack problem. We also identify several subclasses of the ISSP which are polynomial time solvable (with high probability), albeit the problem is generally NP-hard. Then, we propose a new fully polynomial time approximation scheme for solving the general ISSP problem. The time and space complexities of the proposed scheme are $${{\mathcal {O}}}\left( n \max \left\{ 1 / \epsilon ,\log n\right\} \right) $$ O n max 1 / ϵ , log n and $$\mathcal{O}\left( n+1/\epsilon \right) ,$$ O n + 1 / ϵ , respectively, where $$\epsilon $$ ϵ is the relative approximation error. To the best of our knowledge, the proposed scheme has almost the same time complexity but a significantly lower space complexity compared to the best known scheme. Both the correctness and efficiency of the proposed scheme are validated by numerical simulations. In particular, the proposed scheme successfully solves ISSP instances with $$n=100{,}000$$ n = 100 , 000 and $$\epsilon =0.1\%$$ ϵ = 0.1 % within 1 s.

Suggested Citation

  • Rui Diao & Ya-Feng Liu & Yu-Hong Dai, 2017. "A new fully polynomial time approximation scheme for the interval subset sum problem," Journal of Global Optimization, Springer, vol. 68(4), pages 749-775, August.
  • Handle: RePEc:spr:jglopt:v:68:y:2017:i:4:d:10.1007_s10898-017-0514-0
    DOI: 10.1007/s10898-017-0514-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-017-0514-0
    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/s10898-017-0514-0?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. Magazine, M. J. & Oguz, Osman, 1981. "A fully polynomial approximation algorithm for the 0-1 knapsack problem," European Journal of Operational Research, Elsevier, vol. 8(3), pages 270-273, November.
    2. Hans Kellerer & Ulrich Pferschy, 1999. "A New Fully Polynomial Time Approximation Scheme for the Knapsack Problem," Journal of Combinatorial Optimization, Springer, vol. 3(1), pages 59-71, July.
    3. Eugene L. Lawler, 1979. "Fast Approximation Algorithms for Knapsack Problems," Mathematics of Operations Research, INFORMS, vol. 4(4), pages 339-356, November.
    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. Caprara, Alberto & Kellerer, Hans & Pferschy, Ulrich & Pisinger, David, 2000. "Approximation algorithms for knapsack problems with cardinality constraints," European Journal of Operational Research, Elsevier, vol. 123(2), pages 333-345, June.
    2. Rebi Daldal & Iftah Gamzu & Danny Segev & Tonguç Ünlüyurt, 2016. "Approximation algorithms for sequential batch‐testing of series systems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(4), pages 275-286, June.
    3. Freville, Arnaud, 2004. "The multidimensional 0-1 knapsack problem: An overview," European Journal of Operational Research, Elsevier, vol. 155(1), pages 1-21, May.
    4. 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.
    5. Thomas Erlebach & Hans Kellerer & Ulrich Pferschy, 2002. "Approximating Multiobjective Knapsack Problems," Management Science, INFORMS, vol. 48(12), pages 1603-1612, December.
    6. Zhenbo Wang & Wenxun Xing, 2009. "A successive approximation algorithm for the multiple knapsack problem," Journal of Combinatorial Optimization, Springer, vol. 17(4), pages 347-366, May.
    7. Hans Kellerer & Ulrich Pferschy, 1999. "A New Fully Polynomial Time Approximation Scheme for the Knapsack Problem," Journal of Combinatorial Optimization, Springer, vol. 3(1), pages 59-71, July.
    8. Arnaud Fréville & SaÏd Hanafi, 2005. "The Multidimensional 0-1 Knapsack Problem—Bounds and Computational Aspects," Annals of Operations Research, Springer, vol. 139(1), pages 195-227, October.
    9. Luca Bertazzi, 2012. "Minimum and Worst-Case Performance Ratios of Rollout Algorithms," Journal of Optimization Theory and Applications, Springer, vol. 152(2), pages 378-393, February.
    10. Zhou Xu, 2013. "The knapsack problem with a minimum filling constraint," Naval Research Logistics (NRL), John Wiley & Sons, vol. 60(1), pages 56-63, February.
    11. Aardal, Karen & van den Berg, Pieter L. & Gijswijt, Dion & Li, Shanfei, 2015. "Approximation algorithms for hard capacitated k-facility location problems," European Journal of Operational Research, Elsevier, vol. 242(2), pages 358-368.
    12. Haris Aziz & Sujit Gujar & Manisha Padala & Mashbat Suzuki & Jeremy Vollen, 2022. "Coordinating Monetary Contributions in Participatory Budgeting," Papers 2206.05966, arXiv.org, revised Feb 2023.
    13. Daria Dzyabura & Srikanth Jagabathula, 2018. "Offline Assortment Optimization in the Presence of an Online Channel," Management Science, INFORMS, vol. 64(6), pages 2767-2786, June.
    14. Francisco Castillo-Zunino & Pinar Keskinocak, 2021. "Bi-criteria multiple knapsack problem with grouped items," Journal of Heuristics, Springer, vol. 27(5), pages 747-789, October.
    15. Hifi, Mhand & M'Hallah, Rym, 2006. "Strip generation algorithms for constrained two-dimensional two-staged cutting problems," European Journal of Operational Research, Elsevier, vol. 172(2), pages 515-527, July.
    16. Zhong, Xueling & Ou, Jinwen & Wang, Guoqing, 2014. "Order acceptance and scheduling with machine availability constraints," European Journal of Operational Research, Elsevier, vol. 232(3), pages 435-441.
    17. Zhong, Weiya & Dosa, Gyorgy & Tan, Zhiyi, 2007. "On the machine scheduling problem with job delivery coordination," European Journal of Operational Research, Elsevier, vol. 182(3), pages 1057-1072, November.
    18. Edward Y H Lin & Chung-Min Wu, 2004. "The multiple-choice multi-period knapsack problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(2), pages 187-197, February.
    19. Alberto Caprara & Andrea Lodi & Michele Monaci, 2005. "Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing," Mathematics of Operations Research, INFORMS, vol. 30(1), pages 150-172, February.
    20. Stephan Helfrich & Arne Herzel & Stefan Ruzika & Clemens Thielen, 2022. "An approximation algorithm for a general class of multi-parametric optimization problems," Journal of Combinatorial Optimization, Springer, vol. 44(3), pages 1459-1494, October.

    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:jglopt:v:68:y:2017:i:4:d:10.1007_s10898-017-0514-0. 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.