---
_id: '31847'
abstract:
- lang: eng
text: "The famous $k$-Server Problem covers plenty of resource allocation scenarios,
and several variations have been studied extensively for decades. However, to
the best of our knowledge, no research has considered the problem if the servers
are not identical and requests can express which specific servers should serve
them. Therefore, we present a new model generalizing the $k$-Server Problem by
*preferences* of the requests and proceed to study it in a uniform metric space
for deterministic online algorithms (the special case of paging).\r\n\r\nIn our
model, requests can either demand to be answered by any server (*general requests*)
or by a specific one (*specific requests*). If only general requests appear, the
instance is one of the original $k$-Server Problem, and a lower bound for the
competitive ratio of $k$ applies. If only specific requests appear, a solution
with a competitive ratio of $1$ becomes trivial since there is no freedom regarding
the servers' movements. Perhaps counter-intuitively, we show that if both kinds
of requests appear, the lower bound raises to $2k-1$.\r\n\r\nWe study deterministic
online algorithms in uniform metrics and present two algorithms. The first one
has an adaptive competitive ratio dependent on the frequency of specific requests.
It achieves a worst-case competitive ratio of $3k-2$ while it is optimal when
only general or only specific requests appear (competitive ratio of $k$ and $1$,
respectively). The second has a fixed close-to-optimal worst-case competitive
ratio of $2k+14$. For the first algorithm, we show a lower bound of $3k-2$, while
the second algorithm has a lower bound of $2k-1$ when only general requests appear.\r\n
\ \r\nThe two algorithms differ in only one behavioral rule for each server
that significantly influences the competitive ratio. Each server acting according
to the rule allows approaching the worst-case lower bound, while it implies an
increased lower bound for $k$-Server instances. In other words, there is a trade-off
between performing well against instances of the $k$-Server Problem and instances
containing specific requests. We also show that no deterministic online algorithm
can be optimal for both kinds of instances simultaneously."
author:
- first_name: Jannik
full_name: Castenow, Jannik
id: '38705'
last_name: Castenow
- first_name: Björn
full_name: Feldkord, Björn
id: '22704'
last_name: Feldkord
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- 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
citation:
ama: 'Castenow J, Feldkord B, Knollmann T, Malatyali M, Meyer auf der Heide F. The
k-Server with Preferences Problem. In: Proceedings of the 34th ACM Symposium
on Parallelism in Algorithms and Architectures. Association for Computing
Machinery; 2022:345-356. doi:10.1145/3490148.3538595'
apa: Castenow, J., Feldkord, B., Knollmann, T., Malatyali, M., & Meyer auf der
Heide, F. (2022). The k-Server with Preferences Problem. Proceedings of the
34th ACM Symposium on Parallelism in Algorithms and Architectures, 345–356.
https://doi.org/10.1145/3490148.3538595
bibtex: '@inproceedings{Castenow_Feldkord_Knollmann_Malatyali_Meyer auf der Heide_2022,
title={The k-Server with Preferences Problem}, DOI={10.1145/3490148.3538595},
booktitle={Proceedings of the 34th ACM Symposium on Parallelism in Algorithms
and Architectures}, publisher={Association for Computing Machinery}, author={Castenow,
Jannik and Feldkord, Björn and Knollmann, Till and Malatyali, Manuel and Meyer
auf der Heide, Friedhelm}, year={2022}, pages={345–356} }'
chicago: Castenow, Jannik, Björn Feldkord, Till Knollmann, Manuel Malatyali, and
Friedhelm Meyer auf der Heide. “The K-Server with Preferences Problem.” In Proceedings
of the 34th ACM Symposium on Parallelism in Algorithms and Architectures,
345–56. Association for Computing Machinery, 2022. https://doi.org/10.1145/3490148.3538595.
ieee: 'J. Castenow, B. Feldkord, T. Knollmann, M. Malatyali, and F. Meyer auf der
Heide, “The k-Server with Preferences Problem,” in Proceedings of the 34th
ACM Symposium on Parallelism in Algorithms and Architectures, 2022, pp. 345–356,
doi: 10.1145/3490148.3538595.'
mla: Castenow, Jannik, et al. “The K-Server with Preferences Problem.” Proceedings
of the 34th ACM Symposium on Parallelism in Algorithms and Architectures,
Association for Computing Machinery, 2022, pp. 345–56, doi:10.1145/3490148.3538595.
short: 'J. Castenow, B. Feldkord, T. Knollmann, M. Malatyali, F. Meyer auf der Heide,
in: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures,
Association for Computing Machinery, 2022, pp. 345–356.'
date_created: 2022-06-10T09:06:42Z
date_updated: 2022-08-02T08:07:30Z
department:
- _id: '63'
doi: 10.1145/3490148.3538595
external_id:
arxiv:
- '2205.11102'
keyword:
- K-Server Problem
- Heterogeneity
- Online Caching
language:
- iso: eng
page: 345-356
project:
- _id: '1'
name: 'SFB 901: SFB 901'
- _id: '2'
name: 'SFB 901 - A: SFB 901 - Project Area A'
- _id: '5'
name: 'SFB 901 - A1: SFB 901 - Subproject A1'
publication: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and
Architectures
publication_identifier:
isbn:
- '9781450391467'
publisher: Association for Computing Machinery
status: public
title: The k-Server with Preferences Problem
type: conference
user_id: '39241'
year: '2022'
...
---
_id: '20683'
author:
- first_name: Björn
full_name: Feldkord, Björn
id: '22704'
last_name: Feldkord
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- 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
citation:
ama: Feldkord B, Knollmann T, Malatyali M, Meyer auf der Heide F. Managing Multiple
Mobile Resources. Theory of Computing Systems. 2021;65:943–984. doi:10.1007/s00224-020-10023-8
apa: Feldkord, B., Knollmann, T., Malatyali, M., & Meyer auf der Heide, F. (2021).
Managing Multiple Mobile Resources. Theory of Computing Systems, 65,
943–984. https://doi.org/10.1007/s00224-020-10023-8
bibtex: '@article{Feldkord_Knollmann_Malatyali_Meyer auf der Heide_2021, title={Managing
Multiple Mobile Resources}, volume={65}, DOI={10.1007/s00224-020-10023-8},
journal={Theory of Computing Systems}, author={Feldkord, Björn and Knollmann,
Till and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}, year={2021}, pages={943–984}
}'
chicago: 'Feldkord, Björn, Till Knollmann, Manuel Malatyali, and Friedhelm Meyer
auf der Heide. “Managing Multiple Mobile Resources.” Theory of Computing Systems
65 (2021): 943–984. https://doi.org/10.1007/s00224-020-10023-8.'
ieee: 'B. Feldkord, T. Knollmann, M. Malatyali, and F. Meyer auf der Heide, “Managing
Multiple Mobile Resources,” Theory of Computing Systems, vol. 65, pp. 943–984,
2021, doi: 10.1007/s00224-020-10023-8.'
mla: Feldkord, Björn, et al. “Managing Multiple Mobile Resources.” Theory of
Computing Systems, vol. 65, 2021, pp. 943–984, doi:10.1007/s00224-020-10023-8.
short: B. Feldkord, T. Knollmann, M. Malatyali, F. Meyer auf der Heide, Theory of
Computing Systems 65 (2021) 943–984.
date_created: 2020-12-08T08:40:10Z
date_updated: 2022-01-06T06:54:31Z
department:
- _id: '63'
doi: 10.1007/s00224-020-10023-8
intvolume: ' 65'
language:
- iso: eng
page: 943–984
project:
- _id: '1'
name: SFB 901
- _id: '2'
name: SFB 901 - Project Area A
- _id: '5'
name: SFB 901 - Subproject A1
publication: Theory of Computing Systems
publication_status: published
status: public
title: Managing Multiple Mobile Resources
type: journal_article
user_id: '15415'
volume: 65
year: '2021'
...
---
_id: '20817'
author:
- first_name: Marcin
full_name: Bienkowski, Marcin
last_name: Bienkowski
- first_name: Björn
full_name: Feldkord, Björn
id: '22704'
last_name: Feldkord
- first_name: Pawel
full_name: Schmidt, Pawel
last_name: Schmidt
citation:
ama: 'Bienkowski M, Feldkord B, Schmidt P. A Nearly Optimal Deterministic Online
Algorithm for Non-Metric Facility Location. In: Proceedings of the 38th Symposium
on Theoretical Aspects of Computer Science (STACS). ; 2021:14:1-14:17. doi:10.4230/LIPIcs.STACS.2021.14'
apa: Bienkowski, M., Feldkord, B., & Schmidt, P. (2021). A Nearly Optimal Deterministic
Online Algorithm for Non-Metric Facility Location. In Proceedings of the 38th
Symposium on Theoretical Aspects of Computer Science (STACS) (pp. 14:1-14:17).
https://doi.org/10.4230/LIPIcs.STACS.2021.14
bibtex: '@inproceedings{Bienkowski_Feldkord_Schmidt_2021, title={A Nearly Optimal
Deterministic Online Algorithm for Non-Metric Facility Location}, DOI={10.4230/LIPIcs.STACS.2021.14},
booktitle={Proceedings of the 38th Symposium on Theoretical Aspects of Computer
Science (STACS)}, author={Bienkowski, Marcin and Feldkord, Björn and Schmidt,
Pawel}, year={2021}, pages={14:1-14:17} }'
chicago: Bienkowski, Marcin, Björn Feldkord, and Pawel Schmidt. “A Nearly Optimal
Deterministic Online Algorithm for Non-Metric Facility Location.” In Proceedings
of the 38th Symposium on Theoretical Aspects of Computer Science (STACS),
14:1-14:17, 2021. https://doi.org/10.4230/LIPIcs.STACS.2021.14.
ieee: M. Bienkowski, B. Feldkord, and P. Schmidt, “A Nearly Optimal Deterministic
Online Algorithm for Non-Metric Facility Location,” in Proceedings of the 38th
Symposium on Theoretical Aspects of Computer Science (STACS), 2021, pp. 14:1-14:17.
mla: Bienkowski, Marcin, et al. “A Nearly Optimal Deterministic Online Algorithm
for Non-Metric Facility Location.” Proceedings of the 38th Symposium on Theoretical
Aspects of Computer Science (STACS), 2021, pp. 14:1-14:17, doi:10.4230/LIPIcs.STACS.2021.14.
short: 'M. Bienkowski, B. Feldkord, P. Schmidt, in: Proceedings of the 38th Symposium
on Theoretical Aspects of Computer Science (STACS), 2021, pp. 14:1-14:17.'
date_created: 2020-12-21T13:46:16Z
date_updated: 2022-01-06T06:54:40Z
department:
- _id: '63'
doi: 10.4230/LIPIcs.STACS.2021.14
language:
- iso: eng
page: 14:1 - 14:17
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 38th Symposium on Theoretical Aspects of Computer
Science (STACS)
publication_status: published
status: public
title: A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location
type: conference
user_id: '22704'
year: '2021'
...
---
_id: '17370'
abstract:
- lang: eng
text: " We consider a natural extension to the metric uncapacitated Facility Location
Problem (FLP) in which requests ask for different commodities out of a finite
set \\( S \\) of commodities.\r\n Ravi and Sinha (SODA 2004) introduced the model
as the \\emph{Multi-Commodity Facility Location Problem} (MFLP) and considered
it an offline optimization problem.\r\n The model itself is similar to the FLP:
i.e., requests are located at points of a finite metric space and the task of
an algorithm is to construct facilities and assign requests to facilities while
minimizing the construction cost and the sum over all assignment distances.\r\n
\ In addition, requests and facilities are heterogeneous; they request or offer
multiple commodities out of $S$.\r\n A request has to be connected to a set of
facilities jointly offering the commodities demanded by it.\r\n In comparison
to the FLP, an algorithm has to decide not only if and where to place facilities,
but also which commodities to offer at each.\r\n\r\n To the best of our knowledge
we are the first to study the problem in its online variant in which requests,
their positions and their commodities are not known beforehand but revealed over
time.\r\n We present results regarding the competitive ratio.\r\n On the one
hand, we show that heterogeneity influences the competitive ratio by developing
a lower bound on the competitive ratio for any randomized online algorithm of
\\( \\Omega ( \\sqrt{|S|} + \\frac{\\log n}{\\log \\log n} ) \\) that already
holds for simple line metrics.\r\n Here, \\( n \\) is the number of requests.\r\n
\ On the other side, we establish a deterministic \\( \\mathcal{O}(\\sqrt{|S|}
\\cdot \\log n) \\)-competitive algorithm and a randomized \\( \\mathcal{O}(\\sqrt{|S|}
\\cdot \\frac{\\log n}{\\log \\log n} ) \\)-competitive algorithm.\r\n Further,
we show that when considering a more special class of cost functions for the construction
cost of a facility, the competitive ratio decreases given by our deterministic
algorithm depending on the function."
author:
- first_name: Jannik
full_name: Castenow, Jannik
id: '38705'
last_name: Castenow
- first_name: Björn
full_name: Feldkord, Björn
id: '22704'
last_name: Feldkord
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- 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: 'Castenow J, Feldkord B, Knollmann T, Malatyali M, Meyer auf der Heide F. The
Online Multi-Commodity Facility Location Problem. In: Proceedings of the 32nd
ACM Symposium on Parallelism in Algorithms and Architectures. ; 2020. doi:10.1145/3350755.3400281'
apa: Castenow, J., Feldkord, B., Knollmann, T., Malatyali, M., & Meyer auf der
Heide, F. (2020). The Online Multi-Commodity Facility Location Problem. In Proceedings
of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures.
https://doi.org/10.1145/3350755.3400281
bibtex: '@inproceedings{Castenow_Feldkord_Knollmann_Malatyali_Meyer auf der Heide_2020,
title={The Online Multi-Commodity Facility Location Problem}, DOI={10.1145/3350755.3400281},
booktitle={Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms
and Architectures}, author={Castenow, Jannik and Feldkord, Björn and Knollmann,
Till and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}, year={2020} }'
chicago: Castenow, Jannik, Björn Feldkord, Till Knollmann, Manuel Malatyali, and
Friedhelm Meyer auf der Heide. “The Online Multi-Commodity Facility Location Problem.”
In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures,
2020. https://doi.org/10.1145/3350755.3400281.
ieee: J. Castenow, B. Feldkord, T. Knollmann, M. Malatyali, and F. Meyer auf der
Heide, “The Online Multi-Commodity Facility Location Problem,” in Proceedings
of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures,
2020.
mla: Castenow, Jannik, et al. “The Online Multi-Commodity Facility Location Problem.”
Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures,
2020, doi:10.1145/3350755.3400281.
short: 'J. Castenow, B. Feldkord, T. Knollmann, M. Malatyali, F. Meyer auf der Heide,
in: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures,
2020.'
date_created: 2020-07-14T07:53:20Z
date_updated: 2022-01-06T06:53:10Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1145/3350755.3400281
external_id:
arxiv:
- '2005.08391'
file:
- access_level: closed
content_type: application/pdf
creator: tillk
date_created: 2020-07-14T07:56:52Z
date_updated: 2020-07-14T07:56:52Z
file_id: '17373'
file_name: 3350755.3400281.pdf
file_size: 1271416
relation: main_file
success: 1
file_date_updated: 2020-07-14T07:56:52Z
has_accepted_license: '1'
keyword:
- Online Multi-Commodity Facility Location
- Competitive Ratio
- Online Optimization
- Facility Location Problem
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 32nd ACM Symposium on Parallelism in Algorithms and
Architectures
publication_identifier:
isbn:
- '9781450369350'
publication_status: published
status: public
title: The Online Multi-Commodity Facility Location Problem
type: conference
user_id: '39241'
year: '2020'
...
---
_id: '15631'
author:
- first_name: Björn
full_name: Feldkord, Björn
id: '22704'
last_name: Feldkord
citation:
ama: Feldkord B. Mobile Resource Allocation. Universität Paderborn; 2020.
doi:10.17619/UNIPB/1-869
apa: Feldkord, B. (2020). Mobile Resource Allocation. Universität Paderborn.
https://doi.org/10.17619/UNIPB/1-869
bibtex: '@book{Feldkord_2020, place={Universität Paderborn}, title={Mobile Resource
Allocation}, DOI={10.17619/UNIPB/1-869},
author={Feldkord, Björn}, year={2020} }'
chicago: Feldkord, Björn. Mobile Resource Allocation. Universität Paderborn,
2020. https://doi.org/10.17619/UNIPB/1-869.
ieee: B. Feldkord, Mobile Resource Allocation. Universität Paderborn, 2020.
mla: Feldkord, Björn. Mobile Resource Allocation. 2020, doi:10.17619/UNIPB/1-869.
short: B. Feldkord, Mobile Resource Allocation, Universität Paderborn, 2020.
date_created: 2020-01-23T14:20:25Z
date_updated: 2022-01-06T06:52:31Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.17619/UNIPB/1-869
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2020-01-24T08:19:38Z
date_updated: 2020-01-24T08:19:38Z
file_id: '15634'
file_name: DissertationFeldkord.pdf
file_size: 633652
relation: main_file
success: 1
file_date_updated: 2020-01-24T08:19:38Z
has_accepted_license: '1'
language:
- iso: eng
place: Universität Paderborn
project:
- _id: '1'
name: SFB 901
- _id: '2'
name: SFB 901 - Project Area A
- _id: '5'
name: SFB 901 - Subproject A1
status: public
supervisor:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
title: Mobile Resource Allocation
type: dissertation
user_id: '15415'
year: '2020'
...
---
_id: '12870'
author:
- first_name: Björn
full_name: Feldkord, Björn
id: '22704'
last_name: Feldkord
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- 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, Knollmann T, Malatyali M, Meyer auf der Heide F. Managing Multiple
Mobile Resources. In: Proceedings of the 17th Workshop on Approximation and
Online Algorithms (WAOA). Springer; 2019:120-137. doi:10.1007/978-3-030-39479-0_9'
apa: Feldkord, B., Knollmann, T., Malatyali, M., & Meyer auf der Heide, F. (2019).
Managing Multiple Mobile Resources. In Proceedings of the 17th Workshop on
Approximation and Online Algorithms (WAOA) (pp. 120–137). Springer. https://doi.org/10.1007/978-3-030-39479-0_9
bibtex: '@inproceedings{Feldkord_Knollmann_Malatyali_Meyer auf der Heide_2019, title={Managing
Multiple Mobile Resources}, DOI={10.1007/978-3-030-39479-0_9},
booktitle={Proceedings of the 17th Workshop on Approximation and Online Algorithms
(WAOA)}, publisher={Springer}, author={Feldkord, Björn and Knollmann, Till and
Malatyali, Manuel and Meyer auf der Heide, Friedhelm}, year={2019}, pages={120–137}
}'
chicago: Feldkord, Björn, Till Knollmann, Manuel Malatyali, and Friedhelm Meyer
auf der Heide. “Managing Multiple Mobile Resources.” In Proceedings of the
17th Workshop on Approximation and Online Algorithms (WAOA), 120–37. Springer,
2019. https://doi.org/10.1007/978-3-030-39479-0_9.
ieee: B. Feldkord, T. Knollmann, M. Malatyali, and F. Meyer auf der Heide, “Managing
Multiple Mobile Resources,” in Proceedings of the 17th Workshop on Approximation
and Online Algorithms (WAOA), 2019, pp. 120–137.
mla: Feldkord, Björn, et al. “Managing Multiple Mobile Resources.” Proceedings
of the 17th Workshop on Approximation and Online Algorithms (WAOA), Springer,
2019, pp. 120–37, doi:10.1007/978-3-030-39479-0_9.
short: 'B. Feldkord, T. Knollmann, M. Malatyali, F. Meyer auf der Heide, in: Proceedings
of the 17th Workshop on Approximation and Online Algorithms (WAOA), Springer,
2019, pp. 120–137.'
date_created: 2019-07-22T09:00:05Z
date_updated: 2022-01-06T06:51:20Z
department:
- _id: '63'
doi: 10.1007/978-3-030-39479-0_9
external_id:
arxiv:
- '1907.09834'
language:
- iso: eng
page: 120 - 137
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 17th Workshop on Approximation and Online Algorithms
(WAOA)
publication_status: published
publisher: Springer
status: public
title: Managing Multiple Mobile Resources
type: conference
user_id: '22704'
year: '2019'
...
---
_id: '13873'
article_number: '14'
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. ACM Transactions
on Parallel Computing (TOPC). 2019;6(3). doi:10.1145/3364204
apa: Feldkord, B., & Meyer auf der Heide, F. (2019). The Mobile Server Problem.
ACM Transactions on Parallel Computing (TOPC), 6(3). https://doi.org/10.1145/3364204
bibtex: '@article{Feldkord_Meyer auf der Heide_2019, title={The Mobile Server Problem},
volume={6}, DOI={10.1145/3364204},
number={314}, journal={ACM Transactions on Parallel Computing (TOPC)}, author={Feldkord,
Björn and Meyer auf der Heide, Friedhelm}, year={2019} }'
chicago: Feldkord, Björn, and Friedhelm Meyer auf der Heide. “The Mobile Server
Problem.” ACM Transactions on Parallel Computing (TOPC) 6, no. 3 (2019).
https://doi.org/10.1145/3364204.
ieee: B. Feldkord and F. Meyer auf der Heide, “The Mobile Server Problem,” ACM
Transactions on Parallel Computing (TOPC), vol. 6, no. 3, 2019.
mla: Feldkord, Björn, and Friedhelm Meyer auf der Heide. “The Mobile Server Problem.”
ACM Transactions on Parallel Computing (TOPC), vol. 6, no. 3, 14, 2019,
doi:10.1145/3364204.
short: B. Feldkord, F. Meyer auf der Heide, ACM Transactions on Parallel Computing
(TOPC) 6 (2019).
date_created: 2019-10-16T07:06:22Z
date_updated: 2022-01-06T06:51:46Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1145/3364204
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2020-01-24T08:12:58Z
date_updated: 2020-01-24T08:12:58Z
file_id: '15632'
file_name: DissertationFeldkord.pdf
file_size: 633652
relation: main_file
success: 1
file_date_updated: 2020-01-24T08:12:58Z
has_accepted_license: '1'
intvolume: ' 6'
issue: '3'
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: ACM Transactions on Parallel Computing (TOPC)
publication_status: published
status: public
title: The Mobile Server Problem
type: journal_article
user_id: '15504'
volume: 6
year: '2019'
...
---
_id: '2484'
abstract:
- lang: eng
text: We study the classic bin packing problem in a fully-dynamic setting, where
new items can arrive and old items may depart. We want algorithms with low asymptotic
competitive ratio while repacking items sparingly between updates. Formally, each
item i has a movement cost c_i >= 0, and we want to use alpha * OPT bins and incur
a movement cost gamma * c_i, either in the worst case, or in an amortized sense,
for alpha, gamma as small as possible. We call gamma the recourse of the algorithm.
This is motivated by cloud storage applications, where fully-dynamic bin packing
models the problem of data backup to minimize the number of disks used, as well
as communication incurred in moving file backups between disks. Since the set
of files changes over time, we could recompute a solution periodically from scratch,
but this would give a high number of disk rewrites, incurring a high energy cost
and possible wear and tear of the disks. In this work, we present optimal tradeoffs
between number of bins used and number of items repacked, as well as natural extensions
of the latter measure.
author:
- first_name: Björn
full_name: Feldkord, Björn
id: '22704'
last_name: Feldkord
- first_name: Matthias
full_name: Feldotto, Matthias
id: '14052'
last_name: Feldotto
orcid: 0000-0003-1348-6516
- first_name: Anupam
full_name: Gupta, Anupam
last_name: Gupta
- first_name: Guru
full_name: Guruganesh, Guru
last_name: Guruganesh
- first_name: 'Amit '
full_name: 'Kumar, Amit '
last_name: Kumar
- first_name: Sören
full_name: Riechers, Sören
last_name: Riechers
- first_name: David
full_name: Wajc, David
last_name: Wajc
citation:
ama: 'Feldkord B, Feldotto M, Gupta A, et al. Fully-Dynamic Bin Packing with Little
Repacking. In: Chatzigiannakis I, Kaklamanis C, Marx D, Sannella D, eds. 45th
International Colloquium on Automata, Languages, and Programming (ICALP 2018).
Vol 107. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl,
Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik; 2018:51:1-51:24. doi:10.4230/LIPIcs.ICALP.2018.51'
apa: 'Feldkord, B., Feldotto, M., Gupta, A., Guruganesh, G., Kumar, A., Riechers,
S., & Wajc, D. (2018). Fully-Dynamic Bin Packing with Little Repacking. In
I. Chatzigiannakis, C. Kaklamanis, D. Marx, & D. Sannella (Eds.), 45th
International Colloquium on Automata, Languages, and Programming (ICALP 2018)
(Vol. 107, pp. 51:1-51:24). Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum
fuer Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2018.51'
bibtex: '@inproceedings{Feldkord_Feldotto_Gupta_Guruganesh_Kumar_Riechers_Wajc_2018,
place={Dagstuhl, Germany}, series={Leibniz International Proceedings in Informatics
(LIPIcs)}, title={Fully-Dynamic Bin Packing with Little Repacking}, volume={107},
DOI={10.4230/LIPIcs.ICALP.2018.51},
booktitle={45th International Colloquium on Automata, Languages, and Programming
(ICALP 2018)}, publisher={Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
author={Feldkord, Björn and Feldotto, Matthias and Gupta, Anupam and Guruganesh,
Guru and Kumar, Amit and Riechers, Sören and Wajc, David}, editor={Chatzigiannakis,
Ioannis and Kaklamanis, Christos and Marx, Dániel and Sannella, DonaldEditors},
year={2018}, pages={51:1-51:24}, collection={Leibniz International Proceedings
in Informatics (LIPIcs)} }'
chicago: 'Feldkord, Björn, Matthias Feldotto, Anupam Gupta, Guru Guruganesh, Amit Kumar,
Sören Riechers, and David Wajc. “Fully-Dynamic Bin Packing with Little Repacking.”
In 45th International Colloquium on Automata, Languages, and Programming (ICALP
2018), edited by Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx,
and Donald Sannella, 107:51:1-51:24. Leibniz International Proceedings in Informatics
(LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik,
2018. https://doi.org/10.4230/LIPIcs.ICALP.2018.51.'
ieee: B. Feldkord et al., “Fully-Dynamic Bin Packing with Little Repacking,”
in 45th International Colloquium on Automata, Languages, and Programming (ICALP
2018), Prag, 2018, vol. 107, pp. 51:1-51:24.
mla: Feldkord, Björn, et al. “Fully-Dynamic Bin Packing with Little Repacking.”
45th International Colloquium on Automata, Languages, and Programming (ICALP
2018), edited by Ioannis Chatzigiannakis et al., vol. 107, Schloss Dagstuhl--Leibniz-Zentrum
fuer Informatik, 2018, pp. 51:1-51:24, doi:10.4230/LIPIcs.ICALP.2018.51.
short: 'B. Feldkord, M. Feldotto, A. Gupta, G. Guruganesh, A. Kumar, S. Riechers,
D. Wajc, in: I. Chatzigiannakis, C. Kaklamanis, D. Marx, D. Sannella (Eds.), 45th
International Colloquium on Automata, Languages, and Programming (ICALP 2018),
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018, pp.
51:1-51:24.'
conference:
end_date: 2018-07-13
location: Prag
name: 45th International Colloquium on Automata, Languages, and Programming (ICALP
2018)
start_date: 2018-07-10
date_created: 2018-04-24T15:21:56Z
date_updated: 2022-01-06T06:56:39Z
ddc:
- '000'
department:
- _id: '541'
- _id: '63'
doi: 10.4230/LIPIcs.ICALP.2018.51
editor:
- first_name: Ioannis
full_name: Chatzigiannakis, Ioannis
last_name: Chatzigiannakis
- first_name: Christos
full_name: Kaklamanis, Christos
last_name: Kaklamanis
- first_name: Dániel
full_name: Marx, Dániel
last_name: Marx
- first_name: Donald
full_name: Sannella, Donald
last_name: Sannella
external_id:
arxiv:
- '1711.01231'
file:
- access_level: closed
content_type: application/pdf
creator: feldi
date_created: 2018-10-31T16:58:18Z
date_updated: 2018-10-31T16:58:18Z
file_id: '5227'
file_name: LIPIcs-ICALP-2018-51.pdf
file_size: 723824
relation: main_file
success: 1
file_date_updated: 2018-10-31T16:58:18Z
has_accepted_license: '1'
intvolume: ' 107'
language:
- iso: eng
page: 51:1-51:24
place: Dagstuhl, Germany
project:
- _id: '1'
name: SFB 901
- _id: '2'
name: SFB 901 - Project Area A
- _id: '4'
name: SFB 901 - Project Area C
- _id: '5'
name: SFB 901 - Subproject A1
- _id: '7'
name: SFB 901 - Subproject A3
- _id: '16'
name: SFB 901 - Subproject C4
publication: 45th International Colloquium on Automata, Languages, and Programming
(ICALP 2018)
publication_identifier:
isbn:
- 978-3-95977-076-7
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: Fully-Dynamic Bin Packing with Little Repacking
type: conference
user_id: '14052'
volume: 107
year: '2018'
...
---
_id: '2485'
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. Online Facility Location with Mobile Facilities.
In: Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA). ACM; 2018:373-381. doi:10.1145/3210377.3210389'
apa: 'Feldkord, B., & Meyer auf der Heide, F. (2018). Online Facility Location
with Mobile Facilities. In Proceedings of the 30th ACM Symposium on Parallelism
in Algorithms and Architectures (SPAA) (pp. 373–381). Wien: ACM. https://doi.org/10.1145/3210377.3210389'
bibtex: '@inproceedings{Feldkord_Meyer auf der Heide_2018, title={Online Facility
Location with Mobile Facilities}, DOI={10.1145/3210377.3210389},
booktitle={Proceedings of the 30th ACM Symposium on Parallelism in Algorithms
and Architectures (SPAA)}, publisher={ACM}, author={Feldkord, Björn and Meyer
auf der Heide, Friedhelm}, year={2018}, pages={373–381} }'
chicago: Feldkord, Björn, and Friedhelm Meyer auf der Heide. “Online Facility Location
with Mobile Facilities.” In Proceedings of the 30th ACM Symposium on Parallelism
in Algorithms and Architectures (SPAA), 373–81. ACM, 2018. https://doi.org/10.1145/3210377.3210389.
ieee: B. Feldkord and F. Meyer auf der Heide, “Online Facility Location with Mobile
Facilities,” in Proceedings of the 30th ACM Symposium on Parallelism in Algorithms
and Architectures (SPAA), Wien, 2018, pp. 373–381.
mla: Feldkord, Björn, and Friedhelm Meyer auf der Heide. “Online Facility Location
with Mobile Facilities.” Proceedings of the 30th ACM Symposium on Parallelism
in Algorithms and Architectures (SPAA), ACM, 2018, pp. 373–81, doi:10.1145/3210377.3210389.
short: 'B. Feldkord, F. Meyer auf der Heide, in: Proceedings of the 30th ACM Symposium
on Parallelism in Algorithms and Architectures (SPAA), ACM, 2018, pp. 373–381.'
conference:
location: Wien
name: SPAA'18
date_created: 2018-04-25T08:49:43Z
date_updated: 2022-01-06T06:56:39Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1145/3210377.3210389
file:
- access_level: closed
content_type: application/pdf
creator: ups
date_created: 2018-11-02T14:42:33Z
date_updated: 2018-11-02T14:42:33Z
file_id: '5280'
file_name: p373-feldkord.pdf
file_size: 1207546
relation: main_file
success: 1
file_date_updated: 2018-11-02T14:42:33Z
has_accepted_license: '1'
language:
- iso: eng
page: '373 - 381 '
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 30th ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA)
publication_status: published
publisher: ACM
status: public
title: Online Facility Location with Mobile Facilities
type: conference
user_id: '477'
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: '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: '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: '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: '149'
abstract:
- lang: eng
text: 'In this paper we consider a strategic variant of the online facility location
problem. Given is a graph in which each node serves two roles: it is a strategic
client stating requests as well as a potential location for a facility. In each
time step one client states a request which induces private costs equal to the
distance to the closest facility. Before serving, the clients may collectively
decide to open new facilities, sharing the corresponding price. Instead of optimizing
the global costs, each client acts selfishly. The prices of new facilities vary
between nodes and also change over time, but are always bounded by some fixed
value α. Both the requests as well as the facility prices are given by an online
sequence and are not known in advance.We characterize the optimal strategies of
the clients and analyze their overall performance in comparison to a centralized
offline solution. If all players optimize their own competitiveness, the global
performance of the system is O(√α⋅α) times worse than the offline optimum. A restriction
to a natural subclass of strategies improves this result to O(α). We also show
that for fixed facility costs, we can find strategies such that this bound further
improves to O(√α).'
author:
- first_name: Maximilian
full_name: Drees, Maximilian
last_name: Drees
- first_name: Björn
full_name: Feldkord, Björn
id: '22704'
last_name: Feldkord
- first_name: Alexander
full_name: Skopalik, Alexander
id: '40384'
last_name: Skopalik
citation:
ama: 'Drees M, Feldkord B, Skopalik A. Strategic Online Facility Location. In: Proceedings
of the 10th Annual International Conference on Combinatorial Optimization and
Applications (COCOA). LNCS. ; 2016:593--607. doi:10.1007/978-3-319-48749-6_43'
apa: Drees, M., Feldkord, B., & Skopalik, A. (2016). Strategic Online Facility
Location. In Proceedings of the 10th Annual International Conference on Combinatorial
Optimization and Applications (COCOA) (pp. 593--607). https://doi.org/10.1007/978-3-319-48749-6_43
bibtex: '@inproceedings{Drees_Feldkord_Skopalik_2016, series={LNCS}, title={Strategic
Online Facility Location}, DOI={10.1007/978-3-319-48749-6_43},
booktitle={Proceedings of the 10th Annual International Conference on Combinatorial
Optimization and Applications (COCOA)}, author={Drees, Maximilian and Feldkord,
Björn and Skopalik, Alexander}, year={2016}, pages={593--607}, collection={LNCS}
}'
chicago: Drees, Maximilian, Björn Feldkord, and Alexander Skopalik. “Strategic Online
Facility Location.” In Proceedings of the 10th Annual International Conference
on Combinatorial Optimization and Applications (COCOA), 593--607. LNCS, 2016.
https://doi.org/10.1007/978-3-319-48749-6_43.
ieee: M. Drees, B. Feldkord, and A. Skopalik, “Strategic Online Facility Location,”
in Proceedings of the 10th Annual International Conference on Combinatorial
Optimization and Applications (COCOA), 2016, pp. 593--607.
mla: Drees, Maximilian, et al. “Strategic Online Facility Location.” Proceedings
of the 10th Annual International Conference on Combinatorial Optimization and
Applications (COCOA), 2016, pp. 593--607, doi:10.1007/978-3-319-48749-6_43.
short: 'M. Drees, B. Feldkord, A. Skopalik, in: Proceedings of the 10th Annual International
Conference on Combinatorial Optimization and Applications (COCOA), 2016, pp. 593--607.'
date_created: 2017-10-17T12:41:21Z
date_updated: 2022-01-06T06:52:10Z
ddc:
- '040'
department:
- _id: '63'
- _id: '541'
doi: 10.1007/978-3-319-48749-6_43
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-21T12:55:43Z
date_updated: 2018-03-21T12:55:43Z
file_id: '1553'
file_name: 149-chp_3A10.1007_2F978-3-319-48749-6_43.pdf
file_size: 236253
relation: main_file
success: 1
file_date_updated: 2018-03-21T12:55:43Z
has_accepted_license: '1'
language:
- iso: eng
page: 593--607
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '7'
name: SFB 901 - Subproject A3
- _id: '2'
name: SFB 901 - Project Area A
publication: Proceedings of the 10th Annual International Conference on Combinatorial
Optimization and Applications (COCOA)
series_title: LNCS
status: public
title: Strategic Online Facility Location
type: conference
user_id: '477'
year: '2016'
...
---
_id: '391'
author:
- first_name: Björn
full_name: Feldkord, Björn
id: '22704'
last_name: Feldkord
citation:
ama: Feldkord B. On Variants of the Page Migration Problem. Universität Paderborn;
2014.
apa: Feldkord, B. (2014). On Variants of the Page Migration Problem. Universität
Paderborn.
bibtex: '@book{Feldkord_2014, title={On Variants of the Page Migration Problem},
publisher={Universität Paderborn}, author={Feldkord, Björn}, year={2014} }'
chicago: Feldkord, Björn. On Variants of the Page Migration Problem. Universität
Paderborn, 2014.
ieee: B. Feldkord, On Variants of the Page Migration Problem. Universität
Paderborn, 2014.
mla: Feldkord, Björn. On Variants of the Page Migration Problem. Universität
Paderborn, 2014.
short: B. Feldkord, On Variants of the Page Migration Problem, Universität Paderborn,
2014.
date_created: 2017-10-17T12:42:08Z
date_updated: 2022-01-06T06:59:54Z
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: On Variants of the Page Migration Problem
type: mastersthesis
user_id: '477'
year: '2014'
...
---
_id: '600'
author:
- first_name: Björn
full_name: Feldkord, Björn
id: '22704'
last_name: Feldkord
citation:
ama: Feldkord B. Lokale Swaps und überholte Informationen in Basic Network Creation
Games. Universität Paderborn; 2012.
apa: Feldkord, B. (2012). Lokale Swaps und überholte Informationen in Basic Network
Creation Games. Universität Paderborn.
bibtex: '@book{Feldkord_2012, title={Lokale Swaps und überholte Informationen in
Basic Network Creation Games}, publisher={Universität Paderborn}, author={Feldkord,
Björn}, year={2012} }'
chicago: Feldkord, Björn. Lokale Swaps und überholte Informationen in Basic Network
Creation Games. Universität Paderborn, 2012.
ieee: B. Feldkord, Lokale Swaps und überholte Informationen in Basic Network
Creation Games. Universität Paderborn, 2012.
mla: Feldkord, Björn. Lokale Swaps und überholte Informationen in Basic Network
Creation Games. Universität Paderborn, 2012.
short: B. Feldkord, Lokale Swaps und überholte Informationen in Basic Network Creation
Games, Universität Paderborn, 2012.
date_created: 2017-10-17T12:42:49Z
date_updated: 2022-01-06T07:02:49Z
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: Lokale Swaps und überholte Informationen in Basic Network Creation Games
type: bachelorsthesis
user_id: '477'
year: '2012'
...