---
_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: <i>Proceedings of the 46th International
    Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)</i>.
    ; 2020.'
  apa: Pukrop, S., Mäcker, A., &#38; Meyer auf der Heide, F. (2020). Approximating
    Weighted Completion Time for Order Scheduling with Setup Times. In <i>Proceedings
    of the 46th International Conference on Current Trends in Theory and Practice
    of Computer Science (SOFSEM)</i>.
  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 <i>Proceedings
    of the 46th International Conference on Current Trends in Theory and Practice
    of Computer Science (SOFSEM)</i>, 2020.
  ieee: S. Pukrop, A. Mäcker, and F. Meyer auf der Heide, “Approximating Weighted
    Completion Time for Order Scheduling with Setup Times,” in <i>Proceedings of the
    46th International Conference on Current Trends in Theory and Practice of Computer
    Science (SOFSEM)</i>, 2020.
  mla: Pukrop, Simon, et al. “Approximating Weighted Completion Time for Order Scheduling
    with Setup Times.” <i>Proceedings of the 46th International Conference on Current
    Trends in Theory and Practice of Computer Science (SOFSEM)</i>, 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: <i>Proceedings of the 33rd IEEE International Parallel and Distributed
    Processing Symposium (IPDPS)</i>. IEEE; 2019:145-154.'
  apa: Jansen, K., Maack, M., &#38; Mäcker, A. (2019). Scheduling on (Un-)Related
    Machines with Setup Times. In <i>Proceedings of the 33rd IEEE International Parallel
    and Distributed Processing Symposium (IPDPS)</i> (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 <i>Proceedings of the 33rd IEEE International Parallel
    and Distributed Processing Symposium (IPDPS)</i>, 145–54. IEEE, 2019.
  ieee: K. Jansen, M. Maack, and A. Mäcker, “Scheduling on (Un-)Related Machines with
    Setup Times,” in <i>Proceedings of the 33rd IEEE International Parallel and Distributed
    Processing Symposium (IPDPS)</i>, 2019, pp. 145–154.
  mla: Jansen, Klaus, et al. “Scheduling on (Un-)Related Machines with Setup Times.”
    <i>Proceedings of the 33rd IEEE International Parallel and Distributed Processing
    Symposium (IPDPS)</i>, 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. <i>On Scheduling with Setup Times</i>. Universität Paderborn; 2019.
    doi:<a href="https://doi.org/10.17619/UNIPB/1-828">10.17619/UNIPB/1-828</a>
  apa: Mäcker, A. (2019). <i>On Scheduling with Setup Times</i>. Universität Paderborn.
    <a href="https://doi.org/10.17619/UNIPB/1-828">https://doi.org/10.17619/UNIPB/1-828</a>
  bibtex: '@book{Mäcker_2019, place={Universität Paderborn}, title={On Scheduling
    with Setup Times}, DOI={<a href="https://doi.org/10.17619/UNIPB/1-828">10.17619/UNIPB/1-828</a>},
    author={Mäcker, Alexander}, year={2019} }'
  chicago: Mäcker, Alexander. <i>On Scheduling with Setup Times</i>. Universität Paderborn,
    2019. <a href="https://doi.org/10.17619/UNIPB/1-828">https://doi.org/10.17619/UNIPB/1-828</a>.
  ieee: A. Mäcker, <i>On Scheduling with Setup Times</i>. Universität Paderborn, 2019.
  mla: Mäcker, Alexander. <i>On Scheduling with Setup Times</i>. 2019, doi:<a href="https://doi.org/10.17619/UNIPB/1-828">10.17619/UNIPB/1-828</a>.
  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. <i>Journal of Combinatorial Optimization</i>.
    2018;36(4):1356-1379. doi:<a href="https://doi.org/10.1007/s10878-018-0325-3">10.1007/s10878-018-0325-3</a>
  apa: König, J., Mäcker, A., Meyer auf der Heide, F., &#38; Riechers, S. (2018).
    Scheduling with interjob communication on parallel processors. <i>Journal of Combinatorial
    Optimization</i>, <i>36</i>(4), 1356–1379. <a href="https://doi.org/10.1007/s10878-018-0325-3">https://doi.org/10.1007/s10878-018-0325-3</a>
  bibtex: '@article{König_Mäcker_Meyer auf der Heide_Riechers_2018, title={Scheduling
    with interjob communication on parallel processors}, volume={36}, DOI={<a href="https://doi.org/10.1007/s10878-018-0325-3">10.1007/s10878-018-0325-3</a>},
    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.” <i>Journal
    of Combinatorial Optimization</i> 36, no. 4 (2018): 1356–79. <a href="https://doi.org/10.1007/s10878-018-0325-3">https://doi.org/10.1007/s10878-018-0325-3</a>.'
  ieee: J. König, A. Mäcker, F. Meyer auf der Heide, and S. Riechers, “Scheduling
    with interjob communication on parallel processors,” <i>Journal of Combinatorial
    Optimization</i>, vol. 36, no. 4, pp. 1356–1379, 2018.
  mla: König, Jürgen, et al. “Scheduling with Interjob Communication on Parallel Processors.”
    <i>Journal of Combinatorial Optimization</i>, vol. 36, no. 4, 2018, pp. 1356–79,
    doi:<a href="https://doi.org/10.1007/s10878-018-0325-3">10.1007/s10878-018-0325-3</a>.
  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: <i>Proceedings
    of the 15th Workshop on Approximation and Online Algorithms (WAOA)</i>. Vol 10787.
    Lecture Notes in Computer Science. Springer; 2017:207-222. doi:<a href="https://doi.org/10.1007/978-3-319-89441-6">10.1007/978-3-319-89441-6</a>'
  apa: Mäcker, A., Malatyali, M., Meyer auf der Heide, F., &#38; Riechers, S. (2017).
    Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times.
    In <i>Proceedings of the 15th Workshop on Approximation and Online Algorithms
    (WAOA)</i> (Vol. 10787, pp. 207–222). Springer. <a href="https://doi.org/10.1007/978-3-319-89441-6">https://doi.org/10.1007/978-3-319-89441-6</a>
  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={<a href="https://doi.org/10.1007/978-3-319-89441-6">10.1007/978-3-319-89441-6</a>},
    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 <i>Proceedings of the 15th Workshop on Approximation and
    Online Algorithms (WAOA)</i>, 10787:207–22. Lecture Notes in Computer Science.
    Springer, 2017. <a href="https://doi.org/10.1007/978-3-319-89441-6">https://doi.org/10.1007/978-3-319-89441-6</a>.
  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 <i>Proceedings
    of the 15th Workshop on Approximation and Online Algorithms (WAOA)</i>, 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.” <i>Proceedings of the 15th Workshop on Approximation
    and Online Algorithms (WAOA)</i>, vol. 10787, Springer, 2017, pp. 207–22, doi:<a
    href="https://doi.org/10.1007/978-3-319-89441-6">10.1007/978-3-319-89441-6</a>.
  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: <i>Proceedings of the 29th ACM Symposium
    on Parallelism in Algorithms and Architectures (SPAA)</i>. ; 2017:123--132. doi:<a
    href="https://doi.org/10.1145/3087556.3087578">10.1145/3087556.3087578</a>'
  apa: 'Kling, P., Mäcker, A., Riechers, S., &#38; Skopalik, A. (2017). Sharing is
    Caring: Multiprocessor Scheduling with a Sharable Resource. In <i>Proceedings
    of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>
    (pp. 123--132). <a href="https://doi.org/10.1145/3087556.3087578">https://doi.org/10.1145/3087556.3087578</a>'
  bibtex: '@inproceedings{Kling_Mäcker_Riechers_Skopalik_2017, title={Sharing is Caring:
    Multiprocessor Scheduling with a Sharable Resource}, DOI={<a href="https://doi.org/10.1145/3087556.3087578">10.1145/3087556.3087578</a>},
    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 <i>Proceedings
    of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>,
    123--132, 2017. <a href="https://doi.org/10.1145/3087556.3087578">https://doi.org/10.1145/3087556.3087578</a>.'
  ieee: 'P. Kling, A. Mäcker, S. Riechers, and A. Skopalik, “Sharing is Caring: Multiprocessor
    Scheduling with a Sharable Resource,” in <i>Proceedings of the 29th ACM Symposium
    on Parallelism in Algorithms and Architectures (SPAA)</i>, 2017, pp. 123--132.'
  mla: 'Kling, Peter, et al. “Sharing Is Caring: Multiprocessor Scheduling with a
    Sharable Resource.” <i>Proceedings of the 29th ACM Symposium on Parallelism in
    Algorithms and Architectures (SPAA)</i>, 2017, pp. 123--132, doi:<a href="https://doi.org/10.1145/3087556.3087578">10.1145/3087556.3087578</a>.'
  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. <i>Journal of Combinatorial Optimization</i>. 2017;36(4):1168-1194.
    doi:<a href="https://doi.org/10.1007/s10878-017-0198-x">10.1007/s10878-017-0198-x</a>
  apa: Mäcker, A., Malatyali, M., Meyer auf der Heide, F., &#38; Riechers, S. (2017).
    Cost-efficient Scheduling on Machines from the Cloud. <i>Journal of Combinatorial
    Optimization</i>, <i>36</i>(4), 1168–1194. <a href="https://doi.org/10.1007/s10878-017-0198-x">https://doi.org/10.1007/s10878-017-0198-x</a>
  bibtex: '@article{Mäcker_Malatyali_Meyer auf der Heide_Riechers_2017, title={Cost-efficient
    Scheduling on Machines from the Cloud}, volume={36}, DOI={<a href="https://doi.org/10.1007/s10878-017-0198-x">10.1007/s10878-017-0198-x</a>},
    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.” <i>Journal
    of Combinatorial Optimization</i> 36, no. 4 (2017): 1168–94. <a href="https://doi.org/10.1007/s10878-017-0198-x">https://doi.org/10.1007/s10878-017-0198-x</a>.'
  ieee: A. Mäcker, M. Malatyali, F. Meyer auf der Heide, and S. Riechers, “Cost-efficient
    Scheduling on Machines from the Cloud,” <i>Journal of Combinatorial Optimization</i>,
    vol. 36, no. 4, pp. 1168–1194, 2017.
  mla: Mäcker, Alexander, et al. “Cost-Efficient Scheduling on Machines from the Cloud.”
    <i>Journal of Combinatorial Optimization</i>, vol. 36, no. 4, Springer, 2017,
    pp. 1168–94, doi:<a href="https://doi.org/10.1007/s10878-017-0198-x">10.1007/s10878-017-0198-x</a>.
  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: <i>Structural Information and Communication Complexity</i>.
    ; 2017. doi:<a href="https://doi.org/10.1007/978-3-319-72050-0_13">10.1007/978-3-319-72050-0_13</a>'
  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., &#38; Sundermeier, J. (2017). Monitoring of Domain-Related Problems
    in Distributed Data Streams. In <i>Structural Information and Communication Complexity</i>.
    <a href="https://doi.org/10.1007/978-3-319-72050-0_13">https://doi.org/10.1007/978-3-319-72050-0_13</a>
  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={<a href="https://doi.org/10.1007/978-3-319-72050-0_13">10.1007/978-3-319-72050-0_13</a>},
    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 <i>Structural Information and Communication Complexity</i>.
    Cham, 2017. <a href="https://doi.org/10.1007/978-3-319-72050-0_13">https://doi.org/10.1007/978-3-319-72050-0_13</a>.
  ieee: P. Bemmann <i>et al.</i>, “Monitoring of Domain-Related Problems in Distributed
    Data Streams,” in <i>Structural Information and Communication Complexity</i>,
    Cham, 2017.
  mla: Bemmann, Pascal, et al. “Monitoring of Domain-Related Problems in Distributed
    Data Streams.” <i>Structural Information and Communication Complexity</i>, 2017,
    doi:<a href="https://doi.org/10.1007/978-3-319-72050-0_13">10.1007/978-3-319-72050-0_13</a>.
  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: <i>Proceedings of the 10th Annual International
    Conference on Combinatorial Optimization and Applications (COCOA)</i>. ; 2016:578--592.
    doi:<a href="https://doi.org/10.1007/978-3-319-48749-6_42">10.1007/978-3-319-48749-6_42</a>'
  apa: Mäcker, A., Malatyali, M., Meyer auf der Heide, F., &#38; Riechers, S. (2016).
    Cost-efficient Scheduling on Machines from the Cloud. In <i>Proceedings of the
    10th Annual International Conference on Combinatorial Optimization and Applications
    (COCOA)</i> (pp. 578--592). <a href="https://doi.org/10.1007/978-3-319-48749-6_42">https://doi.org/10.1007/978-3-319-48749-6_42</a>
  bibtex: '@inproceedings{Mäcker_Malatyali_Meyer auf der Heide_Riechers_2016, title={Cost-efficient
    Scheduling on Machines from the Cloud}, DOI={<a href="https://doi.org/10.1007/978-3-319-48749-6_42">10.1007/978-3-319-48749-6_42</a>},
    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 <i>Proceedings
    of the 10th Annual International Conference on Combinatorial Optimization and
    Applications (COCOA)</i>, 578--592, 2016. <a href="https://doi.org/10.1007/978-3-319-48749-6_42">https://doi.org/10.1007/978-3-319-48749-6_42</a>.
  ieee: A. Mäcker, M. Malatyali, F. Meyer auf der Heide, and S. Riechers, “Cost-efficient
    Scheduling on Machines from the Cloud,” in <i>Proceedings of the 10th Annual International
    Conference on Combinatorial Optimization and Applications (COCOA)</i>, 2016, pp.
    578--592.
  mla: Mäcker, Alexander, et al. “Cost-Efficient Scheduling on Machines from the Cloud.”
    <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization
    and Applications (COCOA)</i>, 2016, pp. 578--592, doi:<a href="https://doi.org/10.1007/978-3-319-48749-6_42">10.1007/978-3-319-48749-6_42</a>.
  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: <i>Proceedings of the 10th Annual International
    Conference on Combinatorial Optimization and Applications (COCOA)</i>. LNCS. ;
    2016:563--577. doi:<a href="https://doi.org/10.1007/978-3-319-48749-6_41">10.1007/978-3-319-48749-6_41</a>'
  apa: König, J., Mäcker, A., Meyer auf der Heide, F., &#38; Riechers, S. (2016).
    Scheduling with Interjob Communication on Parallel Processors. In <i>Proceedings
    of the 10th Annual International Conference on Combinatorial Optimization and
    Applications (COCOA)</i> (pp. 563--577). <a href="https://doi.org/10.1007/978-3-319-48749-6_41">https://doi.org/10.1007/978-3-319-48749-6_41</a>
  bibtex: '@inproceedings{König_Mäcker_Meyer auf der Heide_Riechers_2016, series={LNCS},
    title={Scheduling with Interjob Communication on Parallel Processors}, DOI={<a
    href="https://doi.org/10.1007/978-3-319-48749-6_41">10.1007/978-3-319-48749-6_41</a>},
    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
    <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization
    and Applications (COCOA)</i>, 563--577. LNCS, 2016. <a href="https://doi.org/10.1007/978-3-319-48749-6_41">https://doi.org/10.1007/978-3-319-48749-6_41</a>.
  ieee: J. König, A. Mäcker, F. Meyer auf der Heide, and S. Riechers, “Scheduling
    with Interjob Communication on Parallel Processors,” in <i>Proceedings of the
    10th Annual International Conference on Combinatorial Optimization and Applications
    (COCOA)</i>, 2016, pp. 563--577.
  mla: König, Jürgen, et al. “Scheduling with Interjob Communication on Parallel Processors.”
    <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization
    and Applications (COCOA)</i>, 2016, pp. 563--577, doi:<a href="https://doi.org/10.1007/978-3-319-48749-6_41">10.1007/978-3-319-48749-6_41</a>.
  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. <i>arXiv:160901184</i>. 2016.
  apa: Mäcker, A., Malatyali, M., Meyer auf der Heide, F., &#38; Riechers, S. (2016).
    Cost-efficient Scheduling on Machines from the Cloud. <i>ArXiv:1609.01184</i>.
  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.” <i>ArXiv:1609.01184</i>,
    2016.
  ieee: A. Mäcker, M. Malatyali, F. Meyer auf der Heide, and S. Riechers, “Cost-efficient
    Scheduling on Machines from the Cloud,” <i>arXiv:1609.01184</i>. 2016.
  mla: Mäcker, Alexander, et al. “Cost-Efficient Scheduling on Machines from the Cloud.”
    <i>ArXiv:1609.01184</i>, 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. <i>Algorithms
    and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada,
    August 5-7, 2015. Proceedings</i>. Lecture Notes in Computer Science. ; 2015:542--553.
    doi:<a href="https://doi.org/10.1007/978-3-319-21840-3_45">10.1007/978-3-319-21840-3_45</a>'
  apa: 'Mäcker, A., Malatyali, M., Meyer auf der Heide, F., &#38; Riechers, S. (2015).
    Non-preemptive Scheduling on Machines with Setup Times. In F. Dehne, J. R. Sack,
    &#38; U. Stege (Eds.), <i>Algorithms and Data Structures: 14th International Symposium,
    WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings</i> (pp. 542--553).
    <a href="https://doi.org/10.1007/978-3-319-21840-3_45">https://doi.org/10.1007/978-3-319-21840-3_45</a>'
  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={<a href="https://doi.org/10.1007/978-3-319-21840-3_45">10.1007/978-3-319-21840-3_45</a>},
    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 <i>Algorithms
    and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada,
    August 5-7, 2015. Proceedings</i>, edited by Frank Dehne, Jörg Rüdiger Sack, and
    Ulrike Stege, 542--553. Lecture Notes in Computer Science, 2015. <a href="https://doi.org/10.1007/978-3-319-21840-3_45">https://doi.org/10.1007/978-3-319-21840-3_45</a>.'
  ieee: 'A. Mäcker, M. Malatyali, F. Meyer auf der Heide, and S. Riechers, “Non-preemptive
    Scheduling on Machines with Setup Times,” in <i>Algorithms and Data Structures:
    14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015.
    Proceedings</i>, 2015, pp. 542--553.'
  mla: 'Mäcker, Alexander, et al. “Non-Preemptive Scheduling on Machines with Setup
    Times.” <i>Algorithms and Data Structures: 14th International Symposium, WADS
    2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings</i>, edited by Frank
    Dehne et al., 2015, pp. 542--553, doi:<a href="https://doi.org/10.1007/978-3-319-21840-3_45">10.1007/978-3-319-21840-3_45</a>.'
  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: <i>Proceedings of the 21st Annual International
    Computing and Combinatorics Conference (COCOON)</i>. Lecture Notes in Computer
    Science. ; 2015:277--288. doi:<a href="https://doi.org/10.1007/978-3-319-21398-9_22">10.1007/978-3-319-21398-9_22</a>'
  apa: Li, S., Mäcker, A., Markarian, C., Meyer auf der Heide, F., &#38; Riechers,
    S. (2015). Towards Flexible Demands in Online Leasing Problems. In <i>Proceedings
    of the 21st Annual International Computing and Combinatorics Conference (COCOON)</i>
    (pp. 277--288). <a href="https://doi.org/10.1007/978-3-319-21398-9_22">https://doi.org/10.1007/978-3-319-21398-9_22</a>
  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={<a href="https://doi.org/10.1007/978-3-319-21398-9_22">10.1007/978-3-319-21398-9_22</a>},
    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 <i>Proceedings of the 21st Annual International Computing and Combinatorics
    Conference (COCOON)</i>, 277--288. Lecture Notes in Computer Science, 2015. <a
    href="https://doi.org/10.1007/978-3-319-21398-9_22">https://doi.org/10.1007/978-3-319-21398-9_22</a>.
  ieee: S. Li, A. Mäcker, C. Markarian, F. Meyer auf der Heide, and S. Riechers, “Towards
    Flexible Demands in Online Leasing Problems,” in <i>Proceedings of the 21st Annual
    International Computing and Combinatorics Conference (COCOON)</i>, 2015, pp. 277--288.
  mla: Li, Shouwei, et al. “Towards Flexible Demands in Online Leasing Problems.”
    <i>Proceedings of the 21st Annual International Computing and Combinatorics Conference
    (COCOON)</i>, 2015, pp. 277--288, doi:<a href="https://doi.org/10.1007/978-3-319-21398-9_22">10.1007/978-3-319-21398-9_22</a>.
  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: <i>Proceedings of the International Conference on Collaboration
    Technologies and Systems (CTS)</i>. ; 2014:396-405. doi:<a href="https://doi.org/10.1109/CTS.2014.6867595">10.1109/CTS.2014.6867595</a>'
  apa: Janiuk, J., Mäcker, A., &#38; Graffi, K. (2014). Secure Distributed Data Structures
    for Peer-to-Peer-based Social Networks. In <i>Proceedings of the International
    Conference on Collaboration Technologies and Systems (CTS)</i> (pp. 396–405).
    <a href="https://doi.org/10.1109/CTS.2014.6867595">https://doi.org/10.1109/CTS.2014.6867595</a>
  bibtex: '@inproceedings{Janiuk_Mäcker_Graffi_2014, title={Secure Distributed Data
    Structures for Peer-to-Peer-based Social Networks}, DOI={<a href="https://doi.org/10.1109/CTS.2014.6867595">10.1109/CTS.2014.6867595</a>},
    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 <i>Proceedings of
    the International Conference on Collaboration Technologies and Systems (CTS)</i>,
    396–405, 2014. <a href="https://doi.org/10.1109/CTS.2014.6867595">https://doi.org/10.1109/CTS.2014.6867595</a>.
  ieee: J. Janiuk, A. Mäcker, and K. Graffi, “Secure Distributed Data Structures for
    Peer-to-Peer-based Social Networks,” in <i>Proceedings of the International Conference
    on Collaboration Technologies and Systems (CTS)</i>, 2014, pp. 396–405.
  mla: Janiuk, Jens, et al. “Secure Distributed Data Structures for Peer-to-Peer-Based
    Social Networks.” <i>Proceedings of the International Conference on Collaboration
    Technologies and Systems (CTS)</i>, 2014, pp. 396–405, doi:<a href="https://doi.org/10.1109/CTS.2014.6867595">10.1109/CTS.2014.6867595</a>.
  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: <i>Proceedings of the 10th International Conference on Web
    and Internet Economics (WINE)</i>. ; 2014:423-428. doi:<a href="https://doi.org/10.1007/978-3-319-13129-0_34">10.1007/978-3-319-13129-0_34</a>'
  apa: Cord-Landwehr, A., Mäcker, A., &#38; Meyer auf der Heide, F. (2014). Quality
    of Service in Network Creation Games. In <i>Proceedings of the 10th International
    Conference on Web and Internet Economics (WINE)</i> (pp. 423–428). <a href="https://doi.org/10.1007/978-3-319-13129-0_34">https://doi.org/10.1007/978-3-319-13129-0_34</a>
  bibtex: '@inproceedings{Cord-Landwehr_Mäcker_Meyer auf der Heide_2014, title={Quality
    of Service in Network Creation Games}, DOI={<a href="https://doi.org/10.1007/978-3-319-13129-0_34">10.1007/978-3-319-13129-0_34</a>},
    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 <i>Proceedings of the 10th
    International Conference on Web and Internet Economics (WINE)</i>, 423–28, 2014.
    <a href="https://doi.org/10.1007/978-3-319-13129-0_34">https://doi.org/10.1007/978-3-319-13129-0_34</a>.
  ieee: A. Cord-Landwehr, A. Mäcker, and F. Meyer auf der Heide, “Quality of Service
    in Network Creation Games,” in <i>Proceedings of the 10th International Conference
    on Web and Internet Economics (WINE)</i>, 2014, pp. 423–428.
  mla: Cord-Landwehr, Andreas, et al. “Quality of Service in Network Creation Games.”
    <i>Proceedings of the 10th International Conference on Web and Internet Economics
    (WINE)</i>, 2014, pp. 423–28, doi:<a href="https://doi.org/10.1007/978-3-319-13129-0_34">10.1007/978-3-319-13129-0_34</a>.
  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. <i>Greedy Network Creation With Heavy And Light Edges</i>. Universität
    Paderborn; 2013.
  apa: Mäcker, A. (2013). <i>Greedy Network Creation With Heavy And Light Edges</i>.
    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. <i>Greedy Network Creation With Heavy And Light Edges</i>.
    Universität Paderborn, 2013.
  ieee: A. Mäcker, <i>Greedy Network Creation With Heavy And Light Edges</i>. Universität
    Paderborn, 2013.
  mla: Mäcker, Alexander. <i>Greedy Network Creation With Heavy And Light Edges</i>.
    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'
...