Name
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) $$Olog(mK)logn-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) $$OKlogn-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) $$Olmaxloglmax (with the maximal lease length $$l_{\\text {max}} $$lmax). For many natural problem instances, the bound improves to $$O\\left( K^2\\right) $$OK2. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/s10878-015-9915-5 | J. Comb. Optim. |
Keywords | Field | DocType |
Online algorithms,Set cover problems,Facility location problems,Primal dual algorithms,Randomized rounding | Set cover problem,Binary logarithm,Online algorithm,Mathematical optimization,Combinatorics,Combinatorial optimization,Facility location problem,Randomized rounding,Integer programming,Online optimization,Mathematics | Journal |
Volume | Issue | ISSN |
32 | 4 | 1382-6905 |
Citations | PageRank | References |
4 | 0.48 | 19 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sebastian Abshoff | 1 | 12 | 2.66 |
| Peter Kling | 2 | 34 | 6.05 |
| christine markarian | 3 | 4 | 0.48 |
| Friedhelm Meyer auf der Heide | 4 | 1744 | 238.01 |
| Peter Pietrzyk | 5 | 57 | 5.06 |