IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v275y2019i2d10.1007_s10479-018-3025-6.html
   My bibliography  Save this article

On interval and circular-arc covering problems

Author

Listed:
  • Reuven Cohen

    (Bar-Ilan University)

  • Mira Gonen

    (Ariel University)

Abstract

In this paper we study several related problems of finding optimal interval and circular-arc covering. We present solutions to the maximum k-interval (k-circular-arc) coverage problems, in which we want to cover maximum weight by selecting k intervals (circular-arcs) out of a given set of intervals (circular-arcs), respectively, the weighted interval covering problem, in which we want to cover maximum weight by placing k intervals with a given length, and the k-centers problem. The general sets version of the discussed problems, namely the general measure k-centers problem and the maximum covering problem for sets are known to be NP-hard. However, for the one dimensional restrictions studied here, and even for circular-arc graphs, we present efficient, polynomial time, algorithms that solve these problems. Our results for the maximum k-interval and k-circular-arc covering problems hold for any right continuous positive measure on $$\mathbb {R}$$ R .

Suggested Citation

  • Reuven Cohen & Mira Gonen, 2019. "On interval and circular-arc covering problems," Annals of Operations Research, Springer, vol. 275(2), pages 281-295, April.
    • Handle: RePEc:spr:annopr:v:275:y:2019:i:2:d:10.1007_s10479-018-3025-6
    DOI: 10.1007/s10479-018-3025-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-018-3025-6
    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/s10479-018-3025-6?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. CORNUEJOLS, Gérard & EMHAUSER, George L. & WOLSEY, Laurence A., 1980. "Worst-case and probabilistic analysis of algorithms for a location problem," LIDAM Reprints CORE 437, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. de Werra, Dominique & Eisenbeis, Christine & Lelait, Sylvain & Stohr, Elena, 2002. "Circular-arc graph coloring: On chords and circuits in the meeting graph," European Journal of Operational Research, Elsevier, vol. 136(3), pages 483-500, February.
    3. Reuven Cohen & Mira Gonen & Asaf Levin & Shmuel Onn, 2017. "On nonlinear multi-covering problems," Journal of Combinatorial Optimization, Springer, vol. 33(2), pages 645-659, February.
    4. Gerard Cornuejols & George L. Nemhauser & Laurence A. Wolsey, 1980. "Worst-Case and Probabilistic Analysis of Algorithms for a Location Problem," Operations Research, INFORMS, vol. 28(4), pages 847-858, August.
    5. Alberto Caprara & Paolo Toth & Matteo Fischetti, 2000. "Algorithms for the Set Covering Problem," Annals of Operations Research, Springer, vol. 98(1), pages 353-371, December.
    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. Songhua Li & Minming Li & Lingjie Duan & Victor C. S. Lee, 2022. "Online algorithms for the maximum k-interval coverage problem," Journal of Combinatorial Optimization, Springer, vol. 44(5), pages 3364-3404, December.

    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. A.A. Ageev & M.I. Sviridenko, 2004. "Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee," Journal of Combinatorial Optimization, Springer, vol. 8(3), pages 307-328, September.
    2. Reuven Cohen & Mira Gonen & Asaf Levin & Shmuel Onn, 2017. "On nonlinear multi-covering problems," Journal of Combinatorial Optimization, Springer, vol. 33(2), pages 645-659, February.
    3. Coslovich, Luca & Pesenti, Raffaele & Ukovich, Walter, 2006. "Minimizing fleet operating costs for a container transportation company," European Journal of Operational Research, Elsevier, vol. 171(3), pages 776-786, June.
    4. İbrahim Muter & Ş. İlker Birbil & Güvenç Şahin, 2010. "Combination of Metaheuristic and Exact Algorithms for Solving Set Covering-Type Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 22(4), pages 603-619, November.
    5. R. Baldacci & E. Hadjiconstantinou & A. Mingozzi, 2004. "An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation," Operations Research, INFORMS, vol. 52(5), pages 723-738, October.
    6. Lan, Guanghui & DePuy, Gail W. & Whitehouse, Gary E., 2007. "An effective and simple heuristic for the set covering problem," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1387-1403, February.
    7. Masoud Yaghini & Mohammad Karimi & Mohadeseh Rahbar, 2015. "A set covering approach for multi-depot train driver scheduling," Journal of Combinatorial Optimization, Springer, vol. 29(3), pages 636-654, April.
    8. 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.
    9. Patrizia Beraldi & Andrzej Ruszczyński, 2002. "The Probabilistic Set-Covering Problem," Operations Research, INFORMS, vol. 50(6), pages 956-967, December.
    10. Jee Eun Kang & Will Recker, 2015. "Strategic Hydrogen Refueling Station Locations with Scheduling and Routing Considerations of Individual Vehicles," Transportation Science, INFORMS, vol. 49(4), pages 767-783, November.
    11. Büsing, Christina & Comis, Martin & Schmidt, Eva & Streicher, Manuel, 2021. "Robust strategic planning for mobile medical units with steerable and unsteerable demands," European Journal of Operational Research, Elsevier, vol. 295(1), pages 34-50.
    12. Gianpaolo Ghiani & Emanuele Manni & Antonella Quaranta, 2010. "Shift Scheduling Problem in Same-Day Courier Industry," Transportation Science, INFORMS, vol. 44(1), pages 116-124, February.
    13. Bentz, Cédric & Cornaz, Denis & Ries, Bernard, 2013. "Packing and covering with linear programming: A survey," European Journal of Operational Research, Elsevier, vol. 227(3), pages 409-422.
    14. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    15. Jacob R. Fooks & Kent D. Messer & Maik Kecinski, 2018. "A Cautionary Note on the Use of Benefit Metrics for Cost-Effective Conservation," Environmental & Resource Economics, Springer;European Association of Environmental and Resource Economists, vol. 71(4), pages 985-999, December.
    16. Giovanni Felici & Sokol Ndreca & Aldo Procacci & Benedetto Scoppola, 2016. "A-priori upper bounds for the set covering problem," Annals of Operations Research, Springer, vol. 238(1), pages 229-241, March.
    17. Owais, Mahmoud & Moussa, Ghada S. & Hussain, Khaled F., 2019. "Sensor location model for O/D estimation: Multi-criteria meta-heuristics approach," Operations Research Perspectives, Elsevier, vol. 6(C).
    18. Shane N. Hall & Sheldon H. Jacobson & Edward C. Sewell, 2008. "An Analysis of Pediatric Vaccine Formulary Selection Problems," Operations Research, INFORMS, vol. 56(6), pages 1348-1365, December.
    19. Nguyen, Tri-Dung, 2014. "A fast approximation algorithm for solving the complete set packing problem," European Journal of Operational Research, Elsevier, vol. 237(1), pages 62-70.
    20. Amadeu A. Coco & Andréa Cynthia Santos & Thiago F. Noronha, 2022. "Robust min-max regret covering problems," Computational Optimization and Applications, Springer, vol. 83(1), pages 111-141, September.

    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:annopr:v:275:y:2019:i:2:d:10.1007_s10479-018-3025-6. 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.