Parking Permit and Network Leasing Problems: Murilo de Lima
ICE-TCS seminar
ICE-TCS seminar #320
Date and time: Tuesday, 6 November 2018, 12:10-13:00
Location: Room V1.04
Speaker: Murilo de Lima (Reykjavik University)
Title: Parking Permit and Network Leasing Problems
Abstract: In traditional optimization problems, we can think that a solution is built by acquiring resources that persist in time. In contrast, in the leasing optimization model, we assume that resources may be leased for different lengths of time and that, due to economies of scale, it is more cost-effective to lease a resource for longer periods. This model has received some attention recently, since it models problems such as cloud resource allocation.
In this seminar, we present some results on approximation and online algorithms for three generalizations of the parking permit problem, which is the seminal leasing problem (Meyerson, FOCS 2005): (i) a generalization with multiple identical resources, (ii) a rent-or-buy generalization, and (iii) a generalization with arbitrary capacities. The last one was proposed by Hu, Ludwig, Richa and Schmid (ICDCS 2015), and we extend their results.
Those results yield approximation and competitive online algorithms for leasing variants of the Steiner network problem, the rent-or-buy problem, and the buy-at-bulk network design problem, by using the technique of approximating a finite metric by a tree metric. In particular, we improve the previous best approximation algorithm for the leasing version of the multi-commodity rent-or-buy-problem.
We also present some partial results for a leasing variant of the connected facility location problem.
This is joint work with Orlando Lee (University of Campinas, Brazil) and Mário César San Felice (Federal University of São Carlos, Brazil).
