---
_id: '4375'
abstract:
- lang: eng
text: "We present a peer-to-peer network that supports the efficient processing
of orthogonal range queries $R=\\bigtimes_{i=1}^{d}[a_i,\\,b_i]$ in a $d$-dimensional
point space.\\\\\r\nThe network is the same for each dimension, namely a distance
halving network like the one introduced by Naor and Wieder (ACM TALG'07).\r\nWe
show how to execute such range queries using $\\mathcal{O}\\left(2^{d'}d\\,\\log
m + d\\,|R|\\right)$ hops (and the same number of messages) in total. Here $[m]^d$
is the ground set, $|R|$ is the size and $d'$ the dimension of the queried range.\r\nFurthermore,
if the peers form a distributed network, the query can be answered in $\\mathcal{O}\\left(d\\,\\log
m + d\\,\\sum_{i=1}^{d}(b_i-a_i+1)\\right)$ communication rounds.\r\nOur algorithms
are based on a mapping of the Hilbert Curve through $[m]^d$ to the peers."
author:
- first_name: Markus
full_name: Benter, Markus
last_name: Benter
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Alexander
full_name: Setzer, Alexander
id: '11108'
last_name: Setzer
- first_name: Jannik
full_name: Sundermeier, Jannik
id: '38705'
last_name: Sundermeier
citation:
ama: 'Benter M, Knollmann T, Meyer auf der Heide F, Setzer A, Sundermeier J. A Peer-to-Peer
based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension.
In: Proceedings of the 4th International Symposium on Algorithmic Aspects of
Cloud Computing (ALGOCLOUD). ; 2018. doi:10.1007/978-3-030-19759-9_4'
apa: Benter, M., Knollmann, T., Meyer auf der Heide, F., Setzer, A., & Sundermeier,
J. (2018). A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries
of arbitrary Dimension. In Proceedings of the 4th International Symposium on
Algorithmic Aspects of Cloud Computing (ALGOCLOUD). Helsinki. https://doi.org/10.1007/978-3-030-19759-9_4
bibtex: '@inproceedings{Benter_Knollmann_Meyer auf der Heide_Setzer_Sundermeier_2018,
title={A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries
of arbitrary Dimension}, DOI={10.1007/978-3-030-19759-9_4},
booktitle={Proceedings of the 4th International Symposium on Algorithmic Aspects
of Cloud Computing (ALGOCLOUD)}, author={Benter, Markus and Knollmann, Till and
Meyer auf der Heide, Friedhelm and Setzer, Alexander and Sundermeier, Jannik},
year={2018} }'
chicago: Benter, Markus, Till Knollmann, Friedhelm Meyer auf der Heide, Alexander
Setzer, and Jannik Sundermeier. “A Peer-to-Peer Based Cloud Storage Supporting
Orthogonal Range Queries of Arbitrary Dimension.” In Proceedings of the 4th
International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD),
2018. https://doi.org/10.1007/978-3-030-19759-9_4.
ieee: M. Benter, T. Knollmann, F. Meyer auf der Heide, A. Setzer, and J. Sundermeier,
“A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary
Dimension,” in Proceedings of the 4th International Symposium on Algorithmic
Aspects of Cloud Computing (ALGOCLOUD), Helsinki, 2018.
mla: Benter, Markus, et al. “A Peer-to-Peer Based Cloud Storage Supporting Orthogonal
Range Queries of Arbitrary Dimension.” Proceedings of the 4th International
Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD), 2018, doi:10.1007/978-3-030-19759-9_4.
short: 'M. Benter, T. Knollmann, F. Meyer auf der Heide, A. Setzer, J. Sundermeier,
in: Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud
Computing (ALGOCLOUD), 2018.'
conference:
end_date: 2018-08-21
location: Helsinki
name: 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)
start_date: 2018-08-20
date_created: 2018-09-11T05:26:59Z
date_updated: 2022-01-06T07:01:00Z
ddc:
- '000'
department:
- _id: '63'
- _id: '79'
doi: 10.1007/978-3-030-19759-9_4
file:
- access_level: closed
content_type: application/pdf
creator: tillk
date_created: 2018-11-27T10:03:33Z
date_updated: 2018-11-27T10:03:33Z
file_id: '5863'
file_name: A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries
of arbitrary Dimension.pdf
file_size: 1122875
relation: main_file
success: 1
file_date_updated: 2018-11-27T10:03:33Z
has_accepted_license: '1'
keyword:
- Distributed Storage
- Multi-Dimensional Range Queries
- Peer-to-Peer
- Hilbert Curve
language:
- iso: eng
project:
- _id: '1'
name: SFB 901
- _id: '2'
name: SFB 901 - Project Area A
- _id: '5'
name: SFB 901 - Subproject A1
publication: Proceedings of the 4th International Symposium on Algorithmic Aspects
of Cloud Computing (ALGOCLOUD)
status: public
title: A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary
Dimension
type: conference
user_id: '14955'
year: '2018'
...
---
_id: '16392'
author:
- first_name: Björn
full_name: Feldkord, Björn
id: '22704'
last_name: Feldkord
- first_name: Manuel
full_name: Malatyali, Manuel
last_name: Malatyali
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Feldkord B, Malatyali M, Meyer auf der Heide F. A Dynamic Distributed Data
Structure for Top-k and k-Select Queries. In: Progress in Pattern Recognition,
Image Analysis, Computer Vision, and Applications. Cham; 2018. doi:10.1007/978-3-319-98355-4_18'
apa: Feldkord, B., Malatyali, M., & Meyer auf der Heide, F. (2018). A Dynamic
Distributed Data Structure for Top-k and k-Select Queries. In Progress in Pattern
Recognition, Image Analysis, Computer Vision, and Applications. Cham. https://doi.org/10.1007/978-3-319-98355-4_18
bibtex: '@inbook{Feldkord_Malatyali_Meyer auf der Heide_2018, place={Cham}, title={A
Dynamic Distributed Data Structure for Top-k and k-Select Queries}, DOI={10.1007/978-3-319-98355-4_18},
booktitle={Progress in Pattern Recognition, Image Analysis, Computer Vision, and
Applications}, author={Feldkord, Björn and Malatyali, Manuel and Meyer auf der
Heide, Friedhelm}, year={2018} }'
chicago: Feldkord, Björn, Manuel Malatyali, and Friedhelm Meyer auf der Heide. “A
Dynamic Distributed Data Structure for Top-k and k-Select Queries.” In Progress
in Pattern Recognition, Image Analysis, Computer Vision, and Applications.
Cham, 2018. https://doi.org/10.1007/978-3-319-98355-4_18.
ieee: B. Feldkord, M. Malatyali, and F. Meyer auf der Heide, “A Dynamic Distributed
Data Structure for Top-k and k-Select Queries,” in Progress in Pattern Recognition,
Image Analysis, Computer Vision, and Applications, Cham, 2018.
mla: Feldkord, Björn, et al. “A Dynamic Distributed Data Structure for Top-k and
k-Select Queries.” Progress in Pattern Recognition, Image Analysis, Computer
Vision, and Applications, 2018, doi:10.1007/978-3-319-98355-4_18.
short: 'B. Feldkord, M. Malatyali, F. Meyer auf der Heide, in: Progress in Pattern
Recognition, Image Analysis, Computer Vision, and Applications, Cham, 2018.'
date_created: 2020-04-03T07:04:59Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1007/978-3-319-98355-4_18
language:
- iso: eng
place: Cham
publication: Progress in Pattern Recognition, Image Analysis, Computer Vision, and
Applications
publication_identifier:
isbn:
- '9783319125671'
- '9783319125688'
issn:
- 0302-9743
- 1611-3349
publication_status: published
status: public
title: A Dynamic Distributed Data Structure for Top-k and k-Select Queries
type: book_chapter
user_id: '15415'
year: '2018'
...
---
_id: '28231'
author:
- first_name: Eric
full_name: Bodden, Eric
id: '59256'
last_name: Bodden
orcid: 0000-0003-3470-3647
- first_name: Falko
full_name: Dressler, Falko
id: '48097'
last_name: Dressler
orcid: 0000-0002-1989-1750
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Christoph
full_name: Scheytt, Christoph
id: '37144'
last_name: Scheytt
- first_name: Ansgar
full_name: Trächtler, Ansgar
id: '552'
last_name: Trächtler
citation:
ama: Bodden E, Dressler F, Meyer auf der Heide F, Scheytt C, Trächtler A. Intelligente
technische Systeme. Vol 369. Verlagsschriftenreihe des Heinz Nixdorf Instituts,
Paderborn; 2017.
apa: Bodden, E., Dressler, F., Meyer auf der Heide, F., Scheytt, C., & Trächtler,
A. (2017). Intelligente technische Systeme (Vol. 369). Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn.
bibtex: '@book{Bodden_Dressler_Meyer auf der Heide_Scheytt_Trächtler_2017, series={Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn}, title={Intelligente technische Systeme},
volume={369}, publisher={Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn},
author={Bodden, Eric and Dressler, Falko and Meyer auf der Heide, Friedhelm and
Scheytt, Christoph and Trächtler, Ansgar}, year={2017}, collection={Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn} }'
chicago: Bodden, Eric, Falko Dressler, Friedhelm Meyer auf der Heide, Christoph
Scheytt, and Ansgar Trächtler. Intelligente technische Systeme. Vol. 369.
Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn. Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn, 2017.
ieee: E. Bodden, F. Dressler, F. Meyer auf der Heide, C. Scheytt, and A. Trächtler,
Intelligente technische Systeme, vol. 369. Verlagsschriftenreihe des Heinz
Nixdorf Instituts, Paderborn, 2017.
mla: Bodden, Eric, et al. Intelligente technische Systeme. Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn, 2017.
short: E. Bodden, F. Dressler, F. Meyer auf der Heide, C. Scheytt, A. Trächtler,
Intelligente technische Systeme, Verlagsschriftenreihe des Heinz Nixdorf Instituts,
Paderborn, 2017.
date_created: 2021-12-02T11:53:20Z
date_updated: 2022-01-06T06:57:53Z
department:
- _id: '26'
intvolume: ' 369'
language:
- iso: ger
publication_identifier:
isbn:
- 978-3-942647-88-5
publication_status: published
publisher: Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn
series_title: Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn
status: public
title: Intelligente technische Systeme
type: misc
user_id: '60046'
volume: 369
year: '2017'
...
---
_id: '24221'
abstract:
- lang: ger
text: Das Wissenschaftsforum Intelligente Technische Systeme (WInTeSys) legt am
11. und 12. Mai 2017 in Paderborn den Schwerpunkt auf die Grundlagen und die Entwicklung
intelligenter technischer Systeme im Kontext Industrie 4.0. Etwa 40 begutachtete
hochkarätige Beiträge geben einen Überblick über Forschungsfelder, Technologien
und Anwendungen. Die Veranstaltung bietet den Teilnehmerinnen und Teilnehmern
eine ausgezeichnete Bühne für den Erfahrungsaustausch auf dem Weg in die Digitalisierung
von Produkten und Produktionssystemen. »Das Besondere ist der Dialog von Hochschulforschung
und industrieller Entwicklung, also das Aufeinandertreffen von »Science-Push«
und »Application-Pull«. Die Beiträge spiegeln die hervorragende Vernetzung in
der Region OWL und darüber hinaus wider«, sagt Veranstalter Prof. Jürgen Gausemeier
(Heinz Nixdorf Institut, Universität Paderborn).
author:
- first_name: Jürgen
full_name: Gausemeier, Jürgen
last_name: Gausemeier
- first_name: Eric
full_name: Bodden, Eric
id: '59256'
last_name: Bodden
orcid: 0000-0003-3470-3647
- first_name: Falko
full_name: Dressler, Falko
id: '48097'
last_name: Dressler
orcid: 0000-0002-1989-1750
- first_name: Roman
full_name: Dumitrescu, Roman
id: '16190'
last_name: Dumitrescu
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Christoph
full_name: Scheytt, Christoph
id: '37144'
last_name: Scheytt
- first_name: Ansgar
full_name: Trächtler, Ansgar
id: '552'
last_name: Trächtler
citation:
ama: Gausemeier J, Bodden E, Dressler F, et al. Wissenschaftsforum Intelligente
Technische Systeme (WInTeSys). Vol 369. Verlagsschriftenreihe des Heinz Nixdorf
Instituts, Paderborn; 2017. doi:10.17619/UNIPB/1-93
apa: Gausemeier, J., Bodden, E., Dressler, F., Dumitrescu, R., Meyer auf der Heide,
F., Scheytt, C., & Trächtler, A. (2017). Wissenschaftsforum Intelligente
Technische Systeme (WInTeSys) (Vol. 369). Verlagsschriftenreihe des Heinz
Nixdorf Instituts, Paderborn. https://doi.org/10.17619/UNIPB/1-93
bibtex: '@book{Gausemeier_Bodden_Dressler_Dumitrescu_Meyer auf der Heide_Scheytt_Trächtler_2017,
series={369}, title={Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)},
volume={369}, DOI={10.17619/UNIPB/1-93},
publisher={Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}, author={Gausemeier,
Jürgen and Bodden, Eric and Dressler, Falko and Dumitrescu, Roman and Meyer auf
der Heide, Friedhelm and Scheytt, Christoph and Trächtler, Ansgar}, year={2017},
collection={369} }'
chicago: Gausemeier, Jürgen, Eric Bodden, Falko Dressler, Roman Dumitrescu, Friedhelm
Meyer auf der Heide, Christoph Scheytt, and Ansgar Trächtler. Wissenschaftsforum
Intelligente Technische Systeme (WInTeSys). Vol. 369. 369. Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn, 2017. https://doi.org/10.17619/UNIPB/1-93.
ieee: J. Gausemeier et al., Wissenschaftsforum Intelligente Technische
Systeme (WInTeSys), vol. 369. Verlagsschriftenreihe des Heinz Nixdorf Instituts,
Paderborn, 2017.
mla: Gausemeier, Jürgen, et al. Wissenschaftsforum Intelligente Technische Systeme
(WInTeSys). Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn,
2017, doi:10.17619/UNIPB/1-93.
short: J. Gausemeier, E. Bodden, F. Dressler, R. Dumitrescu, F. Meyer auf der Heide,
C. Scheytt, A. Trächtler, Wissenschaftsforum Intelligente Technische Systeme (WInTeSys),
Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2017.
date_created: 2021-09-13T08:20:36Z
date_updated: 2022-01-06T06:56:13Z
department:
- _id: '58'
doi: 10.17619/UNIPB/1-93
intvolume: ' 369'
language:
- iso: ger
publication_identifier:
isbn:
- 978-3-942647-88-5
publication_status: published
publisher: Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn
related_material:
link:
- relation: confirmation
url: https://digital.ub.uni-paderborn.de/hs/content/titleinfo/2436759
series_title: '369'
status: public
title: Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)
type: book
user_id: '15931'
volume: 369
year: '2017'
...
---
_id: '27415'
citation:
ama: Gausemeier J, Bodden E, Dressler F, et al., eds. Wissenschaftsforum Intelligente
Technische Systeme (WInTeSys). , Band 369. Vol 369. Verlagsschriftenreihe
des Heinz Nixdorf Instituts; 2017.
apa: Gausemeier, J., Bodden, E., Dressler, F., Dumitrescu, R., Meyer auf der Heide,
F., Scheytt, C., & Trächtler, A. (Eds.). (2017). Wissenschaftsforum Intelligente
Technische Systeme (WInTeSys). , Band 369 (Vol. 369). Verlagsschriftenreihe
des Heinz Nixdorf Instituts.
bibtex: '@book{Gausemeier_Bodden_Dressler_Dumitrescu_Meyer auf der Heide_Scheytt_Trächtler_2017,
place={Paderborn}, title={Wissenschaftsforum Intelligente Technische Systeme (WInTeSys).
, Band 369}, volume={369}, publisher={Verlagsschriftenreihe des Heinz Nixdorf
Instituts}, year={2017} }'
chicago: 'Gausemeier, Jürgen, Eric Bodden, Falko Dressler, Roman Dumitrescu, Friedhelm
Meyer auf der Heide, Christoph Scheytt, and Ansgar Trächtler, eds. Wissenschaftsforum
Intelligente Technische Systeme (WInTeSys). , Band 369. Vol. 369. Paderborn:
Verlagsschriftenreihe des Heinz Nixdorf Instituts, 2017.'
ieee: 'J. Gausemeier et al., Eds., Wissenschaftsforum Intelligente Technische
Systeme (WInTeSys). , Band 369, vol. 369. Paderborn: Verlagsschriftenreihe
des Heinz Nixdorf Instituts, 2017.'
mla: Gausemeier, Jürgen, et al., editors. Wissenschaftsforum Intelligente Technische
Systeme (WInTeSys). , Band 369. Verlagsschriftenreihe des Heinz Nixdorf Instituts,
2017.
short: J. Gausemeier, E. Bodden, F. Dressler, R. Dumitrescu, F. Meyer auf der Heide,
C. Scheytt, A. Trächtler, eds., Wissenschaftsforum Intelligente Technische Systeme
(WInTeSys). , Band 369, Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn,
2017.
date_created: 2021-11-15T08:34:31Z
date_updated: 2022-01-06T06:57:39Z
department:
- _id: '676'
editor:
- first_name: Jürgen
full_name: Gausemeier, Jürgen
last_name: Gausemeier
- first_name: Eric
full_name: Bodden, Eric
id: '59256'
last_name: Bodden
orcid: 0000-0003-3470-3647
- first_name: Falko
full_name: Dressler, Falko
id: '48097'
last_name: Dressler
orcid: 0000-0002-1989-1750
- first_name: Roman
full_name: Dumitrescu, Roman
id: '16190'
last_name: Dumitrescu
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Christoph
full_name: Scheytt, Christoph
id: '37144'
last_name: Scheytt
- first_name: Ansgar
full_name: Trächtler, Ansgar
id: '552'
last_name: Trächtler
intvolume: ' 369'
language:
- iso: ger
place: Paderborn
publisher: Verlagsschriftenreihe des Heinz Nixdorf Instituts
status: public
title: Wissenschaftsforum Intelligente Technische Systeme (WInTeSys). , Band 369
type: book_editor
user_id: '21240'
volume: 369
year: '2017'
...
---
_id: '17811'
abstract:
- lang: eng
text: "We consider a swarm of $n$ autonomous mobile robots, distributed on a\r\n2-dimensional
grid. A basic task for such a swarm is the gathering process: All\r\nrobots have
to gather at one (not predefined) place. A common local model for\r\nextremely
simple robots is the following: The robots do not have a common\r\ncompass, only
have a constant viewing radius, are autonomous and\r\nindistinguishable, can move
at most a constant distance in each step, cannot\r\ncommunicate, are oblivious
and do not have flags or states. The only gathering\r\nalgorithm under this robot
model, with known runtime bounds, needs\r\n$\\mathcal{O}(n^2)$ rounds and works
in the Euclidean plane. The underlying time\r\nmodel for the algorithm is the
fully synchronous $\\mathcal{FSYNC}$ model. On\r\nthe other side, in the case
of the 2-dimensional grid, the only known gathering\r\nalgorithms for the same
time and a similar local model additionally require a\r\nconstant memory, states
and \"flags\" to communicate these states to neighbors in\r\nviewing range. They
gather in time $\\mathcal{O}(n)$.\r\n In this paper we contribute the (to the
best of our knowledge) first\r\ngathering algorithm on the grid that works under
the same simple local model as\r\nthe above mentioned Euclidean plane strategy,
i.e., without memory (oblivious),\r\n\"flags\" and states. We prove its correctness
and an $\\mathcal{O}(n^2)$ time\r\nbound in the fully synchronous $\\mathcal{FSYNC}$
time model. This time bound\r\nmatches the time bound of the best known algorithm
for the Euclidean plane\r\nmentioned above. We say gathering is done if all robots
are located within a\r\n$2\\times 2$ square, because in $\\mathcal{FSYNC}$ such
configurations cannot be\r\nsolved."
author:
- first_name: Matthias
full_name: Fischer, Matthias
id: '146'
last_name: Fischer
- first_name: Daniel
full_name: Jung, Daniel
id: '37827'
last_name: Jung
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: Fischer M, Jung D, Meyer auf der Heide F. Gathering Anonymous, Oblivious Robots
on a Grid. arXiv:170203400. 2017.
apa: Fischer, M., Jung, D., & Meyer auf der Heide, F. (2017). Gathering Anonymous,
Oblivious Robots on a Grid. ArXiv:1702.03400.
bibtex: '@article{Fischer_Jung_Meyer auf der Heide_2017, title={Gathering Anonymous,
Oblivious Robots on a Grid}, journal={arXiv:1702.03400}, author={Fischer, Matthias
and Jung, Daniel and Meyer auf der Heide, Friedhelm}, year={2017} }'
chicago: Fischer, Matthias, Daniel Jung, and Friedhelm Meyer auf der Heide. “Gathering
Anonymous, Oblivious Robots on a Grid.” ArXiv:1702.03400, 2017.
ieee: M. Fischer, D. Jung, and F. Meyer auf der Heide, “Gathering Anonymous, Oblivious
Robots on a Grid,” arXiv:1702.03400. 2017.
mla: Fischer, Matthias, et al. “Gathering Anonymous, Oblivious Robots on a Grid.”
ArXiv:1702.03400, 2017.
short: M. Fischer, D. Jung, F. Meyer auf der Heide, ArXiv:1702.03400 (2017).
date_created: 2020-08-11T13:48:38Z
date_updated: 2022-01-06T06:53:20Z
department:
- _id: '63'
language:
- iso: eng
publication: arXiv:1702.03400
status: public
title: Gathering Anonymous, Oblivious Robots on a Grid
type: preprint
user_id: '15415'
year: '2017'
...
---
_id: '23010'
author:
- first_name: Jürgen
full_name: Gausemeier, Jürgen
last_name: Gausemeier
- first_name: Eric
full_name: Bodden, Eric
id: '59256'
last_name: Bodden
orcid: 0000-0003-3470-3647
- first_name: Falko
full_name: Dressler, Falko
id: '48097'
last_name: Dressler
orcid: 0000-0002-1989-1750
- first_name: Roman
full_name: Dumitrescu, Roman
id: '16190'
last_name: Dumitrescu
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Christoph
full_name: Scheytt, Christoph
last_name: Scheytt
- first_name: Ansgar
full_name: Trächtler, Ansgar
id: '552'
last_name: Trächtler
citation:
ama: Gausemeier J, Bodden E, Dressler F, et al. Wissenschaftsforum Intelligente
Technische Systeme (WInTeSys). Vol 369. Verlagsschriftenreihe des Heinz Nixdorf
Instituts, Paderborn; 2017.
apa: Gausemeier, J., Bodden, E., Dressler, F., Dumitrescu, R., Meyer auf der Heide,
F., Scheytt, C., & Trächtler, A. (2017). Wissenschaftsforum Intelligente
Technische Systeme (WInTeSys) (Vol. 369). Verlagsschriftenreihe des Heinz
Nixdorf Instituts, Paderborn.
bibtex: '@book{Gausemeier_Bodden_Dressler_Dumitrescu_Meyer auf der Heide_Scheytt_Trächtler_2017,
title={Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)}, volume={369},
publisher={Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}, author={Gausemeier,
Jürgen and Bodden, Eric and Dressler, Falko and Dumitrescu, Roman and Meyer auf
der Heide, Friedhelm and Scheytt, Christoph and Trächtler, Ansgar}, year={2017}
}'
chicago: Gausemeier, Jürgen, Eric Bodden, Falko Dressler, Roman Dumitrescu, Friedhelm
Meyer auf der Heide, Christoph Scheytt, and Ansgar Trächtler. Wissenschaftsforum
Intelligente Technische Systeme (WInTeSys). Vol. 369. Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn, 2017.
ieee: J. Gausemeier et al., Wissenschaftsforum Intelligente Technische
Systeme (WInTeSys), vol. 369. Verlagsschriftenreihe des Heinz Nixdorf Instituts,
Paderborn, 2017.
mla: Gausemeier, Jürgen, et al. Wissenschaftsforum Intelligente Technische Systeme
(WInTeSys). Vol. 369, Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn,
2017.
short: J. Gausemeier, E. Bodden, F. Dressler, R. Dumitrescu, F. Meyer auf der Heide,
C. Scheytt, A. Trächtler, Wissenschaftsforum Intelligente Technische Systeme (WInTeSys),
Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2017.
date_created: 2021-08-09T05:50:16Z
date_updated: 2022-01-06T06:55:45Z
department:
- _id: '153'
intvolume: ' 369'
language:
- iso: eng
publisher: Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn
status: public
title: Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)
type: book
user_id: '24876'
volume: 369
year: '2017'
...
---
_id: '79'
abstract:
- lang: eng
text: Consider a problem in which $n$ jobs that are classified into $k$ types arrive
over time at their release times and are to be scheduled on a single machine so
as to minimize the maximum flow time.The machine requires a setup taking $s$ time
units whenever it switches from processing jobs of one type to jobs of a different
type.We consider the problem as an online problem where each job is only known
to the scheduler as soon as it arrives and where the processing time of a job
only becomes known upon its completion (non-clairvoyance).We are interested in
the potential of simple ``greedy-like'' algorithms.We analyze a modification of
the FIFO strategy and show its competitiveness to be $\Theta(\sqrt{n})$, which
is optimal for the considered class of algorithms.For $k=2$ types it achieves
a constant competitiveness.Our main insight is obtained by an analysis of the
smoothed competitiveness.If processing times $p_j$ are independently perturbed
to $\hat p_j = (1+X_j)p_j$, we obtain a competitiveness of $O(\sigma^{-2} \log^2
n)$ when $X_j$ is drawn from a uniform or a (truncated) normal distribution with
standard deviation $\sigma$.The result proves that bad instances are fragile and
``practically'' one might expect a much better performance than given by the $\Omega(\sqrt{n})$-bound.
author:
- first_name: Alexander
full_name: Mäcker, Alexander
id: '13536'
last_name: Mäcker
- first_name: Manuel
full_name: Malatyali, Manuel
last_name: Malatyali
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Sören
full_name: Riechers, Sören
last_name: Riechers
citation:
ama: 'Mäcker A, Malatyali M, Meyer auf der Heide F, Riechers S. Non-Clairvoyant
Scheduling to Minimize Max Flow Time on a Machine with Setup Times. In: Proceedings
of the 15th Workshop on Approximation and Online Algorithms (WAOA). Vol 10787.
Lecture Notes in Computer Science. Springer; 2017:207-222. doi:10.1007/978-3-319-89441-6'
apa: Mäcker, A., Malatyali, M., Meyer auf der Heide, F., & Riechers, S. (2017).
Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times.
In Proceedings of the 15th Workshop on Approximation and Online Algorithms
(WAOA) (Vol. 10787, pp. 207–222). Springer. https://doi.org/10.1007/978-3-319-89441-6
bibtex: '@inproceedings{Mäcker_Malatyali_Meyer auf der Heide_Riechers_2017, series={Lecture
Notes in Computer Science}, title={Non-Clairvoyant Scheduling to Minimize Max
Flow Time on a Machine with Setup Times}, volume={10787}, DOI={10.1007/978-3-319-89441-6},
booktitle={Proceedings of the 15th Workshop on Approximation and Online Algorithms
(WAOA)}, publisher={Springer}, author={Mäcker, Alexander and Malatyali, Manuel
and Meyer auf der Heide, Friedhelm and Riechers, Sören}, year={2017}, pages={207–222},
collection={Lecture Notes in Computer Science} }'
chicago: Mäcker, Alexander, Manuel Malatyali, Friedhelm Meyer auf der Heide, and
Sören Riechers. “Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine
with Setup Times.” In Proceedings of the 15th Workshop on Approximation and
Online Algorithms (WAOA), 10787:207–22. Lecture Notes in Computer Science.
Springer, 2017. https://doi.org/10.1007/978-3-319-89441-6.
ieee: A. Mäcker, M. Malatyali, F. Meyer auf der Heide, and S. Riechers, “Non-Clairvoyant
Scheduling to Minimize Max Flow Time on a Machine with Setup Times,” in Proceedings
of the 15th Workshop on Approximation and Online Algorithms (WAOA), 2017,
vol. 10787, pp. 207–222.
mla: Mäcker, Alexander, et al. “Non-Clairvoyant Scheduling to Minimize Max Flow
Time on a Machine with Setup Times.” Proceedings of the 15th Workshop on Approximation
and Online Algorithms (WAOA), vol. 10787, Springer, 2017, pp. 207–22, doi:10.1007/978-3-319-89441-6.
short: 'A. Mäcker, M. Malatyali, F. Meyer auf der Heide, S. Riechers, in: Proceedings
of the 15th Workshop on Approximation and Online Algorithms (WAOA), Springer,
2017, pp. 207–222.'
date_created: 2017-10-17T12:41:06Z
date_updated: 2022-01-06T07:03:47Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1007/978-3-319-89441-6
file:
- access_level: closed
content_type: application/pdf
creator: ups
date_created: 2018-11-02T14:59:22Z
date_updated: 2018-11-02T14:59:22Z
file_id: '5289'
file_name: Non-clairvoyantSchedulingToMin.pdf
file_size: 380629
relation: main_file
success: 1
file_date_updated: 2018-11-02T14:59:22Z
has_accepted_license: '1'
intvolume: ' 10787'
language:
- iso: eng
page: 207-222
project:
- _id: '1'
name: SFB 901
- _id: '16'
name: SFB 901 - Subprojekt C4
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the 15th Workshop on Approximation and Online Algorithms
(WAOA)
publisher: Springer
series_title: Lecture Notes in Computer Science
status: public
title: Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup
Times
type: conference
user_id: '477'
volume: 10787
year: '2017'
...
---
_id: '82'
abstract:
- lang: eng
text: Many graph problems such as maximum cut, chromatic number, hamiltonian cycle,
and edge dominating set are known to be fixed-parameter tractable (FPT) when parameterized
by the treewidth of the input graphs, but become W-hard with respect to the clique-width
parameter. Recently, Gajarský et al. proposed a new parameter called modular-width
using the notion of modular decomposition of graphs. They showed that the chromatic
number problem and the partitioning into paths problem, and hence hamiltonian
path and hamiltonian cycle, are FPT when parameterized by this parameter. In this
paper, we study modular-width in parameterized parallel complexity and show that
the weighted maximum clique problem and the maximum matching problem are fixed-parameter
parallel-tractable (FPPT) when parameterized by this parameter.
author:
- first_name: Faisal N.
full_name: Abu-Khzam, Faisal N.
last_name: Abu-Khzam
- first_name: Shouwei
full_name: Li, Shouwei
last_name: Li
- first_name: Christine
full_name: Markarian, Christine
id: '37612'
last_name: Markarian
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Pavel
full_name: Podlipyan, Pavel
last_name: Podlipyan
citation:
ama: 'Abu-Khzam FN, Li S, Markarian C, Meyer auf der Heide F, Podlipyan P. Modular-Width:
An Auxiliary Parameter for Parameterized Parallel Complexity. In: Proceedings
of the 11th International Workshop on Frontiers in Algorithmics (FAW). LNCS.
; 2017:139-150. doi:10.1007/978-3-319-59605-1_13'
apa: 'Abu-Khzam, F. N., Li, S., Markarian, C., Meyer auf der Heide, F., & Podlipyan,
P. (2017). Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity.
In Proceedings of the 11th International Workshop on Frontiers in Algorithmics
(FAW) (pp. 139–150). https://doi.org/10.1007/978-3-319-59605-1_13'
bibtex: '@inproceedings{Abu-Khzam_Li_Markarian_Meyer auf der Heide_Podlipyan_2017,
series={LNCS}, title={Modular-Width: An Auxiliary Parameter for Parameterized
Parallel Complexity}, DOI={10.1007/978-3-319-59605-1_13},
booktitle={Proceedings of the 11th International Workshop on Frontiers in Algorithmics
(FAW)}, author={Abu-Khzam, Faisal N. and Li, Shouwei and Markarian, Christine
and Meyer auf der Heide, Friedhelm and Podlipyan, Pavel}, year={2017}, pages={139–150},
collection={LNCS} }'
chicago: 'Abu-Khzam, Faisal N., Shouwei Li, Christine Markarian, Friedhelm Meyer
auf der Heide, and Pavel Podlipyan. “Modular-Width: An Auxiliary Parameter for
Parameterized Parallel Complexity.” In Proceedings of the 11th International
Workshop on Frontiers in Algorithmics (FAW), 139–50. LNCS, 2017. https://doi.org/10.1007/978-3-319-59605-1_13.'
ieee: 'F. N. Abu-Khzam, S. Li, C. Markarian, F. Meyer auf der Heide, and P. Podlipyan,
“Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity,”
in Proceedings of the 11th International Workshop on Frontiers in Algorithmics
(FAW), 2017, pp. 139–150.'
mla: 'Abu-Khzam, Faisal N., et al. “Modular-Width: An Auxiliary Parameter for Parameterized
Parallel Complexity.” Proceedings of the 11th International Workshop on Frontiers
in Algorithmics (FAW), 2017, pp. 139–50, doi:10.1007/978-3-319-59605-1_13.'
short: 'F.N. Abu-Khzam, S. Li, C. Markarian, F. Meyer auf der Heide, P. Podlipyan,
in: Proceedings of the 11th International Workshop on Frontiers in Algorithmics
(FAW), 2017, pp. 139–150.'
date_created: 2017-10-17T12:41:07Z
date_updated: 2022-01-06T07:03:52Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1007/978-3-319-59605-1_13
file:
- access_level: closed
content_type: application/pdf
creator: ups
date_created: 2018-11-02T15:07:35Z
date_updated: 2018-11-02T15:07:35Z
file_id: '5294'
file_name: Modular-WidthAnAuxiliaryParame.pdf
file_size: 238276
relation: main_file
success: 1
file_date_updated: 2018-11-02T15:07:35Z
has_accepted_license: '1'
language:
- iso: eng
page: 139-150
project:
- _id: '1'
name: SFB 901
- _id: '2'
name: SFB 901 - Project Area A
- _id: '5'
name: SFB 901 - Subproject A1
publication: Proceedings of the 11th International Workshop on Frontiers in Algorithmics
(FAW)
series_title: LNCS
status: public
title: 'Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity'
type: conference
user_id: '477'
year: '2017'
...
---
_id: '70'
author:
- first_name: Björn
full_name: Feldkord, Björn
id: '22704'
last_name: Feldkord
- first_name: Christine
full_name: Markarian, Christine
id: '37612'
last_name: Markarian
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Feldkord B, Markarian C, Meyer auf der Heide F. Price Fluctuations in Online
Leasing. In: Proceedings of the 11th Annual International Conference on Combinatorial
Optimization and Applications (COCOA). ; 2017:17-31. doi:10.1007/978-3-319-71147-8_2'
apa: Feldkord, B., Markarian, C., & Meyer auf der Heide, F. (2017). Price Fluctuations
in Online Leasing. In Proceedings of the 11th Annual International Conference
on Combinatorial Optimization and Applications (COCOA) (pp. 17–31). https://doi.org/10.1007/978-3-319-71147-8_2
bibtex: '@inproceedings{Feldkord_Markarian_Meyer auf der Heide_2017, title={Price
Fluctuations in Online Leasing}, DOI={10.1007/978-3-319-71147-8_2},
booktitle={Proceedings of the 11th Annual International Conference on Combinatorial
Optimization and Applications (COCOA)}, author={Feldkord, Björn and Markarian,
Christine and Meyer auf der Heide, Friedhelm}, year={2017}, pages={17–31} }'
chicago: Feldkord, Björn, Christine Markarian, and Friedhelm Meyer auf der Heide.
“Price Fluctuations in Online Leasing.” In Proceedings of the 11th Annual International
Conference on Combinatorial Optimization and Applications (COCOA), 17–31,
2017. https://doi.org/10.1007/978-3-319-71147-8_2.
ieee: B. Feldkord, C. Markarian, and F. Meyer auf der Heide, “Price Fluctuations
in Online Leasing,” in Proceedings of the 11th Annual International Conference
on Combinatorial Optimization and Applications (COCOA), 2017, pp. 17–31.
mla: Feldkord, Björn, et al. “Price Fluctuations in Online Leasing.” Proceedings
of the 11th Annual International Conference on Combinatorial Optimization and
Applications (COCOA), 2017, pp. 17–31, doi:10.1007/978-3-319-71147-8_2.
short: 'B. Feldkord, C. Markarian, F. Meyer auf der Heide, in: Proceedings of the
11th Annual International Conference on Combinatorial Optimization and Applications
(COCOA), 2017, pp. 17–31.'
date_created: 2017-10-17T12:41:05Z
date_updated: 2022-01-06T07:03:26Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1007/978-3-319-71147-8_2
file:
- access_level: closed
content_type: application/pdf
creator: ups
date_created: 2018-11-02T15:06:13Z
date_updated: 2018-11-02T15:06:13Z
file_id: '5293'
file_name: PriceFluctuationInOnlineLeasin.pdf
file_size: 287315
relation: main_file
success: 1
file_date_updated: 2018-11-02T15:06:13Z
has_accepted_license: '1'
language:
- iso: eng
page: 17 - 31
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 11th Annual International Conference on Combinatorial
Optimization and Applications (COCOA)
status: public
title: Price Fluctuations in Online Leasing
type: conference
user_id: '477'
year: '2017'
...
---
_id: '706'
author:
- first_name: Alexander
full_name: Mäcker, Alexander
id: '13536'
last_name: Mäcker
- first_name: Manuel
full_name: Malatyali, Manuel
last_name: Malatyali
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Sören
full_name: Riechers, Sören
last_name: Riechers
citation:
ama: Mäcker A, Malatyali M, Meyer auf der Heide F, Riechers S. Cost-efficient Scheduling
on Machines from the Cloud. Journal of Combinatorial Optimization. 2017;36(4):1168-1194.
doi:10.1007/s10878-017-0198-x
apa: Mäcker, A., Malatyali, M., Meyer auf der Heide, F., & Riechers, S. (2017).
Cost-efficient Scheduling on Machines from the Cloud. Journal of Combinatorial
Optimization, 36(4), 1168–1194. https://doi.org/10.1007/s10878-017-0198-x
bibtex: '@article{Mäcker_Malatyali_Meyer auf der Heide_Riechers_2017, title={Cost-efficient
Scheduling on Machines from the Cloud}, volume={36}, DOI={10.1007/s10878-017-0198-x},
number={4}, journal={Journal of Combinatorial Optimization}, publisher={Springer},
author={Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm
and Riechers, Sören}, year={2017}, pages={1168–1194} }'
chicago: 'Mäcker, Alexander, Manuel Malatyali, Friedhelm Meyer auf der Heide, and
Sören Riechers. “Cost-Efficient Scheduling on Machines from the Cloud.” Journal
of Combinatorial Optimization 36, no. 4 (2017): 1168–94. https://doi.org/10.1007/s10878-017-0198-x.'
ieee: A. Mäcker, M. Malatyali, F. Meyer auf der Heide, and S. Riechers, “Cost-efficient
Scheduling on Machines from the Cloud,” Journal of Combinatorial Optimization,
vol. 36, no. 4, pp. 1168–1194, 2017.
mla: Mäcker, Alexander, et al. “Cost-Efficient Scheduling on Machines from the Cloud.”
Journal of Combinatorial Optimization, vol. 36, no. 4, Springer, 2017,
pp. 1168–94, doi:10.1007/s10878-017-0198-x.
short: A. Mäcker, M. Malatyali, F. Meyer auf der Heide, S. Riechers, Journal of
Combinatorial Optimization 36 (2017) 1168–1194.
date_created: 2017-11-15T10:21:34Z
date_updated: 2022-01-06T07:03:27Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/s10878-017-0198-x
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-14T12:21:34Z
date_updated: 2018-03-14T12:21:34Z
file_id: '1210'
file_name: 706-chp_3A10.1007_2F978-3-319-48749-6_42.pdf
file_size: 608614
relation: main_file
success: 1
file_date_updated: 2018-03-14T12:21:34Z
has_accepted_license: '1'
intvolume: ' 36'
issue: '4'
language:
- iso: eng
page: 1168-1194
project:
- _id: '1'
name: SFB 901
- _id: '16'
name: SFB 901 - Subprojekt C4
- _id: '4'
name: SFB 901 - Project Area C
publication: Journal of Combinatorial Optimization
publisher: Springer
status: public
title: Cost-efficient Scheduling on Machines from the Cloud
type: journal_article
user_id: '15415'
volume: 36
year: '2017'
...
---
_id: '55'
abstract:
- lang: eng
text: We introduce the mobile server problem, inspired by current trends to move
computational tasks from cloud structures to multiple devices close to the end
user. An example for this are embedded systems in autonomous cars that communicate
in order to coordinate their actions. Our model is a variant of the classical
Page Migration Problem. Moreformally, we consider a mobile server holding a data
page.The server can move in the Euclidean space (of arbitrary dimension). In every
round, requests for data items from the page pop up at arbitrary points in the
space. The requests are served, each at a cost of the distance from the requesting
point and the server, and the mobile server may move, at a cost D times the distance
traveled for some constant D . We assume a maximum distance m the server is allowed
to move per round. We show that no online algorithm can achieve a competitive
ratio independent of the length of the input sequence in this setting. Hence we
augment the maximum movement distance of the online algorithms to ( 1 + δ) times
the maximum distance of the offline solution. We provide a deterministic algorithm
which is simple to describe and works for multiple variants of our problem. The
algorithm achieves almost tight competitive ratios independent of the length of
the input sequence.
author:
- first_name: Björn
full_name: Feldkord, Björn
id: '22704'
last_name: Feldkord
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Feldkord B, Meyer auf der Heide F. The Mobile Server Problem. In: Proceedings
of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).
; 2017:313-319. doi:10.1145/3087556.3087575'
apa: Feldkord, B., & Meyer auf der Heide, F. (2017). The Mobile Server Problem.
In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures
(SPAA) (pp. 313–319). https://doi.org/10.1145/3087556.3087575
bibtex: '@inproceedings{Feldkord_Meyer auf der Heide_2017, title={The Mobile Server
Problem}, DOI={10.1145/3087556.3087575},
booktitle={Proceedings of the 29th ACM Symposium on Parallelism in Algorithms
and Architectures (SPAA)}, author={Feldkord, Björn and Meyer auf der Heide, Friedhelm},
year={2017}, pages={313–319} }'
chicago: Feldkord, Björn, and Friedhelm Meyer auf der Heide. “The Mobile Server
Problem.” In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms
and Architectures (SPAA), 313–19, 2017. https://doi.org/10.1145/3087556.3087575.
ieee: B. Feldkord and F. Meyer auf der Heide, “The Mobile Server Problem,” in Proceedings
of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA),
2017, pp. 313–319.
mla: Feldkord, Björn, and Friedhelm Meyer auf der Heide. “The Mobile Server Problem.”
Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures
(SPAA), 2017, pp. 313–19, doi:10.1145/3087556.3087575.
short: 'B. Feldkord, F. Meyer auf der Heide, in: Proceedings of the 29th ACM Symposium
on Parallelism in Algorithms and Architectures (SPAA), 2017, pp. 313–319.'
date_created: 2017-10-17T12:41:02Z
date_updated: 2022-01-06T07:01:56Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1145/3087556.3087575
file:
- access_level: closed
content_type: application/pdf
creator: ups
date_created: 2018-11-02T14:55:10Z
date_updated: 2018-11-02T14:55:10Z
file_id: '5288'
file_name: p313-feldkord.pdf
file_size: 691691
relation: main_file
success: 1
file_date_updated: 2018-11-02T14:55:10Z
has_accepted_license: '1'
language:
- iso: eng
page: 313-319
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 29th ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA)
status: public
title: The Mobile Server Problem
type: conference
user_id: '477'
year: '2017'
...
---
_id: '16444'
author:
- first_name: Jürgen
full_name: Gausemeier, Jürgen
last_name: Gausemeier
- first_name: Eric
full_name: Bodden, Eric
last_name: Bodden
- first_name: Falko
full_name: ' Dressler, Falko'
last_name: ' Dressler'
- first_name: Roman
full_name: Dumitrescu, Roman
last_name: Dumitrescu
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Christoph
full_name: Scheytt, Christoph
last_name: Scheytt
- first_name: Ansgar
full_name: Trächtler, Ansgar
last_name: Trächtler
citation:
ama: Gausemeier J, Bodden E, Dressler F, et al. Wissenschaftsforum Intelligente
Technische Systeme (WInTeSys). Paderborn; 2017.
apa: Gausemeier, J., Bodden, E., Dressler, F., Dumitrescu, R., Meyer auf der Heide,
F., Scheytt, C., & Trächtler, A. (2017). Wissenschaftsforum Intelligente
Technische Systeme (WInTeSys). Paderborn.
bibtex: '@book{Gausemeier_Bodden_ Dressler_Dumitrescu_Meyer auf der Heide_Scheytt_Trächtler_2017,
place={Paderborn}, series={Verlagsschriftenreihe des Heinz Nixdorf Instituts,
Paderborn}}, title={Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)},
author={Gausemeier, Jürgen and Bodden, Eric and Dressler, Falko and Dumitrescu,
Roman and Meyer auf der Heide, Friedhelm and Scheytt, Christoph and Trächtler,
Ansgar}, year={2017}, collection={Verlagsschriftenreihe des Heinz Nixdorf Instituts,
Paderborn}} }'
chicago: Gausemeier, Jürgen, Eric Bodden, Falko Dressler, Roman Dumitrescu, Friedhelm
Meyer auf der Heide, Christoph Scheytt, and Ansgar Trächtler. Wissenschaftsforum
Intelligente Technische Systeme (WInTeSys). Verlagsschriftenreihe Des Heinz
Nixdorf Instituts, Paderborn}. Paderborn, 2017.
ieee: J. Gausemeier et al., Wissenschaftsforum Intelligente Technische
Systeme (WInTeSys). Paderborn, 2017.
mla: Gausemeier, Jürgen, et al. Wissenschaftsforum Intelligente Technische Systeme
(WInTeSys). 2017.
short: J. Gausemeier, E. Bodden, F. Dressler, R. Dumitrescu, F. Meyer auf der Heide,
C. Scheytt, A. Trächtler, Wissenschaftsforum Intelligente Technische Systeme (WInTeSys),
Paderborn, 2017.
date_created: 2020-04-07T06:36:06Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
language:
- iso: eng
page: '369'
place: Paderborn
publication_status: published
series_title: Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}
status: public
title: Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)
type: book
user_id: '15415'
year: '2017'
...
---
_id: '16461'
author:
- first_name: Pascal
full_name: Bemmann, Pascal
last_name: Bemmann
- first_name: Felix
full_name: Biermeier, Felix
last_name: Biermeier
- first_name: Jan
full_name: Bürmann, Jan
last_name: Bürmann
- first_name: Arne
full_name: Kemper, Arne
last_name: Kemper
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- first_name: Steffen
full_name: Knorr, Steffen
last_name: Knorr
- first_name: Nils
full_name: Kothe, Nils
last_name: Kothe
- first_name: Alexander
full_name: Mäcker, Alexander
id: '13536'
last_name: Mäcker
- first_name: Manuel
full_name: Malatyali, Manuel
id: '41265'
last_name: Malatyali
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Sören
full_name: Riechers, Sören
last_name: Riechers
- first_name: Johannes Sebastian
full_name: Schaefer, Johannes Sebastian
id: '30291'
last_name: Schaefer
- first_name: Jannik
full_name: Sundermeier, Jannik
id: '38705'
last_name: Sundermeier
citation:
ama: 'Bemmann P, Biermeier F, Bürmann J, et al. Monitoring of Domain-Related Problems
in Distributed Data Streams. In: Structural Information and Communication Complexity.
; 2017. doi:10.1007/978-3-319-72050-0_13'
apa: Bemmann, P., Biermeier, F., Bürmann, J., Kemper, A., Knollmann, T., Knorr,
S., Kothe, N., Mäcker, A., Malatyali, M., Meyer auf der Heide, F., Riechers, S.,
Schaefer, J. S., & Sundermeier, J. (2017). Monitoring of Domain-Related Problems
in Distributed Data Streams. In Structural Information and Communication Complexity.
https://doi.org/10.1007/978-3-319-72050-0_13
bibtex: '@inbook{Bemmann_Biermeier_Bürmann_Kemper_Knollmann_Knorr_Kothe_Mäcker_Malatyali_Meyer
auf der Heide_et al._2017, place={Cham}, title={Monitoring of Domain-Related Problems
in Distributed Data Streams}, DOI={10.1007/978-3-319-72050-0_13},
booktitle={Structural Information and Communication Complexity}, author={Bemmann,
Pascal and Biermeier, Felix and Bürmann, Jan and Kemper, Arne and Knollmann, Till
and Knorr, Steffen and Kothe, Nils and Mäcker, Alexander and Malatyali, Manuel
and Meyer auf der Heide, Friedhelm and et al.}, year={2017} }'
chicago: Bemmann, Pascal, Felix Biermeier, Jan Bürmann, Arne Kemper, Till Knollmann,
Steffen Knorr, Nils Kothe, et al. “Monitoring of Domain-Related Problems in Distributed
Data Streams.” In Structural Information and Communication Complexity.
Cham, 2017. https://doi.org/10.1007/978-3-319-72050-0_13.
ieee: P. Bemmann et al., “Monitoring of Domain-Related Problems in Distributed
Data Streams,” in Structural Information and Communication Complexity,
Cham, 2017.
mla: Bemmann, Pascal, et al. “Monitoring of Domain-Related Problems in Distributed
Data Streams.” Structural Information and Communication Complexity, 2017,
doi:10.1007/978-3-319-72050-0_13.
short: 'P. Bemmann, F. Biermeier, J. Bürmann, A. Kemper, T. Knollmann, S. Knorr,
N. Kothe, A. Mäcker, M. Malatyali, F. Meyer auf der Heide, S. Riechers, J.S. Schaefer,
J. Sundermeier, in: Structural Information and Communication Complexity, Cham,
2017.'
date_created: 2020-04-08T07:20:20Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1007/978-3-319-72050-0_13
external_id:
arxiv:
- 'arXiv:1706.03568 '
language:
- iso: eng
place: Cham
publication: Structural Information and Communication Complexity
publication_identifier:
isbn:
- '9783319720494'
- '9783319720500'
issn:
- 0302-9743
- 1611-3349
publication_status: published
status: public
title: Monitoring of Domain-Related Problems in Distributed Data Streams
type: book_chapter
user_id: '15415'
year: '2017'
...
---
_id: '16347'
author:
- first_name: Matthias
full_name: Fischer, Matthias
id: '146'
last_name: Fischer
- first_name: Daniel
full_name: Jung, Daniel
id: '37827'
last_name: Jung
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Fischer M, Jung D, Meyer auf der Heide F. Gathering Anonymous, Oblivious Robots
on a Grid. In: Fernández Anta A, Jurdzinski T, Mosteiro MA, Zhang Y, eds. Algorithms
for Sensor Systems - 13th International Symposium on Algorithms and Experiments
for Wireless Sensor Networks, {ALGOSENSORS}. Vol 10718. Lecture Notes in Computer
Science. Vienna, Austria: Springer; 2017:168-181. doi:10.1007/978-3-319-72751-6_13'
apa: 'Fischer, M., Jung, D., & Meyer auf der Heide, F. (2017). Gathering Anonymous,
Oblivious Robots on a Grid. In A. Fernández Anta, T. Jurdzinski, M. A. Mosteiro,
& Y. Zhang (Eds.), Algorithms for Sensor Systems - 13th International Symposium
on Algorithms and Experiments for Wireless Sensor Networks, {ALGOSENSORS}
(Vol. 10718, pp. 168–181). Vienna, Austria: Springer. https://doi.org/10.1007/978-3-319-72751-6_13'
bibtex: '@inproceedings{Fischer_Jung_Meyer auf der Heide_2017, place={Vienna, Austria},
series={Lecture Notes in Computer Science}, title={Gathering Anonymous, Oblivious
Robots on a Grid}, volume={10718}, DOI={10.1007/978-3-319-72751-6_13},
booktitle={Algorithms for Sensor Systems - 13th International Symposium on Algorithms
and Experiments for Wireless Sensor Networks, {ALGOSENSORS}}, publisher={Springer},
author={Fischer, Matthias and Jung, Daniel and Meyer auf der Heide, Friedhelm},
editor={Fernández Anta, Antonio and Jurdzinski, Tomasz and Mosteiro, Miguel A.
and Zhang, YanyongEditors}, year={2017}, pages={168–181}, collection={Lecture
Notes in Computer Science} }'
chicago: 'Fischer, Matthias, Daniel Jung, and Friedhelm Meyer auf der Heide. “Gathering
Anonymous, Oblivious Robots on a Grid.” In Algorithms for Sensor Systems -
13th International Symposium on Algorithms and Experiments for Wireless Sensor
Networks, {ALGOSENSORS}, edited by Antonio Fernández Anta, Tomasz Jurdzinski,
Miguel A. Mosteiro, and Yanyong Zhang, 10718:168–81. Lecture Notes in Computer
Science. Vienna, Austria: Springer, 2017. https://doi.org/10.1007/978-3-319-72751-6_13.'
ieee: M. Fischer, D. Jung, and F. Meyer auf der Heide, “Gathering Anonymous, Oblivious
Robots on a Grid,” in Algorithms for Sensor Systems - 13th International Symposium
on Algorithms and Experiments for Wireless Sensor Networks, {ALGOSENSORS},
2017, vol. 10718, pp. 168–181.
mla: Fischer, Matthias, et al. “Gathering Anonymous, Oblivious Robots on a Grid.”
Algorithms for Sensor Systems - 13th International Symposium on Algorithms
and Experiments for Wireless Sensor Networks, {ALGOSENSORS}, edited by Antonio
Fernández Anta et al., vol. 10718, Springer, 2017, pp. 168–81, doi:10.1007/978-3-319-72751-6_13.
short: 'M. Fischer, D. Jung, F. Meyer auf der Heide, in: A. Fernández Anta, T. Jurdzinski,
M.A. Mosteiro, Y. Zhang (Eds.), Algorithms for Sensor Systems - 13th International
Symposium on Algorithms and Experiments for Wireless Sensor Networks, {ALGOSENSORS},
Springer, Vienna, Austria, 2017, pp. 168–181.'
date_created: 2020-03-27T14:32:39Z
date_updated: 2022-01-06T06:52:49Z
department:
- _id: '63'
doi: 10.1007/978-3-319-72751-6_13
editor:
- first_name: Antonio
full_name: Fernández Anta, Antonio
last_name: Fernández Anta
- first_name: Tomasz
full_name: Jurdzinski, Tomasz
last_name: Jurdzinski
- first_name: Miguel A.
full_name: Mosteiro, Miguel A.
last_name: Mosteiro
- first_name: Yanyong
full_name: Zhang, Yanyong
last_name: Zhang
intvolume: ' 10718'
language:
- iso: eng
page: 168-181
place: Vienna, Austria
publication: Algorithms for Sensor Systems - 13th International Symposium on Algorithms
and Experiments for Wireless Sensor Networks, {ALGOSENSORS}
publisher: Springer
series_title: Lecture Notes in Computer Science
status: public
title: Gathering Anonymous, Oblivious Robots on a Grid
type: conference
user_id: '15415'
volume: 10718
year: '2017'
...
---
_id: '16348'
author:
- first_name: Felix
full_name: Biermeier, Felix
last_name: Biermeier
- first_name: Björn
full_name: Feldkord, Björn
id: '22704'
last_name: Feldkord
- first_name: Manuel
full_name: Malatyali, Manuel
last_name: Malatyali
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Biermeier F, Feldkord B, Malatyali M, Meyer auf der Heide F. A Communication-Efficient
Distributed Data Structure for Top-k and k-Select Queries. In: Proceedings
of the 15th Workshop on Approximation and Online Algorithms (WAOA). Springer;
2017:285-300. doi:10.1007/978-3-319-89441-6_21'
apa: Biermeier, F., Feldkord, B., Malatyali, M., & Meyer auf der Heide, F. (2017).
A Communication-Efficient Distributed Data Structure for Top-k and k-Select Queries.
In Proceedings of the 15th Workshop on Approximation and Online Algorithms
(WAOA) (pp. 285–300). Springer. https://doi.org/10.1007/978-3-319-89441-6_21
bibtex: '@inproceedings{Biermeier_Feldkord_Malatyali_Meyer auf der Heide_2017, title={A
Communication-Efficient Distributed Data Structure for Top-k and k-Select Queries},
DOI={10.1007/978-3-319-89441-6_21},
booktitle={Proceedings of the 15th Workshop on Approximation and Online Algorithms
(WAOA)}, publisher={Springer}, author={Biermeier, Felix and Feldkord, Björn and
Malatyali, Manuel and Meyer auf der Heide, Friedhelm}, year={2017}, pages={285–300}
}'
chicago: Biermeier, Felix, Björn Feldkord, Manuel Malatyali, and Friedhelm Meyer
auf der Heide. “A Communication-Efficient Distributed Data Structure for Top-k
and k-Select Queries.” In Proceedings of the 15th Workshop on Approximation
and Online Algorithms (WAOA), 285–300. Springer, 2017. https://doi.org/10.1007/978-3-319-89441-6_21.
ieee: F. Biermeier, B. Feldkord, M. Malatyali, and F. Meyer auf der Heide, “A Communication-Efficient
Distributed Data Structure for Top-k and k-Select Queries,” in Proceedings
of the 15th Workshop on Approximation and Online Algorithms (WAOA), 2017,
pp. 285–300.
mla: Biermeier, Felix, et al. “A Communication-Efficient Distributed Data Structure
for Top-k and k-Select Queries.” Proceedings of the 15th Workshop on Approximation
and Online Algorithms (WAOA), Springer, 2017, pp. 285–300, doi:10.1007/978-3-319-89441-6_21.
short: 'F. Biermeier, B. Feldkord, M. Malatyali, F. Meyer auf der Heide, in: Proceedings
of the 15th Workshop on Approximation and Online Algorithms (WAOA), Springer,
2017, pp. 285–300.'
date_created: 2020-03-30T09:25:18Z
date_updated: 2022-01-06T06:52:49Z
department:
- _id: '63'
doi: 10.1007/978-3-319-89441-6_21
language:
- iso: eng
page: 285 - 300
publication: Proceedings of the 15th Workshop on Approximation and Online Algorithms
(WAOA)
publisher: Springer
status: public
title: A Communication-Efficient Distributed Data Structure for Top-k and k-Select
Queries
type: conference
user_id: '15415'
year: '2017'
...
---
_id: '16349'
author:
- first_name: Pavel
full_name: Podlipyan, Pavel
last_name: Podlipyan
- first_name: Shouwei
full_name: Li, Shouwei
last_name: Li
- first_name: Christine
full_name: Markarian, Christine
id: '37612'
last_name: Markarian
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Podlipyan P, Li S, Markarian C, Meyer auf der Heide F. A Continuous Strategy
for Collisionless Gathering. In: Proceedings of the 13th International Symposium
on Algorithms and Experiments for Wireless Networks (ALGOSENSORS). ; 2017:182-197.
doi:10.1007/978-3-319-72751-6_14
'
apa: Podlipyan, P., Li, S., Markarian, C., & Meyer auf der Heide, F. (2017).
A Continuous Strategy for Collisionless Gathering. In Proceedings of the 13th
International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS)
(pp. 182–197). https://doi.org/10.1007/978-3-319-72751-6_14
bibtex: '@inproceedings{Podlipyan_Li_Markarian_Meyer auf der Heide_2017, title={A
Continuous Strategy for Collisionless Gathering}, DOI={10.1007/978-3-319-72751-6_14 }, booktitle={Proceedings of the 13th International
Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS)},
author={Podlipyan, Pavel and Li, Shouwei and Markarian, Christine and Meyer auf
der Heide, Friedhelm}, year={2017}, pages={182–197} }'
chicago: Podlipyan, Pavel, Shouwei Li, Christine Markarian, and Friedhelm Meyer
auf der Heide. “A Continuous Strategy for Collisionless Gathering.” In Proceedings
of the 13th International Symposium on Algorithms and Experiments for Wireless
Networks (ALGOSENSORS), 182–97, 2017. https://doi.org/10.1007/978-3-319-72751-6_14 .
ieee: P. Podlipyan, S. Li, C. Markarian, and F. Meyer auf der Heide, “A Continuous
Strategy for Collisionless Gathering,” in Proceedings of the 13th International
Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS),
2017, pp. 182–197.
mla: Podlipyan, Pavel, et al. “A Continuous Strategy for Collisionless Gathering.”
Proceedings of the 13th International Symposium on Algorithms and Experiments
for Wireless Networks (ALGOSENSORS), 2017, pp. 182–97, doi:10.1007/978-3-319-72751-6_14 .
short: 'P. Podlipyan, S. Li, C. Markarian, F. Meyer auf der Heide, in: Proceedings
of the 13th International Symposium on Algorithms and Experiments for Wireless
Networks (ALGOSENSORS), 2017, pp. 182–197.'
date_created: 2020-03-30T09:43:05Z
date_updated: 2022-01-06T06:52:49Z
department:
- _id: '63'
doi: '10.1007/978-3-319-72751-6_14 '
language:
- iso: eng
page: 182-197
publication: Proceedings of the 13th International Symposium on Algorithms and Experiments
for Wireless Networks (ALGOSENSORS)
status: public
title: A Continuous Strategy for Collisionless Gathering
type: conference
user_id: '15415'
year: '2017'
...
---
_id: '177'
abstract:
- lang: eng
text: 'Efficiently parallelizable parameterized problems have been classified as
being either in the class FPP (fixed-parameter parallelizable) or the class PNC
(parameterized analog of NC), which contains FPP as a subclass. In this paper,
we propose a more restrictive class of parallelizable parameterized problems called
fixed-parameter parallel-tractable (FPPT). For a problem to be in FPPT, it should
possess an efficient parallel algorithm not only from a theoretical standpoint
but in practice as well. The primary distinction between FPPT and FPP is the parallel
processor utilization, which is bounded by a polynomial function in the case of
FPPT. We initiate the study of FPPT with the well-known k-vertex cover problem.
In particular, we present a parallel algorithm that outperforms the best known
parallel algorithm for this problem: using O(m) instead of O(n2) parallel processors,
the running time improves from 4logn+O(kk) to O(k⋅log3n), where m is the number
of edges, n is the number of vertices of the input graph, and k is an upper bound
of the size of the sought vertex cover. We also note that a few P-complete problems
fall into FPPT including the monotone circuit value problem (MCV) when the underlying
graphs are bounded by a constant Euler genus.'
author:
- first_name: Faisal N.
full_name: Abu-Khzam, Faisal N.
last_name: Abu-Khzam
- first_name: Shouwei
full_name: Li, Shouwei
last_name: Li
- first_name: Christine
full_name: Markarian, Christine
id: '37612'
last_name: Markarian
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Pavel
full_name: Podlipyan, Pavel
last_name: Podlipyan
citation:
ama: 'Abu-Khzam FN, Li S, Markarian C, Meyer auf der Heide F, Podlipyan P. On the
Parameterized Parallel Complexity and the Vertex Cover Problem. In: Proceedings
of the 10th International Conference on Combinatorial Optimization and Applications
(COCOA). LNCS. ; 2016:477-488. doi:10.1007/978-3-319-48749-6_35'
apa: Abu-Khzam, F. N., Li, S., Markarian, C., Meyer auf der Heide, F., & Podlipyan,
P. (2016). On the Parameterized Parallel Complexity and the Vertex Cover Problem.
In Proceedings of the 10th International Conference on Combinatorial Optimization
and Applications (COCOA) (pp. 477–488). https://doi.org/10.1007/978-3-319-48749-6_35
bibtex: '@inproceedings{Abu-Khzam_Li_Markarian_Meyer auf der Heide_Podlipyan_2016,
series={LNCS}, title={On the Parameterized Parallel Complexity and the Vertex
Cover Problem}, DOI={10.1007/978-3-319-48749-6_35},
booktitle={Proceedings of the 10th International Conference on Combinatorial Optimization
and Applications (COCOA)}, author={Abu-Khzam, Faisal N. and Li, Shouwei and Markarian,
Christine and Meyer auf der Heide, Friedhelm and Podlipyan, Pavel}, year={2016},
pages={477–488}, collection={LNCS} }'
chicago: Abu-Khzam, Faisal N., Shouwei Li, Christine Markarian, Friedhelm Meyer
auf der Heide, and Pavel Podlipyan. “On the Parameterized Parallel Complexity
and the Vertex Cover Problem.” In Proceedings of the 10th International Conference
on Combinatorial Optimization and Applications (COCOA), 477–88. LNCS, 2016.
https://doi.org/10.1007/978-3-319-48749-6_35.
ieee: F. N. Abu-Khzam, S. Li, C. Markarian, F. Meyer auf der Heide, and P. Podlipyan,
“On the Parameterized Parallel Complexity and the Vertex Cover Problem,” in Proceedings
of the 10th International Conference on Combinatorial Optimization and Applications
(COCOA), 2016, pp. 477–488.
mla: Abu-Khzam, Faisal N., et al. “On the Parameterized Parallel Complexity and
the Vertex Cover Problem.” Proceedings of the 10th International Conference
on Combinatorial Optimization and Applications (COCOA), 2016, pp. 477–88,
doi:10.1007/978-3-319-48749-6_35.
short: 'F.N. Abu-Khzam, S. Li, C. Markarian, F. Meyer auf der Heide, P. Podlipyan,
in: Proceedings of the 10th International Conference on Combinatorial Optimization
and Applications (COCOA), 2016, pp. 477–488.'
date_created: 2017-10-17T12:41:26Z
date_updated: 2022-01-06T06:53:17Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1007/978-3-319-48749-6_35
file:
- access_level: closed
content_type: application/pdf
creator: ups
date_created: 2018-11-02T14:15:18Z
date_updated: 2018-11-02T14:15:18Z
file_id: '5266'
file_name: OnTheParameterizedParallelComp.pdf
file_size: 293345
relation: main_file
success: 1
file_date_updated: 2018-11-02T14:15:18Z
has_accepted_license: '1'
language:
- iso: eng
page: 477-488
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 10th International Conference on Combinatorial Optimization
and Applications (COCOA)
series_title: LNCS
status: public
title: On the Parameterized Parallel Complexity and the Vertex Cover Problem
type: conference
user_id: '477'
year: '2016'
...
---
_id: '187'
citation:
ama: Meyer auf der Heide F, ed. Introduction to the Special Issue on SPAA 2014.;
2016. doi:10.1145/2936716
apa: Meyer auf der Heide, F. (Ed.). (2016). Introduction to the Special Issue
on SPAA 2014. Transactions on Parallel Computing (TOPC). https://doi.org/10.1145/2936716
bibtex: '@book{Meyer auf der Heide_2016, title={Introduction to the Special Issue
on SPAA 2014}, DOI={10.1145/2936716},
number={1}, journal={Transactions on Parallel Computing (TOPC)}, year={2016} }'
chicago: Meyer auf der Heide, Friedhelm, ed. Introduction to the Special Issue
on SPAA 2014. Transactions on Parallel Computing (TOPC), 2016. https://doi.org/10.1145/2936716.
ieee: F. Meyer auf der Heide, Ed., Introduction to the Special Issue on SPAA
2014, no. 1. 2016.
mla: Meyer auf der Heide, Friedhelm, editor. “Introduction to the Special Issue
on SPAA 2014.” Transactions on Parallel Computing (TOPC), no. 1, 2016,
doi:10.1145/2936716.
short: F. Meyer auf der Heide, ed., Introduction to the Special Issue on SPAA 2014,
2016.
date_created: 2017-10-17T12:41:28Z
date_updated: 2022-01-06T06:53:51Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1145/2936716
editor:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-21T12:31:42Z
date_updated: 2018-03-21T12:31:42Z
file_id: '1531'
file_name: 187-a1-heide.pdf
file_size: 34053
relation: main_file
success: 1
file_date_updated: 2018-03-21T12:31:42Z
has_accepted_license: '1'
issue: '1'
page: '1'
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '2'
name: SFB 901 - Project Area A
publication: Transactions on Parallel Computing (TOPC)
status: public
title: Introduction to the Special Issue on SPAA 2014
type: journal_editor
user_id: '15504'
year: '2016'
...
---
_id: '207'
abstract:
- lang: eng
text: We consider a scheduling problem where machines need to be rented from the
cloud in order to process jobs. There are two types of machines available which
can be rented for machine-type dependent prices and for arbitrary durations. However,
a machine-type dependent setup time is required before a machine is available
for processing. Jobs arrive online over time, have machine-type dependent sizes
and have individual deadlines. The objective is to rent machines and schedule
jobs so as to meet all deadlines while minimizing the rental cost. Since we observe
the slack of jobs to have a fundamental influence on the competitiveness, we study
the model when instances are parameterized by their (minimum) slack. An instance
is called to have a slack of $\beta$ if, for all jobs, the difference between
the job's release time and the latest point in time at which it needs to be started
is at least $\beta$. While for $\beta series = {LNCS}
author:
- first_name: Alexander
full_name: Mäcker, Alexander
id: '13536'
last_name: Mäcker
- first_name: Manuel
full_name: Malatyali, Manuel
last_name: Malatyali
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Sören
full_name: Riechers, Sören
last_name: Riechers
citation:
ama: 'Mäcker A, Malatyali M, Meyer auf der Heide F, Riechers S. Cost-efficient Scheduling
on Machines from the Cloud. In: Proceedings of the 10th Annual International
Conference on Combinatorial Optimization and Applications (COCOA). ; 2016:578--592.
doi:10.1007/978-3-319-48749-6_42'
apa: Mäcker, A., Malatyali, M., Meyer auf der Heide, F., & Riechers, S. (2016).
Cost-efficient Scheduling on Machines from the Cloud. In Proceedings of the
10th Annual International Conference on Combinatorial Optimization and Applications
(COCOA) (pp. 578--592). https://doi.org/10.1007/978-3-319-48749-6_42
bibtex: '@inproceedings{Mäcker_Malatyali_Meyer auf der Heide_Riechers_2016, title={Cost-efficient
Scheduling on Machines from the Cloud}, DOI={10.1007/978-3-319-48749-6_42},
booktitle={Proceedings of the 10th Annual International Conference on Combinatorial
Optimization and Applications (COCOA)}, author={Mäcker, Alexander and Malatyali,
Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören}, year={2016}, pages={578--592}
}'
chicago: Mäcker, Alexander, Manuel Malatyali, Friedhelm Meyer auf der Heide, and
Sören Riechers. “Cost-Efficient Scheduling on Machines from the Cloud.” In Proceedings
of the 10th Annual International Conference on Combinatorial Optimization and
Applications (COCOA), 578--592, 2016. https://doi.org/10.1007/978-3-319-48749-6_42.
ieee: A. Mäcker, M. Malatyali, F. Meyer auf der Heide, and S. Riechers, “Cost-efficient
Scheduling on Machines from the Cloud,” in Proceedings of the 10th Annual International
Conference on Combinatorial Optimization and Applications (COCOA), 2016, pp.
578--592.
mla: Mäcker, Alexander, et al. “Cost-Efficient Scheduling on Machines from the Cloud.”
Proceedings of the 10th Annual International Conference on Combinatorial Optimization
and Applications (COCOA), 2016, pp. 578--592, doi:10.1007/978-3-319-48749-6_42.
short: 'A. Mäcker, M. Malatyali, F. Meyer auf der Heide, S. Riechers, in: Proceedings
of the 10th Annual International Conference on Combinatorial Optimization and
Applications (COCOA), 2016, pp. 578--592.'
date_created: 2017-10-17T12:41:32Z
date_updated: 2022-01-06T06:54:33Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1007/978-3-319-48749-6_42
file:
- access_level: closed
content_type: application/pdf
creator: ups
date_created: 2018-11-02T14:18:51Z
date_updated: 2018-11-02T14:18:51Z
file_id: '5268'
file_name: Cost-EfficientSchedulingOnMach.pdf
file_size: 608614
relation: main_file
success: 1
file_date_updated: 2018-11-02T14:18:51Z
has_accepted_license: '1'
language:
- iso: eng
page: 578--592
project:
- _id: '1'
name: SFB 901
- _id: '16'
name: SFB 901 - Subprojekt C4
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the 10th Annual International Conference on Combinatorial
Optimization and Applications (COCOA)
status: public
title: Cost-efficient Scheduling on Machines from the Cloud
type: conference
user_id: '477'
year: '2016'
...