---
_id: '580'
abstract:
- lang: eng
text: We present and study a new model for energy-aware and profit-oriented scheduling
on a single processor.The processor features dynamic speed scaling as well as
suspension to a sleep mode.Jobs arrive over time, are preemptable, and have different
sizes, values, and deadlines.On the arrival of a new job, the scheduler may either
accept or reject the job.Accepted jobs need a certain energy investment to be
finished in time, while rejected jobs cause costs equal to their values.Here,
power consumption at speed $s$ is given by $P(s)=s^{\alpha}+\beta$ and the energy
investment is power integrated over time.Additionally, the scheduler may decide
to suspend the processor to a sleep mode in which no energy is consumed, though
awaking entails fixed transition costs $\gamma$.The objective is to minimize the
total value of rejected jobs plus the total energy.Our model combines aspects
from advanced energy conservation techniques (namely speed scaling and sleep states)
and profit-oriented scheduling models.We show that \emph{rejection-oblivious}
schedulers (whose rejection decisions are not based on former decisions) have
– in contrast to the model without sleep states – an unbounded competitive ratio.It
turns out that the jobs' value densities (the ratio between a job's value and
its work) are crucial for the performance of such schedulers.We give an algorithm
whose competitiveness nearly matches the lower bound w.r.t\text{.} the maximum
value density.If the maximum value density is not too large, the competitiveness
becomes $\alpha^{\alpha}+2e\alpha$.Also, we show that it suffices to restrict
the value density of low-value jobs only.Using a technique from \cite{Chan:2010}
we transfer our results to processors with a fixed maximum speed.
author:
- first_name: Andreas
full_name: Cord-Landwehr, Andreas
last_name: Cord-Landwehr
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Fredrik
full_name: Mallmann Trenn, Fredrik
last_name: Mallmann Trenn
citation:
ama: 'Cord-Landwehr A, Kling P, Mallmann Trenn F. Slow Down & Sleep for Profit
in Online Deadline Scheduling. In: Even G, Rawitz D, eds. Proceedings of the
1st Mediterranean Conference on Algorithms (MedAlg). LNCS. ; 2012:218-231.
doi:10.1007/978-3-642-34862-4_17'
apa: Cord-Landwehr, A., Kling, P., & Mallmann Trenn, F. (2012). Slow Down &
Sleep for Profit in Online Deadline Scheduling. In G. Even & D. Rawitz (Eds.),
Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg)
(pp. 218–231). https://doi.org/10.1007/978-3-642-34862-4_17
bibtex: '@inproceedings{Cord-Landwehr_Kling_Mallmann Trenn_2012, series={LNCS},
title={Slow Down & Sleep for Profit in Online Deadline Scheduling}, DOI={10.1007/978-3-642-34862-4_17},
booktitle={Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg)},
author={Cord-Landwehr, Andreas and Kling, Peter and Mallmann Trenn, Fredrik},
editor={Even, Guy and Rawitz, DrorEditors}, year={2012}, pages={218–231}, collection={LNCS}
}'
chicago: Cord-Landwehr, Andreas, Peter Kling, and Fredrik Mallmann Trenn. “Slow
Down & Sleep for Profit in Online Deadline Scheduling.” In Proceedings
of the 1st Mediterranean Conference on Algorithms (MedAlg), edited by Guy
Even and Dror Rawitz, 218–31. LNCS, 2012. https://doi.org/10.1007/978-3-642-34862-4_17.
ieee: A. Cord-Landwehr, P. Kling, and F. Mallmann Trenn, “Slow Down & Sleep
for Profit in Online Deadline Scheduling,” in Proceedings of the 1st Mediterranean
Conference on Algorithms (MedAlg), 2012, pp. 218–231.
mla: Cord-Landwehr, Andreas, et al. “Slow Down & Sleep for Profit in Online
Deadline Scheduling.” Proceedings of the 1st Mediterranean Conference on Algorithms
(MedAlg), edited by Guy Even and Dror Rawitz, 2012, pp. 218–31, doi:10.1007/978-3-642-34862-4_17.
short: 'A. Cord-Landwehr, P. Kling, F. Mallmann Trenn, in: G. Even, D. Rawitz (Eds.),
Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg), 2012,
pp. 218–231.'
date_created: 2017-10-17T12:42:45Z
date_updated: 2022-01-06T07:02:42Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-642-34862-4_17
editor:
- first_name: Guy
full_name: Even, Guy
last_name: Even
- first_name: Dror
full_name: Rawitz, Dror
last_name: Rawitz
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T09:03:39Z
date_updated: 2018-03-15T09:03:39Z
file_id: '1265'
file_name: 580-P._Kling__F._Mallmann-Trenn__A._Cord-Landwehr_-_Slow_Down___Sleep_for_Profit_in_Online_Deadline_Scheduling.pdf
file_size: 325939
relation: main_file
success: 1
file_date_updated: 2018-03-15T09:03:39Z
has_accepted_license: '1'
language:
- iso: eng
page: 218-231
project:
- _id: '1'
name: SFB 901
- _id: '14'
name: SFB 901 - Subprojekt C2
- _id: '16'
name: SFB 901 - Subproject C4
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg)
series_title: LNCS
status: public
title: Slow Down & Sleep for Profit in Online Deadline Scheduling
type: conference
user_id: '477'
year: '2012'
...
---
_id: '581'
abstract:
- lang: eng
text: 'Nanoparticles are getting more and more in the focus of the scientic community
since the potential for the development of very small particles interacting with
each other and completing medical and other tasks is getting bigger year by year.
In this work we introduce a distributed local algorithm for arranging a set of
nanoparticles on the discrete plane into specic geometric shapes, for instance
a rectangle. The concept of a particle we use can be seen as a simple mobile robot
with the following restrictions: it can only view the state of robots it is physically
connected to, is anonymous, has only a constant size memory, can only move by
using other particles as an anchor point on which it pulls itself alongside, and
it operates in Look-Compute-Move cycles. The main result of this work is the presentation
of a random distributed local algorithm which transforms any given connected set
of particles into a particular geometric shape. As an example we provide a version
of this algorithm for forming a rectangle with an arbitrary predened aspect ratio.
To the best of our knowledge this is the rst work that considers arrangement problems
for these types of robots.'
author:
- first_name: Maximilian
full_name: Drees, Maximilian
last_name: Drees
- first_name: Martina
full_name: 'Hüllmann (married name: Eikel), Martina'
last_name: 'Hüllmann (married name: Eikel)'
- first_name: Andreas
full_name: Koutsopoulos, Andreas
last_name: Koutsopoulos
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: 'Drees M, Hüllmann (married name: Eikel) M, Koutsopoulos A, Scheideler C. Self-Organizing
Particle Systems. In: Proceedings of the 26th IEEE International Parallel and
Distributed Processing Symposium (IPDPS). ; 2012:1272-1283. doi:10.1109/IPDPS.2012.116'
apa: 'Drees, M., Hüllmann (married name: Eikel), M., Koutsopoulos, A., & Scheideler,
C. (2012). Self-Organizing Particle Systems. In Proceedings of the 26th IEEE
International Parallel and Distributed Processing Symposium (IPDPS) (pp. 1272–1283).
https://doi.org/10.1109/IPDPS.2012.116'
bibtex: '@inproceedings{Drees_Hüllmann (married name: Eikel)_Koutsopoulos_Scheideler_2012,
title={Self-Organizing Particle Systems}, DOI={10.1109/IPDPS.2012.116},
booktitle={Proceedings of the 26th IEEE International Parallel and Distributed
Processing Symposium (IPDPS)}, author={Drees, Maximilian and Hüllmann (married
name: Eikel), Martina and Koutsopoulos, Andreas and Scheideler, Christian}, year={2012},
pages={1272–1283} }'
chicago: 'Drees, Maximilian, Martina Hüllmann (married name: Eikel), Andreas Koutsopoulos,
and Christian Scheideler. “Self-Organizing Particle Systems.” In Proceedings
of the 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS),
1272–83, 2012. https://doi.org/10.1109/IPDPS.2012.116.'
ieee: 'M. Drees, M. Hüllmann (married name: Eikel), A. Koutsopoulos, and C. Scheideler,
“Self-Organizing Particle Systems,” in Proceedings of the 26th IEEE International
Parallel and Distributed Processing Symposium (IPDPS), 2012, pp. 1272–1283.'
mla: Drees, Maximilian, et al. “Self-Organizing Particle Systems.” Proceedings
of the 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS),
2012, pp. 1272–83, doi:10.1109/IPDPS.2012.116.
short: 'M. Drees, M. Hüllmann (married name: Eikel), A. Koutsopoulos, C. Scheideler,
in: Proceedings of the 26th IEEE International Parallel and Distributed Processing
Symposium (IPDPS), 2012, pp. 1272–1283.'
date_created: 2017-10-17T12:42:45Z
date_updated: 2022-01-06T07:02:42Z
ddc:
- '040'
department:
- _id: '79'
- _id: '63'
doi: 10.1109/IPDPS.2012.116
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T08:39:33Z
date_updated: 2018-03-15T08:39:33Z
file_id: '1263'
file_name: 581-IPDPS2012-Scheideler_Huellmann.pdf
file_size: 373131
relation: main_file
success: 1
file_date_updated: 2018-03-15T08:39:33Z
has_accepted_license: '1'
language:
- iso: eng
page: 1272-1283
project:
- _id: '1'
name: SFB 901
- _id: '13'
name: SFB 901 - Subprojekt C1
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the 26th IEEE International Parallel and Distributed Processing
Symposium (IPDPS)
status: public
title: Self-Organizing Particle Systems
type: conference
user_id: '14955'
year: '2012'
...
---
_id: '601'
abstract:
- lang: eng
text: Wir betrachten eine Gruppe von mobilen, autonomen Robotern in einem ebenen
Gel{\"a}nde. Es gibt keine zentrale Steuerung und die Roboter m{\"u}ssen sich
selbst koordinieren. Zentrale Herausforderung dabei ist, dass jeder Roboter nur
seine unmittelbare Nachbarschaft sieht und auch nur mit Robotern in seiner unmittelbaren
Nachbarschaft kommunizieren kann. Daraus ergeben sich viele algorithmische Fragestellungen.
In dieser Arbeit wird untersucht, unter welchen Voraussetzungen die Roboter sich
auf einem Punkt versammeln bzw. eine Linie zwischen zwei festen Stationen bilden
k{\"o}nnen. Daf{\"u}r werden mehrere Roboter-Strategien in verschiedenen Bewegungsmodellen
vorgestellt. Diese Strategien werden auf ihre Effizienz hin untersucht. Es werden
obere und untere Schranken f{\"u}r die ben{\"o}tigte Anzahl Runden und die Bewegungsdistanz
gezeigt. In einigen F{\"a}llen wird außerdem die ben{\"o}tigte Bewegungsdistanz
mit derjenigen Bewegungsdistanz verglichen, die eine optimale globale Strategie
auf der gleichen Instanz ben{\"o}tigen w{\"u}rde. So werden kompetititve Faktoren
hergeleitet.
author:
- first_name: Barbara
full_name: Kempkes, Barbara
last_name: Kempkes
citation:
ama: Kempkes B. Local Strategies for Robot Formation Problems. Vol 302. Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn; 2012.
apa: Kempkes, B. (2012). Local strategies for robot formation problems (Vol.
302). Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn.
bibtex: '@book{Kempkes_2012, series={Verlagsschriftenreihe des Heinz Nixdorf Instituts,
Paderborn}, title={Local strategies for robot formation problems}, volume={302},
publisher={Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}, author={Kempkes,
Barbara}, year={2012}, collection={Verlagsschriftenreihe des Heinz Nixdorf Instituts,
Paderborn} }'
chicago: Kempkes, Barbara. Local Strategies for Robot Formation Problems.
Vol. 302. Verlagsschriftenreihe Des Heinz Nixdorf Instituts, Paderborn. Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn, 2012.
ieee: B. Kempkes, Local strategies for robot formation problems, vol. 302.
Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2012.
mla: Kempkes, Barbara. Local Strategies for Robot Formation Problems. Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn, 2012.
short: B. Kempkes, Local Strategies for Robot Formation Problems, Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn, 2012.
date_created: 2017-10-17T12:42:49Z
date_updated: 2022-01-06T07:02:50Z
ddc:
- '040'
department:
- _id: '63'
- _id: '26'
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T08:16:44Z
date_updated: 2018-03-15T08:16:44Z
file_id: '1252'
file_name: 601-Kempkes-PhD.pdf
file_size: 3805310
relation: main_file
success: 1
file_date_updated: 2018-03-15T08:16:44Z
has_accepted_license: '1'
intvolume: ' 302'
language:
- iso: eng
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '2'
name: SFB 901 - Project Area A
publication_identifier:
isbn:
- 978-3-942647-21-2
publisher: Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn
series_title: Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn
status: public
supervisor:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
title: Local strategies for robot formation problems
type: dissertation
user_id: '5786'
volume: 302
year: '2012'
...
---
_id: '619'
abstract:
- lang: eng
text: 'Dynamics in networks is caused by a variety of reasons, like nodes moving
in 2D (or 3D) in multihop cellphone networks, joins and leaves in peer-to-peer
networks, evolution in social networks, and many others. In order to understand
such kinds of dynamics, and to design distributed algorithms that behave well
under dynamics, many ways to model dynamics are introduced and analyzed w.r.t.
correctness and eciency of distributed algorithms. In [16], Kuhn, Lynch, and Oshman
have introduced a very general, worst case type model of dynamics: The edge set
of the network may change arbitrarily from step to step, the only restriction
is that it is connected at all times and the set of nodes does not change. An
extended model demands that a xed connected subnetwork is maintained over each
time interval of length T (T-interval dynamics). They have presented, among others,
algorithms for counting the number of nodes under such general models of dynamics.In
this paper, we generalize their models and algorithms by adding random edge faults,
i.e., we consider fault-prone dynamic networks: We assume that an edge currently
existing may fail to transmit data with some probability p. We rst observe that
strong counting, i.e., each node knows the correct count and stops, is not possible
in a model with random edge faults. Our main two positive results are feasibility
and runtime bounds for weak counting, i.e., stopping is no longer required (but
still a correct count in each node), and for strong counting with an upper bound,
i.e., an upper bound N on n is known to all nodes.'
author:
- first_name: Philipp
full_name: Brandes, Philipp
last_name: Brandes
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Brandes P, Meyer auf der Heide F. Distributed Computing in Fault-Prone Dynamic
Networks. In: Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic
Distributed Systems (TADDS). ICPS. ; 2012:9-14. doi:10.1145/2414815.2414818'
apa: Brandes, P., & Meyer auf der Heide, F. (2012). Distributed Computing in
Fault-Prone Dynamic Networks. In Proceedings of the 4th Workshop on Theoretical
Aspects of Dynamic Distributed Systems (TADDS) (pp. 9–14). https://doi.org/10.1145/2414815.2414818
bibtex: '@inproceedings{Brandes_Meyer auf der Heide_2012, series={ICPS}, title={Distributed
Computing in Fault-Prone Dynamic Networks}, DOI={10.1145/2414815.2414818},
booktitle={Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic Distributed
Systems (TADDS)}, author={Brandes, Philipp and Meyer auf der Heide, Friedhelm},
year={2012}, pages={9–14}, collection={ICPS} }'
chicago: Brandes, Philipp, and Friedhelm Meyer auf der Heide. “Distributed Computing
in Fault-Prone Dynamic Networks.” In Proceedings of the 4th Workshop on Theoretical
Aspects of Dynamic Distributed Systems (TADDS), 9–14. ICPS, 2012. https://doi.org/10.1145/2414815.2414818.
ieee: P. Brandes and F. Meyer auf der Heide, “Distributed Computing in Fault-Prone
Dynamic Networks,” in Proceedings of the 4th Workshop on Theoretical Aspects
of Dynamic Distributed Systems (TADDS), 2012, pp. 9–14.
mla: Brandes, Philipp, and Friedhelm Meyer auf der Heide. “Distributed Computing
in Fault-Prone Dynamic Networks.” Proceedings of the 4th Workshop on Theoretical
Aspects of Dynamic Distributed Systems (TADDS), 2012, pp. 9–14, doi:10.1145/2414815.2414818.
short: 'P. Brandes, F. Meyer auf der Heide, in: Proceedings of the 4th Workshop
on Theoretical Aspects of Dynamic Distributed Systems (TADDS), 2012, pp. 9–14.'
date_created: 2017-10-17T12:42:52Z
date_updated: 2022-01-06T07:02:56Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1145/2414815.2414818
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T06:47:15Z
date_updated: 2018-03-15T06:47:15Z
file_id: '1244'
file_name: 619-Brandes_MadHTADDS12_01.pdf
file_size: 346044
relation: main_file
success: 1
file_date_updated: 2018-03-15T06:47:15Z
has_accepted_license: '1'
page: 9-14
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '2'
name: SFB 901 - Project Area A
publication: Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic Distributed
Systems (TADDS)
series_title: ICPS
status: public
title: Distributed Computing in Fault-Prone Dynamic Networks
type: conference
user_id: '15504'
year: '2012'
...
---
_id: '628'
abstract:
- lang: eng
text: Network creation games model the creation and usage costs of networks formed
by a set of selfish peers.Each peer has the ability to change the network in a
limited way, e.g., by creating or deleting incident links.In doing so, a peer
can reduce its individual communication cost.Typically, these costs are modeled
by the maximum or average distance in the network.We introduce a generalized version
of the basic network creation game (BNCG).In the BNCG (by Alon et al., SPAA 2010),
each peer may replace one of its incident links by a link to an arbitrary peer.This
is done in a selfish way in order to minimize either the maximum or average distance
to all other peers.That is, each peer works towards a network structure that allows
himself to communicate efficiently with all other peers.However, participants
of large networks are seldom interested in all peers.Rather, they want to communicate
efficiently with a small subset only.Our model incorporates these (communication)
interests explicitly.Given peers with interests and a communication network forming
a tree, we prove several results on the structure and quality of equilibria in
our model.We focus on the MAX-version, i.e., each node tries to minimize the maximum
distance to nodes it is interested in, and give an upper bound of O(\sqrt(n))
for the private costs in an equilibrium of n peers.Moreover, we give an equilibrium
for a circular interest graph where a node has private cost Omega(\sqrt(n)), showing
that our bound is tight.This example can be extended such that we get a tight
bound of Theta(\sqrt(n)) for the price of anarchy.For the case of general networks
we show the price of anarchy to be Theta(n).Additionally, we prove an interesting
connection between a maximum independent set in the interest graph and the private
costs of the peers.
author:
- first_name: Andreas
full_name: Cord-Landwehr, Andreas
last_name: Cord-Landwehr
- first_name: Martina
full_name: 'Huellmann (married name: Eikel), Martina'
last_name: 'Huellmann (married name: Eikel)'
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Alexander
full_name: Setzer, Alexander
id: '11108'
last_name: Setzer
citation:
ama: 'Cord-Landwehr A, Huellmann (married name: Eikel) M, Kling P, Setzer A. Basic
Network Creation Games with Communication Interests. In: Proceedings of the
5th International Symposium on Algorithmic Game Theory (SAGT). LNCS. ; 2012:72--83.
doi:10.1007/978-3-642-33996-7_7'
apa: 'Cord-Landwehr, A., Huellmann (married name: Eikel), M., Kling, P., & Setzer,
A. (2012). Basic Network Creation Games with Communication Interests. In Proceedings
of the 5th International Symposium on Algorithmic Game Theory (SAGT) (pp.
72--83). https://doi.org/10.1007/978-3-642-33996-7_7'
bibtex: '@inproceedings{Cord-Landwehr_Huellmann (married name: Eikel)_Kling_Setzer_2012,
series={LNCS}, title={Basic Network Creation Games with Communication Interests},
DOI={10.1007/978-3-642-33996-7_7},
booktitle={Proceedings of the 5th International Symposium on Algorithmic Game
Theory (SAGT)}, author={Cord-Landwehr, Andreas and Huellmann (married name: Eikel),
Martina and Kling, Peter and Setzer, Alexander}, year={2012}, pages={72--83},
collection={LNCS} }'
chicago: 'Cord-Landwehr, Andreas, Martina Huellmann (married name: Eikel), Peter
Kling, and Alexander Setzer. “Basic Network Creation Games with Communication
Interests.” In Proceedings of the 5th International Symposium on Algorithmic
Game Theory (SAGT), 72--83. LNCS, 2012. https://doi.org/10.1007/978-3-642-33996-7_7.'
ieee: 'A. Cord-Landwehr, M. Huellmann (married name: Eikel), P. Kling, and A. Setzer,
“Basic Network Creation Games with Communication Interests,” in Proceedings
of the 5th International Symposium on Algorithmic Game Theory (SAGT), 2012,
pp. 72--83.'
mla: Cord-Landwehr, Andreas, et al. “Basic Network Creation Games with Communication
Interests.” Proceedings of the 5th International Symposium on Algorithmic Game
Theory (SAGT), 2012, pp. 72--83, doi:10.1007/978-3-642-33996-7_7.
short: 'A. Cord-Landwehr, M. Huellmann (married name: Eikel), P. Kling, A. Setzer,
in: Proceedings of the 5th International Symposium on Algorithmic Game Theory
(SAGT), 2012, pp. 72--83.'
date_created: 2017-10-17T12:42:54Z
date_updated: 2022-01-06T07:02:59Z
ddc:
- '040'
department:
- _id: '79'
- _id: '63'
doi: 10.1007/978-3-642-33996-7_7
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T06:42:01Z
date_updated: 2018-03-15T06:42:01Z
file_id: '1238'
file_name: 628-FULL_paper_bncs_with_interests.pdf
file_size: 300591
relation: main_file
success: 1
file_date_updated: 2018-03-15T06:42:01Z
has_accepted_license: '1'
language:
- iso: eng
page: 72--83
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '2'
name: SFB 901 - Project Area A
publication: Proceedings of the 5th International Symposium on Algorithmic Game Theory
(SAGT)
series_title: LNCS
status: public
title: Basic Network Creation Games with Communication Interests
type: conference
user_id: '477'
year: '2012'
...
---
_id: '636'
abstract:
- lang: eng
text: We consider an online facility location problem where clients arrive over
time and their demands have to be served by opening facilities and assigning the
clients to opened facilities. When opening a facility we must choose one of K
different lease types to use. A lease type k has a certain lease length lk. Opening
a facility i using lease type k causes a cost of f k i and ensures that i is open
for the next lk time steps. In addition to costs for opening facilities, we have
to take connection costs ci j into account when assigning a client j to facility
i. We develop and analyze the first online algorithm for this problem that has
a time-independent competitive factor.This variant of the online facility location
problem was introduced by Nagarajan and Williamson [7] and is strongly related
to both the online facility problem by Meyerson [5] and the parking permit problem
by Meyerson [6]. Nagarajan and Williamson gave a 3-approximation algorithm for
the offline problem and an O(Klogn)-competitive algorithm for the online variant.
Here, n denotes the total number of clients arriving over time. We extend their
result by removing the dependency on n (and thereby on the time). In general,
our algorithm is O(lmax log(lmax))-competitive. Here lmax denotes the maximum
lease length. Moreover, we prove that it is O(log2(lmax))-competitive for many
“natural” cases. Such cases include, for example, situations where the number
of clients arriving in each time step does not vary too much, or is non-increasing,
or is polynomially bounded in lmax.
author:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Peter
full_name: Pietrzyk, Peter
last_name: Pietrzyk
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
citation:
ama: 'Meyer auf der Heide F, Pietrzyk P, Kling P. An Algorithm for Facility Leasing.
In: Proceedings of the 19th International Colloquium on Structural Information
& Communication Complexity (SIROCCO). LNCS. ; 2012:61-72. doi:10.1007/978-3-642-31104-8_6'
apa: Meyer auf der Heide, F., Pietrzyk, P., & Kling, P. (2012). An Algorithm
for Facility Leasing. In Proceedings of the 19th International Colloquium on
Structural Information & Communication Complexity (SIROCCO) (pp. 61–72).
https://doi.org/10.1007/978-3-642-31104-8_6
bibtex: '@inproceedings{Meyer auf der Heide_Pietrzyk_Kling_2012, series={LNCS},
title={An Algorithm for Facility Leasing}, DOI={10.1007/978-3-642-31104-8_6},
booktitle={Proceedings of the 19th International Colloquium on Structural Information
& Communication Complexity (SIROCCO)}, author={Meyer auf der Heide, Friedhelm
and Pietrzyk, Peter and Kling, Peter}, year={2012}, pages={61–72}, collection={LNCS}
}'
chicago: Meyer auf der Heide, Friedhelm, Peter Pietrzyk, and Peter Kling. “An Algorithm
for Facility Leasing.” In Proceedings of the 19th International Colloquium
on Structural Information & Communication Complexity (SIROCCO), 61–72.
LNCS, 2012. https://doi.org/10.1007/978-3-642-31104-8_6.
ieee: F. Meyer auf der Heide, P. Pietrzyk, and P. Kling, “An Algorithm for Facility
Leasing,” in Proceedings of the 19th International Colloquium on Structural
Information & Communication Complexity (SIROCCO), 2012, pp. 61–72.
mla: Meyer auf der Heide, Friedhelm, et al. “An Algorithm for Facility Leasing.”
Proceedings of the 19th International Colloquium on Structural Information
& Communication Complexity (SIROCCO), 2012, pp. 61–72, doi:10.1007/978-3-642-31104-8_6.
short: 'F. Meyer auf der Heide, P. Pietrzyk, P. Kling, in: Proceedings of the 19th
International Colloquium on Structural Information & Communication Complexity
(SIROCCO), 2012, pp. 61–72.'
date_created: 2017-10-17T12:42:56Z
date_updated: 2022-01-06T07:03:02Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-642-31104-8_6
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-14T14:14:21Z
date_updated: 2018-03-14T14:14:21Z
file_id: '1232'
file_name: 636-Online_Facility_Location.pdf
file_size: 173049
relation: main_file
success: 1
file_date_updated: 2018-03-14T14:14:21Z
has_accepted_license: '1'
page: 61-72
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '2'
name: SFB 901 - Project Area A
publication: Proceedings of the 19th International Colloquium on Structural Information
& Communication Complexity (SIROCCO)
series_title: LNCS
status: public
title: An Algorithm for Facility Leasing
type: conference
user_id: '15504'
year: '2012'
...
---
_id: '638'
author:
- first_name: Fabian
full_name: Eidens, Fabian
id: '25078'
last_name: Eidens
citation:
ama: Eidens F. Adaptive Verbindungsstrategien in dynamischen Suchnetzwerken.
Universität Paderborn; 2012.
apa: Eidens, F. (2012). Adaptive Verbindungsstrategien in dynamischen Suchnetzwerken.
Universität Paderborn.
bibtex: '@book{Eidens_2012, title={Adaptive Verbindungsstrategien in dynamischen
Suchnetzwerken}, publisher={Universität Paderborn}, author={Eidens, Fabian}, year={2012}
}'
chicago: Eidens, Fabian. Adaptive Verbindungsstrategien in dynamischen Suchnetzwerken.
Universität Paderborn, 2012.
ieee: F. Eidens, Adaptive Verbindungsstrategien in dynamischen Suchnetzwerken.
Universität Paderborn, 2012.
mla: Eidens, Fabian. Adaptive Verbindungsstrategien in dynamischen Suchnetzwerken.
Universität Paderborn, 2012.
short: F. Eidens, Adaptive Verbindungsstrategien in dynamischen Suchnetzwerken,
Universität Paderborn, 2012.
date_created: 2017-10-17T12:42:56Z
date_updated: 2022-01-06T07:03:03Z
department:
- _id: '63'
language:
- iso: ger
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '2'
name: SFB 901 - Project Area A
publisher: Universität Paderborn
status: public
title: Adaptive Verbindungsstrategien in dynamischen Suchnetzwerken
type: bachelorsthesis
user_id: '477'
year: '2012'
...
---
_id: '16445'
author:
- first_name: Barbara
full_name: Kempkes, Barbara
last_name: Kempkes
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Kempkes B, Meyer auf der Heide F. Continuous Local Strategies for Robotic
Formation Problems. In: Experimental Algorithms. Berlin, Heidelberg; 2012.
doi:10.1007/978-3-642-30850-5_2'
apa: Kempkes, B., & Meyer auf der Heide, F. (2012). Continuous Local Strategies
for Robotic Formation Problems. In Experimental Algorithms. Berlin, Heidelberg.
https://doi.org/10.1007/978-3-642-30850-5_2
bibtex: '@inbook{Kempkes_Meyer auf der Heide_2012, place={Berlin, Heidelberg}, title={Continuous
Local Strategies for Robotic Formation Problems}, DOI={10.1007/978-3-642-30850-5_2},
booktitle={Experimental Algorithms}, author={Kempkes, Barbara and Meyer auf der
Heide, Friedhelm}, year={2012} }'
chicago: Kempkes, Barbara, and Friedhelm Meyer auf der Heide. “Continuous Local
Strategies for Robotic Formation Problems.” In Experimental Algorithms.
Berlin, Heidelberg, 2012. https://doi.org/10.1007/978-3-642-30850-5_2.
ieee: B. Kempkes and F. Meyer auf der Heide, “Continuous Local Strategies for Robotic
Formation Problems,” in Experimental Algorithms, Berlin, Heidelberg, 2012.
mla: Kempkes, Barbara, and Friedhelm Meyer auf der Heide. “Continuous Local Strategies
for Robotic Formation Problems.” Experimental Algorithms, 2012, doi:10.1007/978-3-642-30850-5_2.
short: 'B. Kempkes, F. Meyer auf der Heide, in: Experimental Algorithms, Berlin,
Heidelberg, 2012.'
date_created: 2020-04-07T06:41:18Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1007/978-3-642-30850-5_2
language:
- iso: eng
place: Berlin, Heidelberg
publication: Experimental Algorithms
publication_identifier:
isbn:
- '9783642308499'
- '9783642308505'
issn:
- 0302-9743
- 1611-3349
publication_status: published
status: public
title: Continuous Local Strategies for Robotic Formation Problems
type: book_chapter
user_id: '15415'
year: '2012'
...
---
_id: '16446'
author:
- first_name: Barbara
full_name: Kempkes, Barbara
last_name: Kempkes
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Kempkes B, Kling P, Meyer auf der Heide F. Optimal and competitive runtime
bounds for continuous, local gathering of mobile robots. In: Proceedinbgs of
the 24th ACM Symposium on Parallelism in Algorithms and Architectures - SPAA ’12.
; 2012. doi:10.1145/2312005.2312009'
apa: Kempkes, B., Kling, P., & Meyer auf der Heide, F. (2012). Optimal and competitive
runtime bounds for continuous, local gathering of mobile robots. In Proceedinbgs
of the 24th ACM symposium on Parallelism in algorithms and architectures - SPAA
’12. https://doi.org/10.1145/2312005.2312009
bibtex: '@inproceedings{Kempkes_Kling_Meyer auf der Heide_2012, title={Optimal and
competitive runtime bounds for continuous, local gathering of mobile robots},
DOI={10.1145/2312005.2312009},
booktitle={Proceedinbgs of the 24th ACM symposium on Parallelism in algorithms
and architectures - SPAA ’12}, author={Kempkes, Barbara and Kling, Peter and Meyer
auf der Heide, Friedhelm}, year={2012} }'
chicago: Kempkes, Barbara, Peter Kling, and Friedhelm Meyer auf der Heide. “Optimal
and Competitive Runtime Bounds for Continuous, Local Gathering of Mobile Robots.”
In Proceedinbgs of the 24th ACM Symposium on Parallelism in Algorithms and
Architectures - SPAA ’12, 2012. https://doi.org/10.1145/2312005.2312009.
ieee: B. Kempkes, P. Kling, and F. Meyer auf der Heide, “Optimal and competitive
runtime bounds for continuous, local gathering of mobile robots,” in Proceedinbgs
of the 24th ACM symposium on Parallelism in algorithms and architectures - SPAA
’12, 2012.
mla: Kempkes, Barbara, et al. “Optimal and Competitive Runtime Bounds for Continuous,
Local Gathering of Mobile Robots.” Proceedinbgs of the 24th ACM Symposium on
Parallelism in Algorithms and Architectures - SPAA ’12, 2012, doi:10.1145/2312005.2312009.
short: 'B. Kempkes, P. Kling, F. Meyer auf der Heide, in: Proceedinbgs of the 24th
ACM Symposium on Parallelism in Algorithms and Architectures - SPAA ’12, 2012.'
date_created: 2020-04-07T06:43:11Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1145/2312005.2312009
language:
- iso: eng
publication: Proceedinbgs of the 24th ACM symposium on Parallelism in algorithms and
architectures - SPAA '12
publication_identifier:
isbn:
- '9781450312134'
publication_status: published
status: public
title: Optimal and competitive runtime bounds for continuous, local gathering of mobile
robots
type: conference
user_id: '15415'
year: '2012'
...
---
_id: '16448'
author:
- first_name: Barbara
full_name: Kempkes, Barbara
last_name: Kempkes
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Kempkes B, Meyer auf der Heide F. Local, Self-organizing Strategies for Robotic
Formation Problems. In: Algorithms for Sensor Systems. Berlin, Heidelberg;
2012. doi:10.1007/978-3-642-28209-6_2'
apa: Kempkes, B., & Meyer auf der Heide, F. (2012). Local, Self-organizing Strategies
for Robotic Formation Problems. In Algorithms for Sensor Systems. Berlin,
Heidelberg. https://doi.org/10.1007/978-3-642-28209-6_2
bibtex: '@inbook{Kempkes_Meyer auf der Heide_2012, place={Berlin, Heidelberg}, title={Local,
Self-organizing Strategies for Robotic Formation Problems}, DOI={10.1007/978-3-642-28209-6_2},
booktitle={Algorithms for Sensor Systems}, author={Kempkes, Barbara and Meyer
auf der Heide, Friedhelm}, year={2012} }'
chicago: Kempkes, Barbara, and Friedhelm Meyer auf der Heide. “Local, Self-Organizing
Strategies for Robotic Formation Problems.” In Algorithms for Sensor Systems.
Berlin, Heidelberg, 2012. https://doi.org/10.1007/978-3-642-28209-6_2.
ieee: B. Kempkes and F. Meyer auf der Heide, “Local, Self-organizing Strategies
for Robotic Formation Problems,” in Algorithms for Sensor Systems, Berlin,
Heidelberg, 2012.
mla: Kempkes, Barbara, and Friedhelm Meyer auf der Heide. “Local, Self-Organizing
Strategies for Robotic Formation Problems.” Algorithms for Sensor Systems,
2012, doi:10.1007/978-3-642-28209-6_2.
short: 'B. Kempkes, F. Meyer auf der Heide, in: Algorithms for Sensor Systems, Berlin,
Heidelberg, 2012.'
date_created: 2020-04-07T06:51:14Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1007/978-3-642-28209-6_2
language:
- iso: eng
place: Berlin, Heidelberg
publication: Algorithms for Sensor Systems
publication_identifier:
isbn:
- '9783642282089'
- '9783642282096'
issn:
- 0302-9743
- 1611-3349
publication_status: published
status: public
title: Local, Self-organizing Strategies for Robotic Formation Problems
type: book_chapter
user_id: '15415'
year: '2012'
...