Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Relaxing the Irrevocability Requirement for Online Graph Algorithms

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 10389))

Included in the following conference series:

  • 1646Accesses

Abstract

Online graph problems are considered in models where the irrevocability requirement is relaxed. Motivated by practical examples where, for example, there is a cost associated with building a facility and no extra cost associated with doing it later, we consider the Late Accept model, where a request can be accepted at a later point, but any acceptance is irrevocable. Similarly, we also consider a Late Reject model, where an accepted request can later be rejected, but any rejection is irrevocable (this is sometimes called preemption). Finally, we consider the Late Accept/Reject model, where late accepts and rejects are both allowed, but any late reject is irrevocable. For Independent Set, the Late Accept/Reject model is necessary to obtain a constant competitive ratio, but for Vertex Cover the Late Accept model is sufficient and for Minimum Spanning Forest the Late Reject model is sufficient. The Matching problem has a competitive ratio of 2, but in the Late Accept/Reject model, its competitive ratio is \(\frac{3}{2}\).

Supported in part by the Danish Council for Independent Research, Natural Sciences, grant DFF-1323-00247, and the Villum Foundation, grant VKR023219.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Bartal, Y., Fiat, A., Leonardi, S.: Lower bounds for on-line graph problems with application to on-line circuit and optical routing. In: 28th STOC, pp. 531–540. ACM (1996)

    Google Scholar 

  2. Boyar, J., Eidenbenz, S.J., Favrholdt, L.M., Kotrbčík, M., Larsen, K.S.: Online dominating set. In: 15th SWAT, LIPIcs, vol. 53, pp. 21:1–21:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH (2016)

    Google Scholar 

  3. Boyar, J., Favrholdt, L.M., Kotrbčík, M., Larsen, K.S.: Relaxing the irrevocability requirements for online graph algorithms. Technical ReportarXiv:1704.08835 [cs.DS], arXiv (2017)

  4. Cygan, M., Jeż, Ł., Sgall, J.: Online knapsack revisited. Theor. Comput. Syst.58(1), 153–190 (2016)

    Article MathSciNet MATH  Google Scholar 

  5. Demange, M., Paschos, V.T.: On-line vertex-covering. Theor. Comput. Sci.332, 83–108 (2005)

    Google Scholar 

  6. Epstein, L., Levin, A., Mestre, J., Segev, D.: Improved approximation guarantees for weighted matching in the semi-streaming model. SIAM J. Discrete Math.25(3), 1251–1265 (2011)

    Article MathSciNet MATH  Google Scholar 

  7. Epstein, L., Levin, A., Segev, D., Weimann, O.: Improved bounds for online preemptive matching. In: 30th STACS, LIPIcs, vol. 20, pp. 389–399. Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH (2013)

    Google Scholar 

  8. Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. Theor. Comput. Sci.348(2–3), 207–216 (2005)

    Article MathSciNet MATH  Google Scholar 

  9. Garay, J.A., Gopal, I.S., Kutten, S., Mansour, Y., Yung, M.: Efficient on-line call control algorithms. J. Algorithm.23(1), 180–194 (1997)

    Article MathSciNet MATH  Google Scholar 

  10. Gu, A., Gupta, A., Kumar, A.: The power of deferral: Maintaining a constant-competitive steiner tree online. SIAM J. Comput.45(1), 1–28 (2016)

    Article MathSciNet MATH  Google Scholar 

  11. Gupta, A., Kumar, A.: Online steiner tree with deletions. In: 25th SODA, pp. 455–467 (2014)

    Google Scholar 

  12. Han, X., Kawase, Y., Makino, K.: Randomized algorithms for online knapsack problems. Theor. Comput. Sci.562, 395–405 (2015)

    Article MathSciNet MATH  Google Scholar 

  13. Han, X., Kawase, Y., Makino, K., Guo, H.: Online removable knapsack problem under convex function. Theor. Comput. Sci.540, 62–69 (2014)

    Article MathSciNet MATH  Google Scholar 

  14. Han, X., Makino, K.: Online minimization knapsack problem. Theor. Comput. Sci.609, 185–196 (2016)

    Article MathSciNet MATH  Google Scholar 

  15. Imase, M., Waxman, B.M.: Dynamic steiner tree problem. SIAM J. Discrete Math.4(3), 369–384 (1991)

    Article MathSciNet MATH  Google Scholar 

  16. Iwama, K., Taketomi, S.: Removable online knapsack problems. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, R., Conejo, R., Hennessy, M. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 293–305. Springer, Heidelberg (2002). doi:10.1007/3-540-45465-9_26

    Chapter  Google Scholar 

  17. Jaillet, P., Lu, X.: Online traveling salesman problems with rejection options. Networks64, 84–95 (2014)

    Article MathSciNet  Google Scholar 

  18. Karlin, A.R., Manasse, M.S., Rudolph, L., Sleator, D.D.: Competitive snoopy caching. Algorithmica3, 79–119 (1988)

    Article MathSciNet MATH  Google Scholar 

  19. Komm, D., Královič, R., Královič, R., Kudahl, C.: Advice complexity of the online induced subgraph problem. In: 41st MFCS, LIPIcs, vol. 58, pp. 59:1–59:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

    Google Scholar 

  20. Korte, B., Hausmann, D.: An analysis of the greedy heuristic for independence systems. Ann. Discrete Math.2, 65–74 (1978)

    Article MathSciNet MATH  Google Scholar 

  21. Megow, N., Skutella, M., Verschae, J., Wiese, A.: The power of recourse for online MST and TSP. SIAM J. Comput.45(3), 859–880 (2016)

    Article MathSciNet MATH  Google Scholar 

  22. Rawitz, D., Rosén, A.: Online budgeted maximum coverage. In: 24th ESA, LIIPCcs, vol. 57, pp. 73:1–73:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH (2016)

    Google Scholar 

  23. Saha, B., Getoor, L.: On maximum coverage in the streaming model & application to multi-topic blog-watch. In: 9th SDM, pp. 697–708. SIAM (2009)

    Google Scholar 

  24. Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Communications of the ACM28(2), 202–208 (1985)

    Article MathSciNet  Google Scholar 

  25. Tarjan, R.E.: Data structures and network algorithms. In: CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44. SIAM (1983)

    Google Scholar 

  26. Vinkemeier, D.E.D., Hougardy, S.: A linear-time approximation algorithm for weighted matchings in graphs. ACM T. Algorithms1(1), 107–122 (2005)

    Article MathSciNet MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Southern Denmark, Odense, Denmark

    Joan Boyar, Lene M. Favrholdt & Kim S. Larsen

  2. The University of Queensland, Brisbane, Australia

    Michal Kotrbčík

Authors
  1. Joan Boyar

    You can also search for this author inPubMed Google Scholar

  2. Lene M. Favrholdt

    You can also search for this author inPubMed Google Scholar

  3. Michal Kotrbčík

    You can also search for this author inPubMed Google Scholar

  4. Kim S. Larsen

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toKim S. Larsen.

Editor information

Editors and Affiliations

  1. Computer Science, University of Toronto , Toronto, Ontario, Canada

    Faith Ellen

  2. Computer Science, Memorial University of Newfoundland , St. John’s, Newfoundland and Labrador, Canada

    Antonina Kolokolova

  3. Carleton University, Ottawa, Ontario, Canada

    Jörg-Rüdiger Sack

Rights and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Cite this paper

Boyar, J., Favrholdt, L.M., Kotrbčík, M., Larsen, K.S. (2017). Relaxing the Irrevocability Requirement for Online Graph Algorithms. In: Ellen, F., Kolokolova, A., Sack, JR. (eds) Algorithms and Data Structures. WADS 2017. Lecture Notes in Computer Science(), vol 10389. Springer, Cham. https://doi.org/10.1007/978-3-319-62127-2_19

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

[8]ページ先頭
©2009-2025 Movatter.jp