---
_id: '17653'
author:
- first_name: Gleb
  full_name: Polevoy, Gleb
  id: '83983'
  last_name: Polevoy
- first_name: M.M.
  full_name: de Weerdt, M.M.
  last_name: de Weerdt
citation:
  ama: 'Polevoy G, de Weerdt MM. Reciprocation Effort Games. In: <i>Proceedings of
    the 29th Benelux Conference on Artificial Intelligence</i>. CCIS. Springer; 2017.'
  apa: Polevoy, G., &#38; de Weerdt, M. M. (2017). Reciprocation Effort Games. In
    <i>Proceedings of the 29th Benelux Conference on Artificial Intelligence</i>.
    Springer.
  bibtex: '@inproceedings{Polevoy_de Weerdt_2017, series={CCIS}, title={Reciprocation
    Effort Games}, booktitle={Proceedings of the 29th Benelux Conference on Artificial
    Intelligence}, publisher={Springer}, author={Polevoy, Gleb and de Weerdt, M.M.},
    year={2017}, collection={CCIS} }'
  chicago: Polevoy, Gleb, and M.M. de Weerdt. “Reciprocation Effort Games.” In <i>Proceedings
    of the 29th Benelux Conference on Artificial Intelligence</i>. CCIS. Springer,
    2017.
  ieee: G. Polevoy and M. M. de Weerdt, “Reciprocation Effort Games,” in <i>Proceedings
    of the 29th Benelux Conference on Artificial Intelligence</i>, 2017.
  mla: Polevoy, Gleb, and M. M. de Weerdt. “Reciprocation Effort Games.” <i>Proceedings
    of the 29th Benelux Conference on Artificial Intelligence</i>, Springer, 2017.
  short: 'G. Polevoy, M.M. de Weerdt, in: Proceedings of the 29th Benelux Conference
    on Artificial Intelligence, Springer, 2017.'
date_created: 2020-08-06T15:20:09Z
date_updated: 2022-01-06T06:53:16Z
department:
- _id: '63'
- _id: '541'
extern: '1'
keyword:
- interaction
- reciprocation
- contribute
- shared effort
- curbing
- convergence
- threshold
- Nash equilibrium
- social welfare
- efficiency
- price of anarchy
- price of stability
language:
- iso: eng
publication: Proceedings of the 29th Benelux Conference on Artificial Intelligence
publisher: Springer
series_title: CCIS
status: public
title: Reciprocation Effort Games
type: conference
user_id: '83983'
year: '2017'
...
---
_id: '17654'
author:
- first_name: Gleb
  full_name: Polevoy, Gleb
  id: '83983'
  last_name: Polevoy
- first_name: M.M.
  full_name: de Weerdt, M.M.
  last_name: de Weerdt
citation:
  ama: 'Polevoy G, de Weerdt MM. Competition between Cooperative Projects. In: <i>Proceedings
    of the 29th Benelux Conference on Artificial Intelligence</i>. CCIS. Springer;
    2017.'
  apa: Polevoy, G., &#38; de Weerdt, M. M. (2017). Competition between Cooperative
    Projects. In <i>Proceedings of the 29th Benelux Conference on Artificial Intelligence</i>.
    Springer.
  bibtex: '@inproceedings{Polevoy_de Weerdt_2017, series={CCIS}, title={Competition
    between Cooperative Projects}, booktitle={Proceedings of the 29th Benelux Conference
    on Artificial Intelligence}, publisher={Springer}, author={Polevoy, Gleb and de
    Weerdt, M.M.}, year={2017}, collection={CCIS} }'
  chicago: Polevoy, Gleb, and M.M. de Weerdt. “Competition between Cooperative Projects.”
    In <i>Proceedings of the 29th Benelux Conference on Artificial Intelligence</i>.
    CCIS. Springer, 2017.
  ieee: G. Polevoy and M. M. de Weerdt, “Competition between Cooperative Projects,”
    in <i>Proceedings of the 29th Benelux Conference on Artificial Intelligence</i>,
    2017.
  mla: Polevoy, Gleb, and M. M. de Weerdt. “Competition between Cooperative Projects.”
    <i>Proceedings of the 29th Benelux Conference on Artificial Intelligence</i>,
    Springer, 2017.
  short: 'G. Polevoy, M.M. de Weerdt, in: Proceedings of the 29th Benelux Conference
    on Artificial Intelligence, Springer, 2017.'
date_created: 2020-08-06T15:20:19Z
date_updated: 2022-01-06T06:53:16Z
department:
- _id: '63'
- _id: '541'
extern: '1'
keyword:
- agents
- projects
- contribute
- shared effort game
- competition
- quota
- threshold
- Nash equilibrium
- social welfare
- efficiency
- price of anarchy
- price of stability
language:
- iso: eng
publication: Proceedings of the 29th Benelux Conference on Artificial Intelligence
publisher: Springer
series_title: CCIS
status: public
title: Competition between Cooperative Projects
type: conference
user_id: '83983'
year: '2017'
...
---
_id: '17811'
abstract:
- lang: eng
  text: "We consider a swarm of $n$ autonomous mobile robots, distributed on a\r\n2-dimensional
    grid. A basic task for such a swarm is the gathering process: All\r\nrobots have
    to gather at one (not predefined) place. A common local model for\r\nextremely
    simple robots is the following: The robots do not have a common\r\ncompass, only
    have a constant viewing radius, are autonomous and\r\nindistinguishable, can move
    at most a constant distance in each step, cannot\r\ncommunicate, are oblivious
    and do not have flags or states. The only gathering\r\nalgorithm under this robot
    model, with known runtime bounds, needs\r\n$\\mathcal{O}(n^2)$ rounds and works
    in the Euclidean plane. The underlying time\r\nmodel for the algorithm is the
    fully synchronous $\\mathcal{FSYNC}$ model. On\r\nthe other side, in the case
    of the 2-dimensional grid, the only known gathering\r\nalgorithms for the same
    time and a similar local model additionally require a\r\nconstant memory, states
    and \"flags\" to communicate these states to neighbors in\r\nviewing range. They
    gather in time $\\mathcal{O}(n)$.\r\n  In this paper we contribute the (to the
    best of our knowledge) first\r\ngathering algorithm on the grid that works under
    the same simple local model as\r\nthe above mentioned Euclidean plane strategy,
    i.e., without memory (oblivious),\r\n\"flags\" and states. We prove its correctness
    and an $\\mathcal{O}(n^2)$ time\r\nbound in the fully synchronous $\\mathcal{FSYNC}$
    time model. This time bound\r\nmatches the time bound of the best known algorithm
    for the Euclidean plane\r\nmentioned above. We say gathering is done if all robots
    are located within a\r\n$2\\times 2$ square, because in $\\mathcal{FSYNC}$ such
    configurations cannot be\r\nsolved."
author:
- first_name: Matthias
  full_name: Fischer, Matthias
  id: '146'
  last_name: Fischer
- first_name: Daniel
  full_name: Jung, Daniel
  id: '37827'
  last_name: Jung
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
citation:
  ama: Fischer M, Jung D, Meyer auf der Heide F. Gathering Anonymous, Oblivious Robots
    on a Grid. <i>arXiv:170203400</i>. 2017.
  apa: Fischer, M., Jung, D., &#38; Meyer auf der Heide, F. (2017). Gathering Anonymous,
    Oblivious Robots on a Grid. <i>ArXiv:1702.03400</i>.
  bibtex: '@article{Fischer_Jung_Meyer auf der Heide_2017, title={Gathering Anonymous,
    Oblivious Robots on a Grid}, journal={arXiv:1702.03400}, author={Fischer, Matthias
    and Jung, Daniel and Meyer auf der Heide, Friedhelm}, year={2017} }'
  chicago: Fischer, Matthias, Daniel Jung, and Friedhelm Meyer auf der Heide. “Gathering
    Anonymous, Oblivious Robots on a Grid.” <i>ArXiv:1702.03400</i>, 2017.
  ieee: M. Fischer, D. Jung, and F. Meyer auf der Heide, “Gathering Anonymous, Oblivious
    Robots on a Grid,” <i>arXiv:1702.03400</i>. 2017.
  mla: Fischer, Matthias, et al. “Gathering Anonymous, Oblivious Robots on a Grid.”
    <i>ArXiv:1702.03400</i>, 2017.
  short: M. Fischer, D. Jung, F. Meyer auf der Heide, ArXiv:1702.03400 (2017).
date_created: 2020-08-11T13:48:38Z
date_updated: 2022-01-06T06:53:20Z
department:
- _id: '63'
language:
- iso: eng
publication: arXiv:1702.03400
status: public
title: Gathering Anonymous, Oblivious Robots on a Grid
type: preprint
user_id: '15415'
year: '2017'
...
---
_id: '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: '82'
abstract:
- lang: eng
  text: Many graph problems such as maximum cut, chromatic number, hamiltonian cycle,
    and edge dominating set are known to be fixed-parameter tractable (FPT) when parameterized
    by the treewidth of the input graphs, but become W-hard with respect to the clique-width
    parameter. Recently, Gajarský et al. proposed a new parameter called modular-width
    using the notion of modular decomposition of graphs. They showed that the chromatic
    number problem and the partitioning into paths problem, and hence hamiltonian
    path and hamiltonian cycle, are FPT when parameterized by this parameter. In this
    paper, we study modular-width in parameterized parallel complexity and show that
    the weighted maximum clique problem and the maximum matching problem are fixed-parameter
    parallel-tractable (FPPT) when parameterized by this parameter.
author:
- first_name: Faisal N.
  full_name: Abu-Khzam, Faisal N.
  last_name: Abu-Khzam
- first_name: Shouwei
  full_name: Li, Shouwei
  last_name: Li
- first_name: Christine
  full_name: Markarian, Christine
  id: '37612'
  last_name: Markarian
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
- first_name: Pavel
  full_name: Podlipyan, Pavel
  last_name: Podlipyan
citation:
  ama: 'Abu-Khzam FN, Li S, Markarian C, Meyer auf der Heide F, Podlipyan P. Modular-Width:
    An Auxiliary Parameter for Parameterized Parallel Complexity. In: <i>Proceedings
    of the 11th International Workshop on Frontiers in Algorithmics (FAW)</i>. LNCS.
    ; 2017:139-150. doi:<a href="https://doi.org/10.1007/978-3-319-59605-1_13">10.1007/978-3-319-59605-1_13</a>'
  apa: 'Abu-Khzam, F. N., Li, S., Markarian, C., Meyer auf der Heide, F., &#38; Podlipyan,
    P. (2017). Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity.
    In <i>Proceedings of the 11th International Workshop on Frontiers in Algorithmics
    (FAW)</i> (pp. 139–150). <a href="https://doi.org/10.1007/978-3-319-59605-1_13">https://doi.org/10.1007/978-3-319-59605-1_13</a>'
  bibtex: '@inproceedings{Abu-Khzam_Li_Markarian_Meyer auf der Heide_Podlipyan_2017,
    series={LNCS}, title={Modular-Width: An Auxiliary Parameter for Parameterized
    Parallel Complexity}, DOI={<a href="https://doi.org/10.1007/978-3-319-59605-1_13">10.1007/978-3-319-59605-1_13</a>},
    booktitle={Proceedings of the 11th International Workshop on Frontiers in Algorithmics
    (FAW)}, author={Abu-Khzam, Faisal N. and Li, Shouwei and Markarian, Christine
    and Meyer auf der Heide, Friedhelm and Podlipyan, Pavel}, year={2017}, pages={139–150},
    collection={LNCS} }'
  chicago: 'Abu-Khzam, Faisal N., Shouwei Li, Christine Markarian, Friedhelm Meyer
    auf der Heide, and Pavel Podlipyan. “Modular-Width: An Auxiliary Parameter for
    Parameterized Parallel Complexity.” In <i>Proceedings of the 11th International
    Workshop on Frontiers in Algorithmics (FAW)</i>, 139–50. LNCS, 2017. <a href="https://doi.org/10.1007/978-3-319-59605-1_13">https://doi.org/10.1007/978-3-319-59605-1_13</a>.'
  ieee: 'F. N. Abu-Khzam, S. Li, C. Markarian, F. Meyer auf der Heide, and P. Podlipyan,
    “Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity,”
    in <i>Proceedings of the 11th International Workshop on Frontiers in Algorithmics
    (FAW)</i>, 2017, pp. 139–150.'
  mla: 'Abu-Khzam, Faisal N., et al. “Modular-Width: An Auxiliary Parameter for Parameterized
    Parallel Complexity.” <i>Proceedings of the 11th International Workshop on Frontiers
    in Algorithmics (FAW)</i>, 2017, pp. 139–50, doi:<a href="https://doi.org/10.1007/978-3-319-59605-1_13">10.1007/978-3-319-59605-1_13</a>.'
  short: 'F.N. Abu-Khzam, S. Li, C. Markarian, F. Meyer auf der Heide, P. Podlipyan,
    in: Proceedings of the 11th International Workshop on Frontiers in Algorithmics
    (FAW), 2017, pp. 139–150.'
date_created: 2017-10-17T12:41:07Z
date_updated: 2022-01-06T07:03:52Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1007/978-3-319-59605-1_13
file:
- access_level: closed
  content_type: application/pdf
  creator: ups
  date_created: 2018-11-02T15:07:35Z
  date_updated: 2018-11-02T15:07:35Z
  file_id: '5294'
  file_name: Modular-WidthAnAuxiliaryParame.pdf
  file_size: 238276
  relation: main_file
  success: 1
file_date_updated: 2018-11-02T15:07:35Z
has_accepted_license: '1'
language:
- iso: eng
page: 139-150
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '5'
  name: SFB 901 - Subproject A1
publication: Proceedings of the 11th International Workshop on Frontiers in Algorithmics
  (FAW)
series_title: LNCS
status: public
title: 'Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity'
type: conference
user_id: '477'
year: '2017'
...
---
_id: '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: '70'
author:
- first_name: Björn
  full_name: Feldkord, Björn
  id: '22704'
  last_name: Feldkord
- first_name: Christine
  full_name: Markarian, Christine
  id: '37612'
  last_name: Markarian
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
citation:
  ama: 'Feldkord B, Markarian C, Meyer auf der Heide F. Price Fluctuations in Online
    Leasing. In: <i>Proceedings of the 11th Annual International Conference on Combinatorial
    Optimization and Applications (COCOA)</i>. ; 2017:17-31. doi:<a href="https://doi.org/10.1007/978-3-319-71147-8_2">10.1007/978-3-319-71147-8_2</a>'
  apa: Feldkord, B., Markarian, C., &#38; Meyer auf der Heide, F. (2017). Price Fluctuations
    in Online Leasing. In <i>Proceedings of the 11th Annual International Conference
    on Combinatorial Optimization and Applications (COCOA)</i> (pp. 17–31). <a href="https://doi.org/10.1007/978-3-319-71147-8_2">https://doi.org/10.1007/978-3-319-71147-8_2</a>
  bibtex: '@inproceedings{Feldkord_Markarian_Meyer auf der Heide_2017, title={Price
    Fluctuations in Online Leasing}, DOI={<a href="https://doi.org/10.1007/978-3-319-71147-8_2">10.1007/978-3-319-71147-8_2</a>},
    booktitle={Proceedings of the 11th Annual International Conference on Combinatorial
    Optimization and Applications (COCOA)}, author={Feldkord, Björn and Markarian,
    Christine and Meyer auf der Heide, Friedhelm}, year={2017}, pages={17–31} }'
  chicago: Feldkord, Björn, Christine Markarian, and Friedhelm Meyer auf der Heide.
    “Price Fluctuations in Online Leasing.” In <i>Proceedings of the 11th Annual International
    Conference on Combinatorial Optimization and Applications (COCOA)</i>, 17–31,
    2017. <a href="https://doi.org/10.1007/978-3-319-71147-8_2">https://doi.org/10.1007/978-3-319-71147-8_2</a>.
  ieee: B. Feldkord, C. Markarian, and F. Meyer auf der Heide, “Price Fluctuations
    in Online Leasing,” in <i>Proceedings of the 11th Annual International Conference
    on Combinatorial Optimization and Applications (COCOA)</i>, 2017, pp. 17–31.
  mla: Feldkord, Björn, et al. “Price Fluctuations in Online Leasing.” <i>Proceedings
    of the 11th Annual International Conference on Combinatorial Optimization and
    Applications (COCOA)</i>, 2017, pp. 17–31, doi:<a href="https://doi.org/10.1007/978-3-319-71147-8_2">10.1007/978-3-319-71147-8_2</a>.
  short: 'B. Feldkord, C. Markarian, F. Meyer auf der Heide, in: Proceedings of the
    11th Annual International Conference on Combinatorial Optimization and Applications
    (COCOA), 2017, pp. 17–31.'
date_created: 2017-10-17T12:41:05Z
date_updated: 2022-01-06T07:03:26Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1007/978-3-319-71147-8_2
file:
- access_level: closed
  content_type: application/pdf
  creator: ups
  date_created: 2018-11-02T15:06:13Z
  date_updated: 2018-11-02T15:06:13Z
  file_id: '5293'
  file_name: PriceFluctuationInOnlineLeasin.pdf
  file_size: 287315
  relation: main_file
  success: 1
file_date_updated: 2018-11-02T15:06:13Z
has_accepted_license: '1'
language:
- iso: eng
page: 17 - 31
project:
- _id: '1'
  name: SFB 901
- _id: '5'
  name: SFB 901 - Subprojekt A1
- _id: '2'
  name: SFB 901 - Project Area A
publication: Proceedings of the 11th Annual International Conference on Combinatorial
  Optimization and Applications (COCOA)
status: public
title: Price Fluctuations in Online Leasing
type: conference
user_id: '477'
year: '2017'
...
---
_id: '703'
author:
- first_name: Pavel
  full_name: Podlipyan, Pavel
  last_name: Podlipyan
citation:
  ama: Podlipyan P. <i>Local Algorithms for the Continuous Gathering Problem</i>.
    Universität Paderborn; 2017. doi:<a href="https://doi.org/10.17619/UNIPB/1-230">10.17619/UNIPB/1-230</a>
  apa: Podlipyan, P. (2017). <i>Local Algorithms for the Continuous Gathering Problem</i>.
    Universität Paderborn. <a href="https://doi.org/10.17619/UNIPB/1-230">https://doi.org/10.17619/UNIPB/1-230</a>
  bibtex: '@book{Podlipyan_2017, title={Local Algorithms for the Continuous Gathering
    Problem}, DOI={<a href="https://doi.org/10.17619/UNIPB/1-230">10.17619/UNIPB/1-230</a>},
    publisher={Universität Paderborn}, author={Podlipyan, Pavel}, year={2017} }'
  chicago: Podlipyan, Pavel. <i>Local Algorithms for the Continuous Gathering Problem</i>.
    Universität Paderborn, 2017. <a href="https://doi.org/10.17619/UNIPB/1-230">https://doi.org/10.17619/UNIPB/1-230</a>.
  ieee: P. Podlipyan, <i>Local Algorithms for the Continuous Gathering Problem</i>.
    Universität Paderborn, 2017.
  mla: Podlipyan, Pavel. <i>Local Algorithms for the Continuous Gathering Problem</i>.
    Universität Paderborn, 2017, doi:<a href="https://doi.org/10.17619/UNIPB/1-230">10.17619/UNIPB/1-230</a>.
  short: P. Podlipyan, Local Algorithms for the Continuous Gathering Problem, Universität
    Paderborn, 2017.
date_created: 2017-11-14T14:13:21Z
date_updated: 2022-01-06T07:03:26Z
department:
- _id: '63'
doi: 10.17619/UNIPB/1-230
language:
- iso: eng
publisher: Universität Paderborn
related_material:
  link:
  - relation: confirmation
    url: https://doi.org/10.17619/UNIPB/1-230
status: public
supervisor:
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
title: Local Algorithms for the Continuous Gathering Problem
type: dissertation
user_id: '15415'
year: '2017'
...
---
_id: '704'
author:
- first_name: Sören
  full_name: Riechers, Sören
  last_name: Riechers
citation:
  ama: Riechers S. <i>Scheduling with Scarce Resources</i>. Universität Paderborn;
    2017. doi:<a href="https://doi.org/10.17619/UNIPB/1-231">10.17619/UNIPB/1-231</a>
  apa: Riechers, S. (2017). <i>Scheduling with Scarce Resources</i>. Universität Paderborn.
    <a href="https://doi.org/10.17619/UNIPB/1-231">https://doi.org/10.17619/UNIPB/1-231</a>
  bibtex: '@book{Riechers_2017, title={Scheduling with Scarce Resources}, DOI={<a
    href="https://doi.org/10.17619/UNIPB/1-231">10.17619/UNIPB/1-231</a>}, publisher={Universität
    Paderborn}, author={Riechers, Sören}, year={2017} }'
  chicago: Riechers, Sören. <i>Scheduling with Scarce Resources</i>. Universität Paderborn,
    2017. <a href="https://doi.org/10.17619/UNIPB/1-231">https://doi.org/10.17619/UNIPB/1-231</a>.
  ieee: S. Riechers, <i>Scheduling with Scarce Resources</i>. Universität Paderborn,
    2017.
  mla: Riechers, Sören. <i>Scheduling with Scarce Resources</i>. Universität Paderborn,
    2017, doi:<a href="https://doi.org/10.17619/UNIPB/1-231">10.17619/UNIPB/1-231</a>.
  short: S. Riechers, Scheduling with Scarce Resources, Universität Paderborn, 2017.
date_created: 2017-11-15T07:51:07Z
date_updated: 2022-01-06T07:03:27Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.17619/UNIPB/1-231
file:
- access_level: closed
  content_type: application/pdf
  creator: feldi
  date_created: 2018-11-14T15:18:37Z
  date_updated: 2018-11-14T15:18:37Z
  file_id: '5673'
  file_name: thesisStable.pdf
  file_size: 1491627
  relation: main_file
  success: 1
file_date_updated: 2018-11-14T15:18:37Z
has_accepted_license: '1'
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '16'
  name: SFB 901 - Subprojekt C4
- _id: '4'
  name: SFB 901 - Project Area C
publisher: Universität Paderborn
status: public
supervisor:
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
title: Scheduling with Scarce Resources
type: dissertation
user_id: '14052'
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: '97'
abstract:
- lang: eng
  text: Bridging the gap between informal, imprecise, and vague user requirements
    descriptions and precise formalized specifications is the main task of requirements
    engineering. Techniques such as interviews or story telling are used when requirements
    engineers try to identify a user's needs. The requirements specification process
    is typically done in a dialogue between users, domain experts, and requirements
    engineers. In our research, we aim at automating the specification of requirements.
    The idea is to distinguish between untrained users and trained users, and to exploit
    domain knowledge learned from previous runs of our system. We let untrained users
    provide unstructured natural language descriptions, while we allow trained users
    to provide examples of behavioral descriptions. In both cases, our goal is to
    synthesize formal requirements models similar to statecharts. From requirements
    specification processes with trained users, behavioral ontologies are learned
    which are later used to support the requirements specification process for untrained
    users. Our research method is original in combining natural language processing
    and search-based techniques for the synthesis of requirements specifications.
    Our work is embedded in a larger project that aims at automating the whole software
    development and deployment process in envisioned future software service markets.
author:
- first_name: Lorijn
  full_name: van Rooijen, Lorijn
  id: '58843'
  last_name: van Rooijen
- first_name: Frederik Simon
  full_name: Bäumer, Frederik Simon
  id: '38837'
  last_name: Bäumer
- first_name: Marie Christin
  full_name: Platenius, Marie Christin
  last_name: Platenius
- first_name: Michaela
  full_name: Geierhos, Michaela
  id: '42496'
  last_name: Geierhos
  orcid: 0000-0002-8180-5606
- first_name: Heiko
  full_name: Hamann, Heiko
  last_name: Hamann
- first_name: Gregor
  full_name: Engels, Gregor
  id: '107'
  last_name: Engels
citation:
  ama: 'van Rooijen L, Bäumer FS, Platenius MC, Geierhos M, Hamann H, Engels G. From
    User Demand to Software Service: Using Machine Learning to Automate the Requirements
    Specification Process. In: <i>2017 IEEE 25th International Requirements Engineering
    Conference Workshops (REW)</i>. Piscataway, NJ, USA: IEEE; 2017:379-385. doi:<a
    href="https://doi.org/10.1109/REW.2017.26">10.1109/REW.2017.26</a>'
  apa: 'van Rooijen, L., Bäumer, F. S., Platenius, M. C., Geierhos, M., Hamann, H.,
    &#38; Engels, G. (2017). From User Demand to Software Service: Using Machine Learning
    to Automate the Requirements Specification Process. In <i>2017 IEEE 25th International
    Requirements Engineering Conference Workshops (REW)</i> (pp. 379–385). Piscataway,
    NJ, USA: IEEE. <a href="https://doi.org/10.1109/REW.2017.26">https://doi.org/10.1109/REW.2017.26</a>'
  bibtex: '@inproceedings{van Rooijen_Bäumer_Platenius_Geierhos_Hamann_Engels_2017,
    place={Piscataway, NJ, USA}, title={From User Demand to Software Service: Using
    Machine Learning to Automate the Requirements Specification Process}, DOI={<a
    href="https://doi.org/10.1109/REW.2017.26">10.1109/REW.2017.26</a>}, booktitle={2017
    IEEE 25th International Requirements Engineering Conference Workshops (REW)},
    publisher={IEEE}, author={van Rooijen, Lorijn and Bäumer, Frederik Simon and Platenius,
    Marie Christin and Geierhos, Michaela and Hamann, Heiko and Engels, Gregor}, year={2017},
    pages={379–385} }'
  chicago: 'Rooijen, Lorijn van, Frederik Simon Bäumer, Marie Christin Platenius,
    Michaela Geierhos, Heiko Hamann, and Gregor Engels. “From User Demand to Software
    Service: Using Machine Learning to Automate the Requirements Specification Process.”
    In <i>2017 IEEE 25th International Requirements Engineering Conference Workshops
    (REW)</i>, 379–85. Piscataway, NJ, USA: IEEE, 2017. <a href="https://doi.org/10.1109/REW.2017.26">https://doi.org/10.1109/REW.2017.26</a>.'
  ieee: 'L. van Rooijen, F. S. Bäumer, M. C. Platenius, M. Geierhos, H. Hamann, and
    G. Engels, “From User Demand to Software Service: Using Machine Learning to Automate
    the Requirements Specification Process,” in <i>2017 IEEE 25th International Requirements
    Engineering Conference Workshops (REW)</i>, Lisbon, Portugal, 2017, pp. 379–385.'
  mla: 'van Rooijen, Lorijn, et al. “From User Demand to Software Service: Using Machine
    Learning to Automate the Requirements Specification Process.” <i>2017 IEEE 25th
    International Requirements Engineering Conference Workshops (REW)</i>, IEEE, 2017,
    pp. 379–85, doi:<a href="https://doi.org/10.1109/REW.2017.26">10.1109/REW.2017.26</a>.'
  short: 'L. van Rooijen, F.S. Bäumer, M.C. Platenius, M. Geierhos, H. Hamann, G.
    Engels, in: 2017 IEEE 25th International Requirements Engineering Conference Workshops
    (REW), IEEE, Piscataway, NJ, USA, 2017, pp. 379–385.'
conference:
  end_date: 2017-09-08
  location: Lisbon, Portugal
  name: 2017 IEEE 25th International Requirements Engineering Conference Workshops
    (REW)
  start_date: 2017-09-04
date_created: 2017-10-17T12:41:10Z
date_updated: 2022-01-06T07:04:18Z
ddc:
- '000'
department:
- _id: '36'
- _id: '1'
- _id: '579'
- _id: '34'
- _id: '7'
- _id: '66'
- _id: '238'
- _id: '63'
doi: 10.1109/REW.2017.26
file:
- access_level: closed
  content_type: application/pdf
  creator: ups
  date_created: 2018-11-02T14:50:35Z
  date_updated: 2018-11-02T14:50:35Z
  file_id: '5285'
  file_name: 08054881.pdf
  file_size: 433613
  relation: main_file
  success: 1
file_date_updated: 2018-11-02T14:50:35Z
has_accepted_license: '1'
keyword:
- Software
- Unified modeling language
- Requirements engineering
- Ontologies
- Search problems
- Natural languages
language:
- iso: eng
page: 379-385
place: Piscataway, NJ, USA
project:
- _id: '1'
  name: SFB 901
- _id: '9'
  name: SFB 901 - Subprojekt B1
- _id: '3'
  name: SFB 901 - Project Area B
publication: 2017 IEEE 25th International Requirements Engineering Conference Workshops
  (REW)
publication_identifier:
  eisbn:
  - '978-1-5386-3488-2 '
  isbn:
  - 978-1-5386-3489-9
publication_status: published
publisher: IEEE
quality_controlled: '1'
status: public
title: 'From User Demand to Software Service: Using Machine Learning to Automate the
  Requirements Specification Process'
type: conference
user_id: '57458'
year: '2017'
...
---
_id: '55'
abstract:
- lang: eng
  text: We introduce the mobile server problem, inspired by current trends to move
    computational tasks from cloud structures to multiple devices close to the end
    user. An example for this are embedded systems in autonomous cars that communicate
    in order to coordinate their actions. Our model is a variant of the classical
    Page Migration Problem. Moreformally, we consider a mobile server holding a data
    page.The server can move in the Euclidean space (of arbitrary dimension). In every
    round, requests for data items from the page pop up at arbitrary points in the
    space. The requests are served, each at a cost of the distance from the requesting
    point and the server, and the mobile server may move, at a cost D times the distance
    traveled for some constant D . We assume a maximum distance m the server is allowed
    to move per round. We show that no online algorithm can achieve a competitive
    ratio independent of the length of the input sequence in this setting. Hence we
    augment the maximum movement distance of the online algorithms to ( 1 + δ) times
    the maximum distance of the offline solution. We provide a deterministic algorithm
    which is simple to describe and works for multiple variants of our problem. The
    algorithm achieves almost tight competitive ratios independent of the length of
    the input sequence.
author:
- first_name: Björn
  full_name: Feldkord, Björn
  id: '22704'
  last_name: Feldkord
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
citation:
  ama: 'Feldkord B, Meyer auf der Heide F. The Mobile Server Problem. In: <i>Proceedings
    of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>.
    ; 2017:313-319. doi:<a href="https://doi.org/10.1145/3087556.3087575">10.1145/3087556.3087575</a>'
  apa: Feldkord, B., &#38; Meyer auf der Heide, F. (2017). The Mobile Server Problem.
    In <i>Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures
    (SPAA)</i> (pp. 313–319). <a href="https://doi.org/10.1145/3087556.3087575">https://doi.org/10.1145/3087556.3087575</a>
  bibtex: '@inproceedings{Feldkord_Meyer auf der Heide_2017, title={The Mobile Server
    Problem}, DOI={<a href="https://doi.org/10.1145/3087556.3087575">10.1145/3087556.3087575</a>},
    booktitle={Proceedings of the 29th ACM Symposium on Parallelism in Algorithms
    and Architectures (SPAA)}, author={Feldkord, Björn and Meyer auf der Heide, Friedhelm},
    year={2017}, pages={313–319} }'
  chicago: Feldkord, Björn, and Friedhelm Meyer auf der Heide. “The Mobile Server
    Problem.” In <i>Proceedings of the 29th ACM Symposium on Parallelism in Algorithms
    and Architectures (SPAA)</i>, 313–19, 2017. <a href="https://doi.org/10.1145/3087556.3087575">https://doi.org/10.1145/3087556.3087575</a>.
  ieee: B. Feldkord and F. Meyer auf der Heide, “The Mobile Server Problem,” in <i>Proceedings
    of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>,
    2017, pp. 313–319.
  mla: Feldkord, Björn, and Friedhelm Meyer auf der Heide. “The Mobile Server Problem.”
    <i>Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures
    (SPAA)</i>, 2017, pp. 313–19, doi:<a href="https://doi.org/10.1145/3087556.3087575">10.1145/3087556.3087575</a>.
  short: 'B. Feldkord, F. Meyer auf der Heide, in: Proceedings of the 29th ACM Symposium
    on Parallelism in Algorithms and Architectures (SPAA), 2017, pp. 313–319.'
date_created: 2017-10-17T12:41:02Z
date_updated: 2022-01-06T07:01:56Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1145/3087556.3087575
file:
- access_level: closed
  content_type: application/pdf
  creator: ups
  date_created: 2018-11-02T14:55:10Z
  date_updated: 2018-11-02T14:55:10Z
  file_id: '5288'
  file_name: p313-feldkord.pdf
  file_size: 691691
  relation: main_file
  success: 1
file_date_updated: 2018-11-02T14:55:10Z
has_accepted_license: '1'
language:
- iso: eng
page: 313-319
project:
- _id: '1'
  name: SFB 901
- _id: '5'
  name: SFB 901 - Subprojekt A1
- _id: '2'
  name: SFB 901 - Project Area A
publication: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and
  Architectures (SPAA)
status: public
title: The Mobile Server Problem
type: conference
user_id: '477'
year: '2017'
...
---
_id: '66'
abstract:
- lang: eng
  text: In budget games, players compete over resources with finite budgets. For every
    resource, a player has a specific demand and as a strategy, he chooses a subset
    of resources. If the total demand on a resource does not exceed its budget, the
    utility of each player who chose that resource equals his demand. Otherwise, the
    budget is shared proportionally. In the general case, pure Nash equilibria (NE)
    do not exist for such games. In this paper, we consider the natural classes of
    singleton and matroid budget games with additional constraints and show that for
    each, pure NE can be guaranteed. In addition, we introduce a lexicographical potential
    function to prove that every matroid budget game has an approximate pure NE which
    depends on the largest ratio between the different demands of each individual
    player.
author:
- first_name: Maximilian
  full_name: Drees, Maximilian
  last_name: Drees
- first_name: Matthias
  full_name: Feldotto, Matthias
  id: '14052'
  last_name: Feldotto
  orcid: 0000-0003-1348-6516
- 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: 'Drees M, Feldotto M, Riechers S, Skopalik A. Pure Nash Equilibria in Restricted
    Budget Games. In: <i>Proceedings of the 23rd International Computing and Combinatorics
    Conference (COCOON)</i>. LNCS. ; 2017:175--187. doi:<a href="https://doi.org/10.1007/978-3-319-62389-4_15">10.1007/978-3-319-62389-4_15</a>'
  apa: Drees, M., Feldotto, M., Riechers, S., &#38; Skopalik, A. (2017). Pure Nash
    Equilibria in Restricted Budget Games. In <i>Proceedings of the 23rd International
    Computing and Combinatorics Conference (COCOON)</i> (pp. 175--187). <a href="https://doi.org/10.1007/978-3-319-62389-4_15">https://doi.org/10.1007/978-3-319-62389-4_15</a>
  bibtex: '@inproceedings{Drees_Feldotto_Riechers_Skopalik_2017, series={LNCS}, title={Pure
    Nash Equilibria in Restricted Budget Games}, DOI={<a href="https://doi.org/10.1007/978-3-319-62389-4_15">10.1007/978-3-319-62389-4_15</a>},
    booktitle={Proceedings of the 23rd International Computing and Combinatorics Conference
    (COCOON)}, author={Drees, Maximilian and Feldotto, Matthias and Riechers, Sören
    and Skopalik, Alexander}, year={2017}, pages={175--187}, collection={LNCS} }'
  chicago: Drees, Maximilian, Matthias Feldotto, Sören Riechers, and Alexander Skopalik.
    “Pure Nash Equilibria in Restricted Budget Games.” In <i>Proceedings of the 23rd
    International Computing and Combinatorics Conference (COCOON)</i>, 175--187. LNCS,
    2017. <a href="https://doi.org/10.1007/978-3-319-62389-4_15">https://doi.org/10.1007/978-3-319-62389-4_15</a>.
  ieee: M. Drees, M. Feldotto, S. Riechers, and A. Skopalik, “Pure Nash Equilibria
    in Restricted Budget Games,” in <i>Proceedings of the 23rd International Computing
    and Combinatorics Conference (COCOON)</i>, 2017, pp. 175--187.
  mla: Drees, Maximilian, et al. “Pure Nash Equilibria in Restricted Budget Games.”
    <i>Proceedings of the 23rd International Computing and Combinatorics Conference
    (COCOON)</i>, 2017, pp. 175--187, doi:<a href="https://doi.org/10.1007/978-3-319-62389-4_15">10.1007/978-3-319-62389-4_15</a>.
  short: 'M. Drees, M. Feldotto, S. Riechers, A. Skopalik, in: Proceedings of the
    23rd International Computing and Combinatorics Conference (COCOON), 2017, pp.
    175--187.'
date_created: 2017-10-17T12:41:04Z
date_updated: 2022-01-06T07:03:13Z
ddc:
- '000'
department:
- _id: '541'
- _id: '63'
doi: 10.1007/978-3-319-62389-4_15
file:
- access_level: closed
  content_type: application/pdf
  creator: feldi
  date_created: 2018-10-31T16:58:42Z
  date_updated: 2018-10-31T16:58:42Z
  file_id: '5228'
  file_name: Drees2017_Chapter_PureNashEquilibriaInRestricted.pdf
  file_size: 346390
  relation: main_file
  success: 1
file_date_updated: 2018-10-31T16:58:42Z
has_accepted_license: '1'
language:
- iso: eng
page: 175--187
project:
- _id: '1'
  name: SFB 901
- _id: '7'
  name: SFB 901 - Subprojekt A3
- _id: '16'
  name: SFB 901 - Subproject C4
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '4'
  name: SFB 901 - Project Area C
publication: Proceedings of the 23rd International Computing and Combinatorics Conference
  (COCOON)
series_title: LNCS
status: public
title: Pure Nash Equilibria in Restricted Budget Games
type: conference
user_id: '14052'
year: '2017'
...
---
_id: '695'
author:
- first_name: Joshua
  full_name: Nowack, Joshua
  last_name: Nowack
citation:
  ama: Nowack J. <i>On-The-Fly Konstruktion zusammenhängender Straßennetze aus gegebenen
    Einzelteilen</i>. Universität Paderborn; 2017.
  apa: Nowack, J. (2017). <i>On-The-Fly Konstruktion zusammenhängender Straßennetze
    aus gegebenen Einzelteilen</i>. Universität Paderborn.
  bibtex: '@book{Nowack_2017, title={On-The-Fly Konstruktion zusammenhängender Straßennetze
    aus gegebenen Einzelteilen}, publisher={Universität Paderborn}, author={Nowack,
    Joshua}, year={2017} }'
  chicago: Nowack, Joshua. <i>On-The-Fly Konstruktion zusammenhängender Straßennetze
    aus gegebenen Einzelteilen</i>. Universität Paderborn, 2017.
  ieee: J. Nowack, <i>On-The-Fly Konstruktion zusammenhängender Straßennetze aus gegebenen
    Einzelteilen</i>. Universität Paderborn, 2017.
  mla: Nowack, Joshua. <i>On-The-Fly Konstruktion zusammenhängender Straßennetze aus
    gegebenen Einzelteilen</i>. Universität Paderborn, 2017.
  short: J. Nowack, On-The-Fly Konstruktion zusammenhängender Straßennetze aus gegebenen
    Einzelteilen, Universität Paderborn, 2017.
date_created: 2017-11-14T06:57:49Z
date_updated: 2022-01-06T07:03:23Z
department:
- _id: '63'
language:
- iso: ger
publisher: Universität Paderborn
status: public
title: On-The-Fly Konstruktion zusammenhängender Straßennetze aus gegebenen Einzelteilen
type: bachelorsthesis
user_id: '14052'
year: '2017'
...
---
_id: '16444'
author:
- first_name: Jürgen
  full_name: Gausemeier, Jürgen
  last_name: Gausemeier
- first_name: Eric
  full_name: Bodden, Eric
  last_name: Bodden
- first_name: Falko
  full_name: ' Dressler, Falko'
  last_name: ' Dressler'
- first_name: Roman
  full_name: Dumitrescu, Roman
  last_name: Dumitrescu
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
- first_name: Christoph
  full_name: Scheytt, Christoph
  last_name: Scheytt
- first_name: Ansgar
  full_name: Trächtler, Ansgar
  last_name: Trächtler
citation:
  ama: Gausemeier J, Bodden E,  Dressler F, et al. <i>Wissenschaftsforum Intelligente
    Technische Systeme (WInTeSys)</i>. Paderborn; 2017.
  apa: Gausemeier, J., Bodden, E.,  Dressler, F., Dumitrescu, R., Meyer auf der Heide,
    F., Scheytt, C., &#38; Trächtler, A. (2017). <i>Wissenschaftsforum Intelligente
    Technische Systeme (WInTeSys)</i>. Paderborn.
  bibtex: '@book{Gausemeier_Bodden_ Dressler_Dumitrescu_Meyer auf der Heide_Scheytt_Trächtler_2017,
    place={Paderborn}, series={Verlagsschriftenreihe des Heinz Nixdorf Instituts,
    Paderborn}}, title={Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)},
    author={Gausemeier, Jürgen and Bodden, Eric and  Dressler, Falko and Dumitrescu,
    Roman and Meyer auf der Heide, Friedhelm and Scheytt, Christoph and Trächtler,
    Ansgar}, year={2017}, collection={Verlagsschriftenreihe des Heinz Nixdorf Instituts,
    Paderborn}} }'
  chicago: Gausemeier, Jürgen, Eric Bodden, Falko  Dressler, Roman Dumitrescu, Friedhelm
    Meyer auf der Heide, Christoph Scheytt, and Ansgar Trächtler. <i>Wissenschaftsforum
    Intelligente Technische Systeme (WInTeSys)</i>. Verlagsschriftenreihe Des Heinz
    Nixdorf Instituts, Paderborn}. Paderborn, 2017.
  ieee: J. Gausemeier <i>et al.</i>, <i>Wissenschaftsforum Intelligente Technische
    Systeme (WInTeSys)</i>. Paderborn, 2017.
  mla: Gausemeier, Jürgen, et al. <i>Wissenschaftsforum Intelligente Technische Systeme
    (WInTeSys)</i>. 2017.
  short: J. Gausemeier, E. Bodden, F.  Dressler, R. Dumitrescu, F. Meyer auf der Heide,
    C. Scheytt, A. Trächtler, Wissenschaftsforum Intelligente Technische Systeme (WInTeSys),
    Paderborn, 2017.
date_created: 2020-04-07T06:36:06Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
language:
- iso: eng
page: '369'
place: Paderborn
publication_status: published
series_title: Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}
status: public
title: Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)
type: book
user_id: '15415'
year: '2017'
...
---
_id: '16461'
author:
- first_name: Pascal
  full_name: Bemmann, Pascal
  last_name: Bemmann
- first_name: Felix
  full_name: Biermeier, Felix
  last_name: Biermeier
- first_name: Jan
  full_name: Bürmann, Jan
  last_name: Bürmann
- first_name: Arne
  full_name: Kemper, Arne
  last_name: Kemper
- first_name: Till
  full_name: Knollmann, Till
  id: '39241'
  last_name: Knollmann
  orcid: 0000-0003-2014-4696
- first_name: Steffen
  full_name: Knorr, Steffen
  last_name: Knorr
- first_name: Nils
  full_name: Kothe, Nils
  last_name: Kothe
- first_name: Alexander
  full_name: Mäcker, Alexander
  id: '13536'
  last_name: Mäcker
- first_name: Manuel
  full_name: Malatyali, Manuel
  id: '41265'
  last_name: Malatyali
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
- first_name: Sören
  full_name: Riechers, Sören
  last_name: Riechers
- first_name: Johannes Sebastian
  full_name: Schaefer, Johannes Sebastian
  id: '30291'
  last_name: Schaefer
- first_name: Jannik
  full_name: Sundermeier, Jannik
  id: '38705'
  last_name: Sundermeier
citation:
  ama: 'Bemmann P, Biermeier F, Bürmann J, et al. Monitoring of Domain-Related Problems
    in Distributed Data Streams. In: <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: '1073'
author:
- first_name: Simon
  full_name: Nachtigall, Simon
  last_name: Nachtigall
citation:
  ama: Nachtigall S. <i>Sortieren dynamischer Daten</i>. Universität Paderborn; 2017.
  apa: Nachtigall, S. (2017). <i>Sortieren dynamischer Daten</i>. Universität Paderborn.
  bibtex: '@book{Nachtigall_2017, title={Sortieren dynamischer Daten}, publisher={Universität
    Paderborn}, author={Nachtigall, Simon}, year={2017} }'
  chicago: Nachtigall, Simon. <i>Sortieren dynamischer Daten</i>. Universität Paderborn,
    2017.
  ieee: S. Nachtigall, <i>Sortieren dynamischer Daten</i>. Universität Paderborn,
    2017.
  mla: Nachtigall, Simon. <i>Sortieren dynamischer Daten</i>. Universität Paderborn,
    2017.
  short: S. Nachtigall, Sortieren dynamischer Daten, Universität Paderborn, 2017.
date_created: 2017-12-19T09:59:32Z
date_updated: 2022-01-06T06:50:50Z
department:
- _id: '63'
- _id: '541'
language:
- iso: ger
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '7'
  name: SFB 901 - Subproject A3
publisher: Universität Paderborn
status: public
supervisor:
- first_name: Alexander
  full_name: Skopalik, Alexander
  id: '40384'
  last_name: Skopalik
title: Sortieren dynamischer Daten
type: bachelorsthesis
user_id: '14052'
year: '2017'
...
---
_id: '1074'
author:
- first_name: Simon
  full_name: Pukrop, Simon
  last_name: Pukrop
citation:
  ama: Pukrop S. <i>Robuste Optimierung in Congestion Games</i>. Universität Paderborn;
    2017.
  apa: Pukrop, S. (2017). <i>Robuste Optimierung in Congestion Games</i>. Universität
    Paderborn.
  bibtex: '@book{Pukrop_2017, title={Robuste Optimierung in Congestion Games}, publisher={Universität
    Paderborn}, author={Pukrop, Simon}, year={2017} }'
  chicago: Pukrop, Simon. <i>Robuste Optimierung in Congestion Games</i>. Universität
    Paderborn, 2017.
  ieee: S. Pukrop, <i>Robuste Optimierung in Congestion Games</i>. Universität Paderborn,
    2017.
  mla: Pukrop, Simon. <i>Robuste Optimierung in Congestion Games</i>. Universität
    Paderborn, 2017.
  short: S. Pukrop, Robuste Optimierung in Congestion Games, Universität Paderborn,
    2017.
date_created: 2017-12-19T10:00:25Z
date_updated: 2022-01-06T06:50:50Z
department:
- _id: '63'
- _id: '541'
language:
- iso: ger
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '7'
  name: SFB 901 - Subproject A3
publisher: Universität Paderborn
status: public
supervisor:
- first_name: Alexander
  full_name: Skopalik, Alexander
  id: '40384'
  last_name: Skopalik
title: Robuste Optimierung in Congestion Games
type: bachelorsthesis
user_id: '14052'
year: '2017'
...
---
_id: '1080'
author:
- first_name: Jan
  full_name: Bürmann, Jan
  last_name: Bürmann
citation:
  ama: Bürmann J. <i>Complexity of Signalling in Routing Games under Uncertainty</i>.
    Universität Paderborn; 2017.
  apa: Bürmann, J. (2017). <i>Complexity of Signalling in Routing Games under Uncertainty</i>.
    Universität Paderborn.
  bibtex: '@book{Bürmann_2017, title={Complexity of Signalling in Routing Games under
    Uncertainty}, publisher={Universität Paderborn}, author={Bürmann, Jan}, year={2017}
    }'
  chicago: Bürmann, Jan. <i>Complexity of Signalling in Routing Games under Uncertainty</i>.
    Universität Paderborn, 2017.
  ieee: J. Bürmann, <i>Complexity of Signalling in Routing Games under Uncertainty</i>.
    Universität Paderborn, 2017.
  mla: Bürmann, Jan. <i>Complexity of Signalling in Routing Games under Uncertainty</i>.
    Universität Paderborn, 2017.
  short: J. Bürmann, Complexity of Signalling in Routing Games under Uncertainty,
    Universität Paderborn, 2017.
date_created: 2017-12-19T10:07:35Z
date_updated: 2022-01-06T06:50:50Z
department:
- _id: '63'
- _id: '541'
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '7'
  name: SFB 901 - Subproject A3
publisher: Universität Paderborn
status: public
supervisor:
- first_name: Alexander
  full_name: Skopalik, Alexander
  id: '40384'
  last_name: Skopalik
title: Complexity of Signalling in Routing Games under Uncertainty
type: mastersthesis
user_id: '14052'
year: '2017'
...
---
_id: '1081'
author:
- first_name: Vipin Ravindran
  full_name: Vijayalakshmi, Vipin Ravindran
  last_name: Vijayalakshmi
citation:
  ama: Vijayalakshmi VR. <i>Bounding the Inefficiency of Equilibria in Congestion
    Games under Taxation</i>. Universität Paderborn; 2017.
  apa: Vijayalakshmi, V. R. (2017). <i>Bounding the Inefficiency of Equilibria in
    Congestion Games under Taxation</i>. Universität Paderborn.
  bibtex: '@book{Vijayalakshmi_2017, title={Bounding the Inefficiency of Equilibria
    in Congestion Games under Taxation}, publisher={Universität Paderborn}, author={Vijayalakshmi,
    Vipin Ravindran}, year={2017} }'
  chicago: Vijayalakshmi, Vipin Ravindran. <i>Bounding the Inefficiency of Equilibria
    in Congestion Games under Taxation</i>. Universität Paderborn, 2017.
  ieee: V. R. Vijayalakshmi, <i>Bounding the Inefficiency of Equilibria in Congestion
    Games under Taxation</i>. Universität Paderborn, 2017.
  mla: Vijayalakshmi, Vipin Ravindran. <i>Bounding the Inefficiency of Equilibria
    in Congestion Games under Taxation</i>. Universität Paderborn, 2017.
  short: V.R. Vijayalakshmi, Bounding the Inefficiency of Equilibria in Congestion
    Games under Taxation, Universität Paderborn, 2017.
date_created: 2017-12-19T10:08:44Z
date_updated: 2022-01-06T06:50:51Z
department:
- _id: '63'
- _id: '541'
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '7'
  name: SFB 901 - Subproject A3
publisher: Universität Paderborn
status: public
supervisor:
- first_name: Alexander
  full_name: Skopalik, Alexander
  id: '40384'
  last_name: Skopalik
title: Bounding the Inefficiency of Equilibria in Congestion Games under Taxation
type: mastersthesis
user_id: '14052'
year: '2017'
...