---
_id: '13868'
author:
- first_name: Simon
full_name: Pukrop, Simon
id: '44428'
last_name: Pukrop
- first_name: Alexander
full_name: Mäcker, Alexander
id: '13536'
last_name: Mäcker
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Pukrop S, Mäcker A, Meyer auf der Heide F. Approximating Weighted Completion
Time for Order Scheduling with Setup Times. In: Proceedings of the 46th International
Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM).
; 2020.'
apa: Pukrop, S., Mäcker, A., & Meyer auf der Heide, F. (2020). Approximating
Weighted Completion Time for Order Scheduling with Setup Times. In Proceedings
of the 46th International Conference on Current Trends in Theory and Practice
of Computer Science (SOFSEM).
bibtex: '@inproceedings{Pukrop_Mäcker_Meyer auf der Heide_2020, title={Approximating
Weighted Completion Time for Order Scheduling with Setup Times}, booktitle={Proceedings
of the 46th International Conference on Current Trends in Theory and Practice
of Computer Science (SOFSEM)}, author={Pukrop, Simon and Mäcker, Alexander and
Meyer auf der Heide, Friedhelm}, year={2020} }'
chicago: Pukrop, Simon, Alexander Mäcker, and Friedhelm Meyer auf der Heide. “Approximating
Weighted Completion Time for Order Scheduling with Setup Times.” In Proceedings
of the 46th International Conference on Current Trends in Theory and Practice
of Computer Science (SOFSEM), 2020.
ieee: S. Pukrop, A. Mäcker, and F. Meyer auf der Heide, “Approximating Weighted
Completion Time for Order Scheduling with Setup Times,” in Proceedings of the
46th International Conference on Current Trends in Theory and Practice of Computer
Science (SOFSEM), 2020.
mla: Pukrop, Simon, et al. “Approximating Weighted Completion Time for Order Scheduling
with Setup Times.” Proceedings of the 46th International Conference on Current
Trends in Theory and Practice of Computer Science (SOFSEM), 2020.
short: 'S. Pukrop, A. Mäcker, F. Meyer auf der Heide, in: Proceedings of the 46th
International Conference on Current Trends in Theory and Practice of Computer
Science (SOFSEM), 2020.'
date_created: 2019-10-15T12:19:49Z
date_updated: 2022-01-06T06:51:45Z
department:
- _id: '63'
language:
- iso: eng
project:
- _id: '4'
name: SFB 901 - Project Area C
- _id: '1'
name: SFB 901
- _id: '16'
name: SFB 901 - Subproject C4
publication: Proceedings of the 46th International Conference on Current Trends in
Theory and Practice of Computer Science (SOFSEM)
status: public
title: Approximating Weighted Completion Time for Order Scheduling with Setup Times
type: conference
user_id: '44428'
year: '2020'
...
---
_id: '8866'
author:
- first_name: Klaus
full_name: Jansen, Klaus
last_name: Jansen
- first_name: Marten
full_name: Maack, Marten
last_name: Maack
- first_name: Alexander
full_name: Mäcker, Alexander
id: '13536'
last_name: Mäcker
citation:
ama: 'Jansen K, Maack M, Mäcker A. Scheduling on (Un-)Related Machines with Setup
Times. In: Proceedings of the 33rd IEEE International Parallel and Distributed
Processing Symposium (IPDPS). IEEE; 2019:145-154.'
apa: Jansen, K., Maack, M., & Mäcker, A. (2019). Scheduling on (Un-)Related
Machines with Setup Times. In Proceedings of the 33rd IEEE International Parallel
and Distributed Processing Symposium (IPDPS) (pp. 145–154). IEEE.
bibtex: '@inproceedings{Jansen_Maack_Mäcker_2019, title={Scheduling on (Un-)Related
Machines with Setup Times}, booktitle={Proceedings of the 33rd IEEE International
Parallel and Distributed Processing Symposium (IPDPS)}, publisher={IEEE}, author={Jansen,
Klaus and Maack, Marten and Mäcker, Alexander}, year={2019}, pages={145–154} }'
chicago: Jansen, Klaus, Marten Maack, and Alexander Mäcker. “Scheduling on (Un-)Related
Machines with Setup Times.” In Proceedings of the 33rd IEEE International Parallel
and Distributed Processing Symposium (IPDPS), 145–54. IEEE, 2019.
ieee: K. Jansen, M. Maack, and A. Mäcker, “Scheduling on (Un-)Related Machines with
Setup Times,” in Proceedings of the 33rd IEEE International Parallel and Distributed
Processing Symposium (IPDPS), 2019, pp. 145–154.
mla: Jansen, Klaus, et al. “Scheduling on (Un-)Related Machines with Setup Times.”
Proceedings of the 33rd IEEE International Parallel and Distributed Processing
Symposium (IPDPS), IEEE, 2019, pp. 145–54.
short: 'K. Jansen, M. Maack, A. Mäcker, in: Proceedings of the 33rd IEEE International
Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2019, pp. 145–154.'
date_created: 2019-04-09T11:28:46Z
date_updated: 2022-01-06T07:04:04Z
department:
- _id: '63'
language:
- iso: eng
page: 145 - 154
project:
- _id: '4'
name: SFB 901 - Project Area C
- _id: '16'
name: SFB 901 - Subproject C4
- _id: '1'
name: SFB 901
publication: Proceedings of the 33rd IEEE International Parallel and Distributed Processing
Symposium (IPDPS)
publisher: IEEE
status: public
title: Scheduling on (Un-)Related Machines with Setup Times
type: conference
user_id: '13536'
year: '2019'
...
---
_id: '14851'
author:
- first_name: Alexander
full_name: Mäcker, Alexander
id: '13536'
last_name: Mäcker
citation:
ama: Mäcker A. On Scheduling with Setup Times. Universität Paderborn; 2019.
doi:10.17619/UNIPB/1-828
apa: Mäcker, A. (2019). On Scheduling with Setup Times. Universität Paderborn.
https://doi.org/10.17619/UNIPB/1-828
bibtex: '@book{Mäcker_2019, place={Universität Paderborn}, title={On Scheduling
with Setup Times}, DOI={10.17619/UNIPB/1-828},
author={Mäcker, Alexander}, year={2019} }'
chicago: Mäcker, Alexander. On Scheduling with Setup Times. Universität Paderborn,
2019. https://doi.org/10.17619/UNIPB/1-828.
ieee: A. Mäcker, On Scheduling with Setup Times. Universität Paderborn, 2019.
mla: Mäcker, Alexander. On Scheduling with Setup Times. 2019, doi:10.17619/UNIPB/1-828.
short: A. Mäcker, On Scheduling with Setup Times, Universität Paderborn, 2019.
date_created: 2019-11-07T14:17:05Z
date_updated: 2022-01-06T06:52:08Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.17619/UNIPB/1-828
language:
- iso: eng
place: Universität Paderborn
project:
- _id: '1'
name: SFB 901
- _id: '16'
name: SFB 901 - Subproject C4
- _id: '4'
name: SFB 901 - Project Area C
related_material:
link:
- relation: confirmation
url: https://doi.org/10.17619/UNIPB/1-828
status: public
supervisor:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
title: On Scheduling with Setup Times
type: dissertation
user_id: '15415'
year: '2019'
...
---
_id: '3551'
author:
- first_name: Jürgen
full_name: König, Jürgen
id: '22358'
last_name: König
- first_name: Alexander
full_name: Mäcker, Alexander
id: '13536'
last_name: Mäcker
- 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: König J, Mäcker A, Meyer auf der Heide F, Riechers S. Scheduling with interjob
communication on parallel processors. Journal of Combinatorial Optimization.
2018;36(4):1356-1379. doi:10.1007/s10878-018-0325-3
apa: König, J., Mäcker, A., Meyer auf der Heide, F., & Riechers, S. (2018).
Scheduling with interjob communication on parallel processors. Journal of Combinatorial
Optimization, 36(4), 1356–1379. https://doi.org/10.1007/s10878-018-0325-3
bibtex: '@article{König_Mäcker_Meyer auf der Heide_Riechers_2018, title={Scheduling
with interjob communication on parallel processors}, volume={36}, DOI={10.1007/s10878-018-0325-3},
number={4}, journal={Journal of Combinatorial Optimization}, author={König, Jürgen
and Mäcker, Alexander and Meyer auf der Heide, Friedhelm and Riechers, Sören},
year={2018}, pages={1356–1379} }'
chicago: 'König, Jürgen, Alexander Mäcker, Friedhelm Meyer auf der Heide, and Sören
Riechers. “Scheduling with Interjob Communication on Parallel Processors.” Journal
of Combinatorial Optimization 36, no. 4 (2018): 1356–79. https://doi.org/10.1007/s10878-018-0325-3.'
ieee: J. König, A. Mäcker, F. Meyer auf der Heide, and S. Riechers, “Scheduling
with interjob communication on parallel processors,” Journal of Combinatorial
Optimization, vol. 36, no. 4, pp. 1356–1379, 2018.
mla: König, Jürgen, et al. “Scheduling with Interjob Communication on Parallel Processors.”
Journal of Combinatorial Optimization, vol. 36, no. 4, 2018, pp. 1356–79,
doi:10.1007/s10878-018-0325-3.
short: J. König, A. Mäcker, F. Meyer auf der Heide, S. Riechers, Journal of Combinatorial
Optimization 36 (2018) 1356–1379.
date_created: 2018-07-13T09:57:48Z
date_updated: 2022-01-06T06:59:24Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1007/s10878-018-0325-3
file:
- access_level: closed
content_type: application/pdf
creator: ups
date_created: 2018-11-02T15:20:24Z
date_updated: 2018-11-02T15:20:24Z
file_id: '5299'
file_name: SchedulingWithInterjobCommunic.pdf
file_size: 745708
relation: main_file
success: 1
file_date_updated: 2018-11-02T15:20:24Z
has_accepted_license: '1'
intvolume: ' 36'
issue: '4'
language:
- iso: eng
page: 1356-1379
project:
- _id: '16'
name: SFB 901 - Subproject C4
- _id: '1'
name: SFB 901
- _id: '4'
name: SFB 901 - Project Area C
publication: Journal of Combinatorial Optimization
status: public
title: Scheduling with interjob communication on parallel processors
type: journal_article
user_id: '477'
volume: 36
year: '2018'
...
---
_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: '59'
abstract:
- lang: eng
text: We consider a scheduling problem on $m$ identical processors sharing an arbitrarily
divisible resource. In addition to assigning jobs to processors, the scheduler
must distribute the resource among the processors (e.g., for three processors
in shares of 20\%, 15\%, and 65\%) and adjust this distribution over time. Each
job $j$ comes with a size $p_j \in \mathbb{R}$ and a resource requirement $r_j
> 0$. Jobs do not benefit when receiving a share larger than $r_j$ of the resource.
But providing them with a fraction of the resource requirement causes a linear
decrease in the processing efficiency. We seek a (non-preemptive) job and resource
assignment minimizing the makespan.Our main result is an efficient approximation
algorithm which achieves an approximation ratio of $2 + 1/(m-2)$. It can be improved
to an (asymptotic) ratio of $1 + 1/(m-1)$ if all jobs have unit size. Our algorithms
also imply new results for a well-known bin packing problem with splittable items
and a restricted number of allowed item parts per bin.Based upon the above solution,
we also derive an approximation algorithm with similar guarantees for a setting
in which we introduce so-called tasks each containing several jobs and where we
are interested in the average completion time of tasks (a task is completed when
all its jobs are completed).
author:
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Alexander
full_name: Mäcker, Alexander
id: '13536'
last_name: Mäcker
- first_name: Sören
full_name: Riechers, Sören
last_name: Riechers
- first_name: Alexander
full_name: Skopalik, Alexander
id: '40384'
last_name: Skopalik
citation:
ama: 'Kling P, Mäcker A, Riechers S, Skopalik A. Sharing is Caring: Multiprocessor
Scheduling with a Sharable Resource. In: Proceedings of the 29th ACM Symposium
on Parallelism in Algorithms and Architectures (SPAA). ; 2017:123--132. doi:10.1145/3087556.3087578'
apa: 'Kling, P., Mäcker, A., Riechers, S., & Skopalik, A. (2017). Sharing is
Caring: Multiprocessor Scheduling with a Sharable Resource. In Proceedings
of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
(pp. 123--132). https://doi.org/10.1145/3087556.3087578'
bibtex: '@inproceedings{Kling_Mäcker_Riechers_Skopalik_2017, title={Sharing is Caring:
Multiprocessor Scheduling with a Sharable Resource}, DOI={10.1145/3087556.3087578},
booktitle={Proceedings of the 29th ACM Symposium on Parallelism in Algorithms
and Architectures (SPAA)}, author={Kling, Peter and Mäcker, Alexander and Riechers,
Sören and Skopalik, Alexander}, year={2017}, pages={123--132} }'
chicago: 'Kling, Peter, Alexander Mäcker, Sören Riechers, and Alexander Skopalik.
“Sharing Is Caring: Multiprocessor Scheduling with a Sharable Resource.” In Proceedings
of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA),
123--132, 2017. https://doi.org/10.1145/3087556.3087578.'
ieee: 'P. Kling, A. Mäcker, S. Riechers, and A. Skopalik, “Sharing is Caring: Multiprocessor
Scheduling with a Sharable Resource,” in Proceedings of the 29th ACM Symposium
on Parallelism in Algorithms and Architectures (SPAA), 2017, pp. 123--132.'
mla: 'Kling, Peter, et al. “Sharing Is Caring: Multiprocessor Scheduling with a
Sharable Resource.” Proceedings of the 29th ACM Symposium on Parallelism in
Algorithms and Architectures (SPAA), 2017, pp. 123--132, doi:10.1145/3087556.3087578.'
short: 'P. Kling, A. Mäcker, S. Riechers, A. Skopalik, in: Proceedings of the 29th
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2017, pp.
123--132.'
date_created: 2017-10-17T12:41:02Z
date_updated: 2022-01-06T07:02:46Z
ddc:
- '040'
department:
- _id: '63'
- _id: '541'
doi: 10.1145/3087556.3087578
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-21T13:17:33Z
date_updated: 2018-03-21T13:17:33Z
file_id: '1578'
file_name: 59-progress.pdf
file_size: 784867
relation: main_file
success: 1
file_date_updated: 2018-03-21T13:17:33Z
has_accepted_license: '1'
language:
- iso: eng
page: 123--132
project:
- _id: '1'
name: SFB 901
- _id: '7'
name: SFB 901 - Subprojekt A3
- _id: '4'
name: SFB 901 - Project Area C
- _id: '16'
name: SFB 901 - Subproject C4
- _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: 'Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource'
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: '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: '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'
...
---
_id: '157'
abstract:
- lang: eng
text: Consider a scheduling problem in which a set of jobs with interjob communication,
canonically represented by a weighted tree, needs to be scheduled on m parallel
processors interconnected by a shared communication channel. In each time step,
we may allow any processed job to use a certain capacity of the channel in order
to satisfy (parts of) its communication demands to adjacent jobs processed in
parallel. The goal is to find a schedule that minimizes the makespan and in which
communication demands of all jobs are satisfied.We show that this problem is NP-hard
in the strong sense even if the number of processors and the maximum degree of
the underlying tree is constant.Consequently, we design and analyze simple approximation
algorithms with asymptotic approximation ratio 2-2/m in case of paths and a ratio
of 5/2 in case of arbitrary trees.
author:
- first_name: Jürgen
full_name: König, Jürgen
last_name: König
- first_name: Alexander
full_name: Mäcker, Alexander
id: '13536'
last_name: Mäcker
- 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: 'König J, Mäcker A, Meyer auf der Heide F, Riechers S. Scheduling with Interjob
Communication on Parallel Processors. In: Proceedings of the 10th Annual International
Conference on Combinatorial Optimization and Applications (COCOA). LNCS. ;
2016:563--577. doi:10.1007/978-3-319-48749-6_41'
apa: König, J., Mäcker, A., Meyer auf der Heide, F., & Riechers, S. (2016).
Scheduling with Interjob Communication on Parallel Processors. In Proceedings
of the 10th Annual International Conference on Combinatorial Optimization and
Applications (COCOA) (pp. 563--577). https://doi.org/10.1007/978-3-319-48749-6_41
bibtex: '@inproceedings{König_Mäcker_Meyer auf der Heide_Riechers_2016, series={LNCS},
title={Scheduling with Interjob Communication on Parallel Processors}, DOI={10.1007/978-3-319-48749-6_41},
booktitle={Proceedings of the 10th Annual International Conference on Combinatorial
Optimization and Applications (COCOA)}, author={König, Jürgen and Mäcker, Alexander
and Meyer auf der Heide, Friedhelm and Riechers, Sören}, year={2016}, pages={563--577},
collection={LNCS} }'
chicago: König, Jürgen, Alexander Mäcker, Friedhelm Meyer auf der Heide, and Sören
Riechers. “Scheduling with Interjob Communication on Parallel Processors.” In
Proceedings of the 10th Annual International Conference on Combinatorial Optimization
and Applications (COCOA), 563--577. LNCS, 2016. https://doi.org/10.1007/978-3-319-48749-6_41.
ieee: J. König, A. Mäcker, F. Meyer auf der Heide, and S. Riechers, “Scheduling
with Interjob Communication on Parallel Processors,” in Proceedings of the
10th Annual International Conference on Combinatorial Optimization and Applications
(COCOA), 2016, pp. 563--577.
mla: König, Jürgen, et al. “Scheduling with Interjob Communication on Parallel Processors.”
Proceedings of the 10th Annual International Conference on Combinatorial Optimization
and Applications (COCOA), 2016, pp. 563--577, doi:10.1007/978-3-319-48749-6_41.
short: 'J. König, A. Mäcker, F. Meyer auf der Heide, S. Riechers, in: Proceedings
of the 10th Annual International Conference on Combinatorial Optimization and
Applications (COCOA), 2016, pp. 563--577.'
date_created: 2017-10-17T12:41:22Z
date_updated: 2022-01-06T06:52:32Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-319-48749-6_41
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-21T12:50:29Z
date_updated: 2018-03-21T12:50:29Z
file_id: '1549'
file_name: 157-chp_3A10.1007_2F978-3-319-48749-6_41.pdf
file_size: 753147
relation: main_file
success: 1
file_date_updated: 2018-03-21T12:50:29Z
has_accepted_license: '1'
page: 563--577
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)
series_title: LNCS
status: public
title: Scheduling with Interjob Communication on Parallel Processors
type: conference
user_id: '15504'
year: '2016'
...
---
_id: '16396'
abstract:
- lang: eng
text: "We consider a scheduling problem where machines need to be rented from the\r\ncloud
in order to process jobs. There are two types of machines available which\r\ncan
be rented for machine-type dependent prices and for arbitrary durations.\r\nHowever,
a machine-type dependent setup time is required before a machine is\r\navailable
for processing. Jobs arrive online over time, have machine-type\r\ndependent sizes
and have individual deadlines. The objective is to rent\r\nmachines and schedule
jobs so as to meet all deadlines while minimizing the\r\nrental cost.\r\n Since
we observe the slack of jobs to have a fundamental influence on the\r\ncompetitiveness,
we study the model when instances are parameterized by their\r\n(minimum) slack.
An instance is called to have a slack of $\\beta$ if, for all\r\njobs, the difference
between the job's release time and the latest point in\r\ntime at which it needs
to be started is at least $\\beta$. While for $\\beta < s$\r\nno finite competitiveness
is possible, our main result is an\r\n$O(\\frac{c}{\\varepsilon} + \\frac{1}{\\varepsilon^3})$-competitive
online\r\nalgorithm for $\\beta = (1+\\varepsilon)s$ with $\\frac{1}{s} \\leq
\\varepsilon\r\n\\leq 1$, where $s$ and $c$ denotes the largest setup time and
the cost ratio of\r\nthe machine-types, respectively. It is complemented by a
lower bound of\r\n$\\Omega(\\frac{c}{\\varepsilon})$."
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. arXiv:160901184. 2016.
apa: Mäcker, A., Malatyali, M., Meyer auf der Heide, F., & Riechers, S. (2016).
Cost-efficient Scheduling on Machines from the Cloud. ArXiv:1609.01184.
bibtex: '@article{Mäcker_Malatyali_Meyer auf der Heide_Riechers_2016, title={Cost-efficient
Scheduling on Machines from the Cloud}, journal={arXiv:1609.01184}, author={Mäcker,
Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers,
Sören}, year={2016} }'
chicago: Mäcker, Alexander, Manuel Malatyali, Friedhelm Meyer auf der Heide, and
Sören Riechers. “Cost-Efficient Scheduling on Machines from the Cloud.” ArXiv:1609.01184,
2016.
ieee: A. Mäcker, M. Malatyali, F. Meyer auf der Heide, and S. Riechers, “Cost-efficient
Scheduling on Machines from the Cloud,” arXiv:1609.01184. 2016.
mla: Mäcker, Alexander, et al. “Cost-Efficient Scheduling on Machines from the Cloud.”
ArXiv:1609.01184, 2016.
short: A. Mäcker, M. Malatyali, F. Meyer auf der Heide, S. Riechers, ArXiv:1609.01184
(2016).
date_created: 2020-04-03T09:24:28Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
external_id:
arxiv:
- '1609.01184'
language:
- iso: eng
publication: arXiv:1609.01184
status: public
title: Cost-efficient Scheduling on Machines from the Cloud
type: preprint
user_id: '15415'
year: '2016'
...
---
_id: '274'
abstract:
- lang: eng
text: Consider the problem in which n jobs that are classified into k types are
to be scheduled on m identical machines without preemption. A machine requires
a proper setup taking s time units before processing jobs of a given type. The
objective is to minimize the makespan of the resulting schedule. We design and
analyze an approximation algorithm that runs in time polynomial in n,m and k and
computes a solution with an approximation factor that can be made arbitrarily
close to 3/2.
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-preemptive Scheduling
on Machines with Setup Times. In: Dehne F, Sack JR, Stege U, eds. Algorithms
and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada,
August 5-7, 2015. Proceedings. Lecture Notes in Computer Science. ; 2015:542--553.
doi:10.1007/978-3-319-21840-3_45'
apa: 'Mäcker, A., Malatyali, M., Meyer auf der Heide, F., & Riechers, S. (2015).
Non-preemptive Scheduling on Machines with Setup Times. In F. Dehne, J. R. Sack,
& U. Stege (Eds.), Algorithms and Data Structures: 14th International Symposium,
WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings (pp. 542--553).
https://doi.org/10.1007/978-3-319-21840-3_45'
bibtex: '@inproceedings{Mäcker_Malatyali_Meyer auf der Heide_Riechers_2015, series={Lecture
Notes in Computer Science}, title={Non-preemptive Scheduling on Machines with
Setup Times}, DOI={10.1007/978-3-319-21840-3_45},
booktitle={Algorithms and Data Structures: 14th International Symposium, WADS
2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings}, author={Mäcker, Alexander
and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören},
editor={Dehne, Frank and Sack, Jörg Rüdiger and Stege, UlrikeEditors}, year={2015},
pages={542--553}, collection={Lecture Notes in Computer Science} }'
chicago: 'Mäcker, Alexander, Manuel Malatyali, Friedhelm Meyer auf der Heide, and
Sören Riechers. “Non-Preemptive Scheduling on Machines with Setup Times.” In Algorithms
and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada,
August 5-7, 2015. Proceedings, edited by Frank Dehne, Jörg Rüdiger Sack, and
Ulrike Stege, 542--553. Lecture Notes in Computer Science, 2015. https://doi.org/10.1007/978-3-319-21840-3_45.'
ieee: 'A. Mäcker, M. Malatyali, F. Meyer auf der Heide, and S. Riechers, “Non-preemptive
Scheduling on Machines with Setup Times,” in Algorithms and Data Structures:
14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015.
Proceedings, 2015, pp. 542--553.'
mla: 'Mäcker, Alexander, et al. “Non-Preemptive Scheduling on Machines with Setup
Times.” Algorithms and Data Structures: 14th International Symposium, WADS
2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, edited by Frank
Dehne et al., 2015, pp. 542--553, doi:10.1007/978-3-319-21840-3_45.'
short: 'A. Mäcker, M. Malatyali, F. Meyer auf der Heide, S. Riechers, in: F. Dehne,
J.R. Sack, U. Stege (Eds.), Algorithms and Data Structures: 14th International
Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, 2015,
pp. 542--553.'
date_created: 2017-10-17T12:41:45Z
date_updated: 2022-01-06T06:57:39Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-319-21840-3_45
editor:
- first_name: Frank
full_name: Dehne, Frank
last_name: Dehne
- first_name: Jörg Rüdiger
full_name: Sack, Jörg Rüdiger
last_name: Sack
- first_name: Ulrike
full_name: Stege, Ulrike
last_name: Stege
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-21T09:28:34Z
date_updated: 2018-03-21T09:28:34Z
file_id: '1473'
file_name: 274-chp_3A10.1007_2F978-3-319-21840-3_45.pdf
file_size: 215498
relation: main_file
success: 1
file_date_updated: 2018-03-21T09:28:34Z
has_accepted_license: '1'
page: 542--553
project:
- _id: '1'
name: SFB 901
- _id: '16'
name: SFB 901 - Subprojekt C4
- _id: '4'
name: SFB 901 - Project Area C
publication: 'Algorithms and Data Structures: 14th International Symposium, WADS 2015,
Victoria, BC, Canada, August 5-7, 2015. Proceedings'
series_title: Lecture Notes in Computer Science
status: public
title: Non-preemptive Scheduling on Machines with Setup Times
type: conference
user_id: '15504'
year: '2015'
...
---
_id: '240'
abstract:
- lang: eng
text: We consider online leasing problems in which demands arrive over time and
need to be served by leasing resources. We introduce a new model for these problems
such that a resource can be leased for K different durations each incurring a
different cost (longer leases cost less per time unit). Each demand i can be served
anytime between its arrival ai and its deadline ai+di by a leased resource. The
objective is to meet all deadlines while minimizing the total leasing costs. This
model is a natural generalization of Meyerson’s ParkingPermitProblem (FOCS 2005)
in which di=0 for all i. We propose an online algorithm that is Θ(K+dmaxlmin)-competitive
where dmax and lmin denote the largest di and the shortest available lease length,
respectively. We also extend the SetCoverLeasing problem by deadlines and give
a competitive online algorithm which also improves on existing solutions for the
original SetCoverLeasing problem.
author:
- first_name: Shouwei
full_name: Li, Shouwei
last_name: Li
- first_name: Alexander
full_name: Mäcker, Alexander
id: '13536'
last_name: Mäcker
- 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: Sören
full_name: Riechers, Sören
last_name: Riechers
citation:
ama: 'Li S, Mäcker A, Markarian C, Meyer auf der Heide F, Riechers S. Towards Flexible
Demands in Online Leasing Problems. In: Proceedings of the 21st Annual International
Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer
Science. ; 2015:277--288. doi:10.1007/978-3-319-21398-9_22'
apa: Li, S., Mäcker, A., Markarian, C., Meyer auf der Heide, F., & Riechers,
S. (2015). Towards Flexible Demands in Online Leasing Problems. In Proceedings
of the 21st Annual International Computing and Combinatorics Conference (COCOON)
(pp. 277--288). https://doi.org/10.1007/978-3-319-21398-9_22
bibtex: '@inproceedings{Li_Mäcker_Markarian_Meyer auf der Heide_Riechers_2015, series={Lecture
Notes in Computer Science}, title={Towards Flexible Demands in Online Leasing
Problems}, DOI={10.1007/978-3-319-21398-9_22},
booktitle={Proceedings of the 21st Annual International Computing and Combinatorics
Conference (COCOON)}, author={Li, Shouwei and Mäcker, Alexander and Markarian,
Christine and Meyer auf der Heide, Friedhelm and Riechers, Sören}, year={2015},
pages={277--288}, collection={Lecture Notes in Computer Science} }'
chicago: Li, Shouwei, Alexander Mäcker, Christine Markarian, Friedhelm Meyer auf
der Heide, and Sören Riechers. “Towards Flexible Demands in Online Leasing Problems.”
In Proceedings of the 21st Annual International Computing and Combinatorics
Conference (COCOON), 277--288. Lecture Notes in Computer Science, 2015. https://doi.org/10.1007/978-3-319-21398-9_22.
ieee: S. Li, A. Mäcker, C. Markarian, F. Meyer auf der Heide, and S. Riechers, “Towards
Flexible Demands in Online Leasing Problems,” in Proceedings of the 21st Annual
International Computing and Combinatorics Conference (COCOON), 2015, pp. 277--288.
mla: Li, Shouwei, et al. “Towards Flexible Demands in Online Leasing Problems.”
Proceedings of the 21st Annual International Computing and Combinatorics Conference
(COCOON), 2015, pp. 277--288, doi:10.1007/978-3-319-21398-9_22.
short: 'S. Li, A. Mäcker, C. Markarian, F. Meyer auf der Heide, S. Riechers, in:
Proceedings of the 21st Annual International Computing and Combinatorics Conference
(COCOON), 2015, pp. 277--288.'
date_created: 2017-10-17T12:41:38Z
date_updated: 2022-01-06T06:56:05Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-319-21398-9_22
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-21T10:28:50Z
date_updated: 2018-03-21T10:28:50Z
file_id: '1498'
file_name: 240-chp_3A10.1007_2F978-3-319-21398-9_22.pdf
file_size: 264482
relation: main_file
success: 1
file_date_updated: 2018-03-21T10:28:50Z
has_accepted_license: '1'
page: 277--288
project:
- _id: '1'
name: SFB 901
- _id: '16'
name: SFB 901 - Subprojekt C4
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '2'
name: SFB 901 - Project Area A
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the 21st Annual International Computing and Combinatorics
Conference (COCOON)
series_title: Lecture Notes in Computer Science
status: public
title: Towards Flexible Demands in Online Leasing Problems
type: conference
user_id: '15504'
year: '2015'
...
---
_id: '367'
abstract:
- lang: eng
text: Online social networks are attracting billions of nowadays, both on a global
scale as well as in social enterprise networks. Using distributed hash tables
and peer-to-peer technology allows online social networks to be operated securely
and efficiently only by using the resources of the user devices, thus alleviating
censorship or data misuse by a single network operator. In this paper, we address
the challenges that arise in implementing reliably and conveniently to use distributed
data structures, such as lists or sets, in such a distributed hash-tablebased
online social network. We present a secure, distributed list data structure that
manages the list entries in several buckets in the distributed hash table. The
list entries are authenticated, integrity is maintained and access control for
single users and also groups is integrated. The approach for secure distributed
lists is also applied for prefix trees and sets, and implemented and evaluated
in a peer-to-peer framework for social networks. Evaluation shows that the distributed
data structure is convenient and efficient to use and that the requirements on
security hold.
author:
- first_name: Jens
full_name: Janiuk, Jens
last_name: Janiuk
- first_name: Alexander
full_name: Mäcker, Alexander
id: '13536'
last_name: Mäcker
- first_name: Kalman
full_name: Graffi, Kalman
last_name: Graffi
citation:
ama: 'Janiuk J, Mäcker A, Graffi K. Secure Distributed Data Structures for Peer-to-Peer-based
Social Networks. In: Proceedings of the International Conference on Collaboration
Technologies and Systems (CTS). ; 2014:396-405. doi:10.1109/CTS.2014.6867595'
apa: Janiuk, J., Mäcker, A., & Graffi, K. (2014). Secure Distributed Data Structures
for Peer-to-Peer-based Social Networks. In Proceedings of the International
Conference on Collaboration Technologies and Systems (CTS) (pp. 396–405).
https://doi.org/10.1109/CTS.2014.6867595
bibtex: '@inproceedings{Janiuk_Mäcker_Graffi_2014, title={Secure Distributed Data
Structures for Peer-to-Peer-based Social Networks}, DOI={10.1109/CTS.2014.6867595},
booktitle={Proceedings of the International Conference on Collaboration Technologies
and Systems (CTS)}, author={Janiuk, Jens and Mäcker, Alexander and Graffi, Kalman},
year={2014}, pages={396–405} }'
chicago: Janiuk, Jens, Alexander Mäcker, and Kalman Graffi. “Secure Distributed
Data Structures for Peer-to-Peer-Based Social Networks.” In Proceedings of
the International Conference on Collaboration Technologies and Systems (CTS),
396–405, 2014. https://doi.org/10.1109/CTS.2014.6867595.
ieee: J. Janiuk, A. Mäcker, and K. Graffi, “Secure Distributed Data Structures for
Peer-to-Peer-based Social Networks,” in Proceedings of the International Conference
on Collaboration Technologies and Systems (CTS), 2014, pp. 396–405.
mla: Janiuk, Jens, et al. “Secure Distributed Data Structures for Peer-to-Peer-Based
Social Networks.” Proceedings of the International Conference on Collaboration
Technologies and Systems (CTS), 2014, pp. 396–405, doi:10.1109/CTS.2014.6867595.
short: 'J. Janiuk, A. Mäcker, K. Graffi, in: Proceedings of the International Conference
on Collaboration Technologies and Systems (CTS), 2014, pp. 396–405.'
date_created: 2017-10-17T12:42:03Z
date_updated: 2022-01-06T06:59:29Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1109/CTS.2014.6867595
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-20T07:18:12Z
date_updated: 2018-03-20T07:18:12Z
file_id: '1404'
file_name: 367-cts_conf.pdf
file_size: 647997
relation: main_file
success: 1
file_date_updated: 2018-03-20T07:18:12Z
has_accepted_license: '1'
language:
- iso: eng
page: 396-405
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 International Conference on Collaboration Technologies
and Systems (CTS)
status: public
title: Secure Distributed Data Structures for Peer-to-Peer-based Social Networks
type: conference
user_id: '477'
year: '2014'
...
---
_id: '380'
abstract:
- lang: eng
text: 'Network creation games model the creation and usage costs of networks formed
by n selfish nodes. Each node v can buy a set of edges, each for a fixed price
α > 0. Its goal is to minimize its private costs, i.e., the sum (SUM-game, Fabrikant
et al., PODC 2003) or maximum (MAX-game, Demaine et al., PODC 2007) of distances
from v to all other nodes plus the prices of the bought edges. The above papers
show the existence of Nash equilibria as well as upper and lower bounds for the
prices of anarchy and stability. In several subsequent papers, these bounds were
improved for a wide range of prices α. In this paper, we extend these models by
incorporating quality-of-service aspects: Each edge cannot only be bought at a
fixed quality (edge length one) for a fixed price α. Instead, we assume that quality
levels (i.e., edge lengths) are varying in a fixed interval [βˇ,β^] , 0 series
= {LNCS}'
author:
- first_name: Andreas
full_name: Cord-Landwehr, Andreas
last_name: Cord-Landwehr
- first_name: Alexander
full_name: Mäcker, Alexander
id: '13536'
last_name: Mäcker
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Cord-Landwehr A, Mäcker A, Meyer auf der Heide F. Quality of Service in Network
Creation Games. In: Proceedings of the 10th International Conference on Web
and Internet Economics (WINE). ; 2014:423-428. doi:10.1007/978-3-319-13129-0_34'
apa: Cord-Landwehr, A., Mäcker, A., & Meyer auf der Heide, F. (2014). Quality
of Service in Network Creation Games. In Proceedings of the 10th International
Conference on Web and Internet Economics (WINE) (pp. 423–428). https://doi.org/10.1007/978-3-319-13129-0_34
bibtex: '@inproceedings{Cord-Landwehr_Mäcker_Meyer auf der Heide_2014, title={Quality
of Service in Network Creation Games}, DOI={10.1007/978-3-319-13129-0_34},
booktitle={Proceedings of the 10th International Conference on Web and Internet
Economics (WINE)}, author={Cord-Landwehr, Andreas and Mäcker, Alexander and Meyer
auf der Heide, Friedhelm}, year={2014}, pages={423–428} }'
chicago: Cord-Landwehr, Andreas, Alexander Mäcker, and Friedhelm Meyer auf der Heide.
“Quality of Service in Network Creation Games.” In Proceedings of the 10th
International Conference on Web and Internet Economics (WINE), 423–28, 2014.
https://doi.org/10.1007/978-3-319-13129-0_34.
ieee: A. Cord-Landwehr, A. Mäcker, and F. Meyer auf der Heide, “Quality of Service
in Network Creation Games,” in Proceedings of the 10th International Conference
on Web and Internet Economics (WINE), 2014, pp. 423–428.
mla: Cord-Landwehr, Andreas, et al. “Quality of Service in Network Creation Games.”
Proceedings of the 10th International Conference on Web and Internet Economics
(WINE), 2014, pp. 423–28, doi:10.1007/978-3-319-13129-0_34.
short: 'A. Cord-Landwehr, A. Mäcker, F. Meyer auf der Heide, in: Proceedings of
the 10th International Conference on Web and Internet Economics (WINE), 2014,
pp. 423–428.'
date_created: 2017-10-17T12:42:06Z
date_updated: 2022-01-06T06:59:36Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-319-13129-0_34
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-20T07:05:59Z
date_updated: 2018-03-20T07:05:59Z
file_id: '1394'
file_name: 380-WINE2014.pdf
file_size: 166640
relation: main_file
success: 1
file_date_updated: 2018-03-20T07:05:59Z
has_accepted_license: '1'
page: 423-428
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 10th International Conference on Web and Internet
Economics (WINE)
status: public
title: Quality of Service in Network Creation Games
type: conference
user_id: '15504'
year: '2014'
...
---
_id: '526'
author:
- first_name: Alexander
full_name: Mäcker, Alexander
id: '13536'
last_name: Mäcker
citation:
ama: Mäcker A. Greedy Network Creation With Heavy And Light Edges. Universität
Paderborn; 2013.
apa: Mäcker, A. (2013). Greedy Network Creation With Heavy And Light Edges.
Universität Paderborn.
bibtex: '@book{Mäcker_2013, title={Greedy Network Creation With Heavy And Light
Edges}, publisher={Universität Paderborn}, author={Mäcker, Alexander}, year={2013}
}'
chicago: Mäcker, Alexander. Greedy Network Creation With Heavy And Light Edges.
Universität Paderborn, 2013.
ieee: A. Mäcker, Greedy Network Creation With Heavy And Light Edges. Universität
Paderborn, 2013.
mla: Mäcker, Alexander. Greedy Network Creation With Heavy And Light Edges.
Universität Paderborn, 2013.
short: A. Mäcker, Greedy Network Creation With Heavy And Light Edges, Universität
Paderborn, 2013.
date_created: 2017-10-17T12:42:35Z
date_updated: 2022-01-06T07:01:48Z
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: Greedy Network Creation With Heavy And Light Edges
type: mastersthesis
user_id: '15504'
year: '2013'
...