Towards the price of leasing online

Sebastian Abshoff (), Peter Kling (), Christine Markarian (), Friedhelm Meyer auf der Heide () and Peter Pietrzyk ()
Additional contact information
Sebastian Abshoff: University of Paderborn
Peter Kling: Simon Fraser University, School of Computing Science
Christine Markarian: University of Paderborn
Friedhelm Meyer auf der Heide: University of Paderborn
Peter Pietrzyk: University of Paderborn

Journal of Combinatorial Optimization, 2016, vol. 32, issue 4, No 14, 1197-1216

Abstract: Abstract We consider online optimization problems in which certain goods have to be acquired in order to provide a service or infrastructure. Classically, decisions for such problems are considered as final: one buys the goods. However, in many real world applications, there is a shift away from the idea of buying goods. Instead, leasing is often a more flexible and lucrative business model. Research has realized this shift and recently initiated the theoretical study of leasing models (Anthony and Gupta in Proceedings of the integer programming and combinatorial optimization: 12th International IPCO Conference, Ithaca, NY, USA, June 25–27, 2007; Meyerson in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23–25 Oct 2005, Pittsburgh, PA, USA, 2005; Nagarajan and Williamson in Discret Optim 10(4):361–370, 2013) We extend this line of work and suggest a more systematic study of leasing aspects for a class of online optimization problems. We provide two major technical results. We introduce the leasing variant of online set multicover and give an $$O\left( \log (mK)\log n\right) $$ O log ( m K ) log n -competitive algorithm (with n, m, and K being the number of elements, sets, and leases, respectively). Our results also imply improvements for the non-leasing variant of online set cover. Moreover, we extend results for the leasing variant of online facility location. Nagarajan and Williamson (Discret Optim 10(4):361–370, 2013) gave an $$O\left( K\log n\right) $$ O K log n -competitive algorithm for this problem (with n and K being the number of clients and leases, respectively). We remove the dependency on n (and, thereby, on time). In general, this leads to a bound of $$O\left( l_{\text {max}} \log l_{\text {max}} \right) $$ O l max log l max (with the maximal lease length $$l_{\text {max}} $$ l max ). For many natural problem instances, the bound improves to $$O\left( K^2\right) $$ O K 2 .

Keywords: Online algorithms; Set cover problems; Facility location problems; Primal dual algorithms; Randomized rounding (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9915-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:32:y:2016:i:4:d:10.1007_s10878-015-9915-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9915-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().