Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Towards Flexible Demands in Online Leasing Problems
Ist Teil von
Algorithmica, 2018-05, Vol.80 (5), p.1556-1574
Ort / Verlag
New York: Springer US
Erscheinungsjahr
2018
Link zum Volltext
Quelle
Alma/SFX Local Collection
Beschreibungen/Notizen
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 (longer leases cost less per time unit). Each demand
i
can be served any time between its arrival
a
i
and its deadline
a
i
+
d
i
by a leased resource. The objective is to meet all deadlines while minimizing the total leasing costs. This model is a natural generalization of Meyerson’s
ParkingPermitProblem
(in: Proceedings of the 46th annual IEEE symposium on foundations of computer science, FOCS ’05, IEEE Computer Society, Washington, pp 274–284,
2005
) in which
d
i
=
0
for all
i
. We propose an online algorithm that is
Θ
(
K
+
d
max
l
min
)
-competitive, where
d
max
and
l
min
denote the largest
d
i
and the shortest available lease length, respectively. We also extend
SetCoverLeasing
and
FacilityLeasing
to their respective variants in which deadlines are added. For the former, we give an
O
log
(
m
·
(
K
+
d
max
l
min
)
)
log
l
max
-competitive randomized algorithm, where
m
represents the number of subsets and
l
max
represents the largest available lease length. This improves on existing solutions for the original
SetCoverLeasing
problem. For the latter, we give an
O
(
K
+
d
max
l
min
)
log
l
max
-competitive deterministic algorithm.