invited-talk

Online Resource Leasing

Authors:

Christine Markarian,

Friedhelm Meyer auf der HeideAuthors Info & Claims

PODC '15: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing

Pages 343 - 344

https://doi.org/10.1145/2767386.2767454

Published: 21 July 2015 Publication History

Get Access

Abstract

Many markets have seen a shift from the idea of buying and moved to leasing instead. Arguably, the latter has been the major catalyst for their success. Ten years ago, research realized this shift and initiated the study of 'online leasing problems' by introducing leasing to online optimization problems. Resources required to provide a service in an 'online leasing problem' are no more bought but leased for different durations. In this paper, we provide an overview of results that contribute to the understanding of 'online resource leasing problems'.

References

[1]

. Meyerson The parking permit problem. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 274 - 284, 2005.

Digital Library

Google Scholar

[2]

. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, and J. Naor The online set cover problem. In Proceedings of the 35th Annual ACM Symposium on the Theory of Computation (STOC), pp. 100 - 105, 2003.

Digital Library

Google Scholar

[3]

. Andrews and L. Zhang Wavelength assignment in optical networks with fixed fiber capacity. In Proceedings of the 31st International Colloquium (ICALP), pp. 134 - 145, 2004.

Google Scholar

[4]

. Gupta, A. Kumar, M. P'al, and Roughgarden Approximation via cost sharing: Simpler and better approximation algorithms for network design. Journal of the ACM (JACM) 54 (3), No. 11, 2007.

Digital Library

Google Scholar

[5]

. Fotakis A primal-dual algorithm for online non-uniform facility location. Journal of Discrete Algorithms, 5 (1), pp. 141 - 148, 2007.

Digital Library

Google Scholar

[6]

. Fotakis On the competitive ratio for online facility location. Algorithmica, 50 (1), pp. 1 - 57, 2008.

Digital Library

Google Scholar

[7]

. Meyerson Online facility location. In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 426 - 431, 2001.

Digital Library

Google Scholar

[8]

. M. Anthony and A. Gupta Infrastructure leasing problems. In Proceedings of the 12th International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 424 - 438, 2007.

Digital Library

Google Scholar

[9]

. Nagarajan and D. Williamson Offline and online facility leasing. In Proceedings of the 13th International Conference on Integer Programming and Combinatorial Optimization (IPCO), 5035, pp. 303 - 315, 2008.

Digital Library

Google Scholar

[10]

. Kling, F. Meyer auf der Heide, and P. Pietrzyk An Algorithm for online facility leasing. In Proceedings of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 61 - 72, 2012.

Digital Library

Google Scholar

[11]

. Li, A. Macker, C. Markarian, F. Meyer auf der Heide, and Sören Riechers Towards flexible demands in pnline leasing problems. In 21st International Computing and Combinatorics Conference (COCOON), to appear, 2015.

Google Scholar

[12]

. Abshoff, C. Markarian, and F. Meyer auf der Heide Randomized Online algorithms for set cover leasing problems. In Proceedings of the 8th Annual International Conference on Combinatorial Optimization and Applications (COCOA), pp 25 - 34, 2014.

Digital Library

Google Scholar

Cited By

View all

Markarian CKhallouf P(2023)Online Facility Location Problems Inspired by the COVID-19 PandemicInnovative Intelligent Industrial Production and Logistics10.1007/978-3-031-37228-5_7(110-123)Online publication date: 7-Jul-2023
https://doi.org/10.1007/978-3-031-37228-5_7
Feldkord BMarkarian CMeyer Auf der Heide F(2017)Price Fluctuation in Online LeasingCombinatorial Optimization and Applications10.1007/978-3-319-71147-8_2(17-31)Online publication date: 16-Nov-2017
https://doi.org/10.1007/978-3-319-71147-8_2

Index Terms

Online Resource Leasing
1. General and reference
  1. Document types
    1. Surveys and overviews

Recommendations

Price Fluctuation in Online Leasing
Combinatorial Optimization and Applications
Abstract
Current theoretical attempts towards understanding real-life leasing scenarios assume the following leasing model. Demands arrive with time and need to be served by leased resources. Different types of leases are available, each with a fixed ...
Towards Flexible Demands in Online Leasing Problems

We consider online leasing problems in which demands arrive over time and need to be served by leasing resources. We introduce a new model for these problems in which a resource can be leased for K different durations each incurring a different cost (...
Randomized Online Algorithms for Set Cover Leasing Problems
Combinatorial Optimization and Applications
Abstract
In the leasing variant of Set Cover presented by Anthony et al. [1], elements arrive over time and must be covered by sets from a family of subsets of . Each set can be leased for different periods of time. Let and . Leasing a set for a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '15: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing

July 2015

508 pages

ISBN:9781450336178

DOI:10.1145/2767386

General Chair:
Chryssis Georgiou
University of Cyprus, Cyprus
,
Program Chair:
Paul G. Spirakis
University of Liverpool, UK & CTI, Greece

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 July 2015

Check for updates

Author Tags

Qualifiers

Invited-talk

Conference

PODC '15

Sponsor:

PODC '15: ACM Symposium on Principles of Distributed Computing

July 21 - 23, 2015

Donostia-San Sebastián, Spain

Acceptance Rates

PODC '15 Paper Acceptance Rate 45 of 191 submissions, 24%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
193
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Markarian CKhallouf P(2023)Online Facility Location Problems Inspired by the COVID-19 PandemicInnovative Intelligent Industrial Production and Logistics10.1007/978-3-031-37228-5_7(110-123)Online publication date: 7-Jul-2023
https://doi.org/10.1007/978-3-031-37228-5_7
Feldkord BMarkarian CMeyer Auf der Heide F(2017)Price Fluctuation in Online LeasingCombinatorial Optimization and Applications10.1007/978-3-319-71147-8_2(17-31)Online publication date: 16-Nov-2017
https://doi.org/10.1007/978-3-319-71147-8_2

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Price Fluctuation in Online Leasing

Towards Flexible Demands in Online Leasing Problems

Randomized Online Algorithms for Set Cover Leasing Problems