---
_id: '20005'
author:
- first_name: Marco
full_name: Dorigo, Marco
last_name: Dorigo
- first_name: Heiko
full_name: Hamann, Heiko
last_name: Hamann
- first_name: Gabriele
full_name: Valentini, Gabriele
last_name: Valentini
citation:
ama: 'Dorigo M, Hamann H, Valentini G. Efficient Decision-Making in a Self-Organizing
Robot Swarm: On the Speed Versus Accuracy Trade-Off. In: Proceedings of the
14th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2015).
; 2015.'
apa: 'Dorigo, M., Hamann, H., & Valentini, G. (2015). Efficient Decision-Making
in a Self-Organizing Robot Swarm: On the Speed Versus Accuracy Trade-Off. In Proceedings
of the 14th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2015).'
bibtex: '@inproceedings{Dorigo_Hamann_Valentini_2015, title={Efficient Decision-Making
in a Self-Organizing Robot Swarm: On the Speed Versus Accuracy Trade-Off}, booktitle={Proceedings
of the 14th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2015)},
author={Dorigo, Marco and Hamann, Heiko and Valentini, Gabriele}, year={2015}
}'
chicago: 'Dorigo, Marco, Heiko Hamann, and Gabriele Valentini. “Efficient Decision-Making
in a Self-Organizing Robot Swarm: On the Speed Versus Accuracy Trade-Off.” In
Proceedings of the 14th Int. Conf. on Autonomous Agents and Multiagent Systems
(AAMAS 2015), 2015.'
ieee: 'M. Dorigo, H. Hamann, and G. Valentini, “Efficient Decision-Making in a Self-Organizing
Robot Swarm: On the Speed Versus Accuracy Trade-Off,” in Proceedings of the
14th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2015),
2015.'
mla: 'Dorigo, Marco, et al. “Efficient Decision-Making in a Self-Organizing Robot
Swarm: On the Speed Versus Accuracy Trade-Off.” Proceedings of the 14th Int.
Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2015), 2015.'
short: 'M. Dorigo, H. Hamann, G. Valentini, in: Proceedings of the 14th Int. Conf.
on Autonomous Agents and Multiagent Systems (AAMAS 2015), 2015.'
date_created: 2020-10-15T12:29:26Z
date_updated: 2022-01-06T06:54:18Z
department:
- _id: '63'
- _id: '238'
language:
- iso: eng
publication: Proceedings of the 14th Int. Conf. on Autonomous Agents and Multiagent
Systems (AAMAS 2015)
status: public
title: 'Efficient Decision-Making in a Self-Organizing Robot Swarm: On the Speed Versus
Accuracy Trade-Off'
type: conference
user_id: '15415'
year: '2015'
...
---
_id: '20006'
author:
- first_name: Marco
full_name: Dorigo, Marco
last_name: Dorigo
- first_name: Heiko
full_name: Hamann, Heiko
last_name: Hamann
- first_name: Gabriele
full_name: Valentini, Gabriele
last_name: Valentini
citation:
ama: 'Dorigo M, Hamann H, Valentini G. Self-organized collective decisions in a
robot swarm. In: AAAI-15 Video Proceedings. ; 2015.'
apa: Dorigo, M., Hamann, H., & Valentini, G. (2015). Self-organized collective
decisions in a robot swarm. In AAAI-15 Video Proceedings.
bibtex: '@inproceedings{Dorigo_Hamann_Valentini_2015, title={Self-organized collective
decisions in a robot swarm}, booktitle={AAAI-15 Video Proceedings}, author={Dorigo,
Marco and Hamann, Heiko and Valentini, Gabriele}, year={2015} }'
chicago: Dorigo, Marco, Heiko Hamann, and Gabriele Valentini. “Self-Organized Collective
Decisions in a Robot Swarm.” In AAAI-15 Video Proceedings, 2015.
ieee: M. Dorigo, H. Hamann, and G. Valentini, “Self-organized collective decisions
in a robot swarm,” in AAAI-15 Video Proceedings, 2015.
mla: Dorigo, Marco, et al. “Self-Organized Collective Decisions in a Robot Swarm.”
AAAI-15 Video Proceedings, 2015.
short: 'M. Dorigo, H. Hamann, G. Valentini, in: AAAI-15 Video Proceedings, 2015.'
date_created: 2020-10-15T12:38:13Z
date_updated: 2022-01-06T06:54:18Z
department:
- _id: '63'
- _id: '238'
language:
- iso: eng
publication: AAAI-15 Video Proceedings
status: public
title: Self-organized collective decisions in a robot swarm
type: conference
user_id: '15415'
year: '2015'
...
---
_id: '266'
abstract:
- lang: eng
text: 'Many markets have seen a shift from the idea of buying and moved to leasing
instead. Arguably, the latter has been the major catalyst for their success. Ten
years ago, research realized this shift and initiated the study of "online leasing
problems" by introducing leasing to online optimization problems. Resources required
to provide a service in an "online leasing problem" are no more bought but leased
for different durations. In this paper, we provide an overview of results that
contribute to the understanding of "online resource leasing problems". '
author:
- 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: 'Markarian C, Meyer auf der Heide F. Online Resource Leasing. In: Proceedings
of the 2015 ACM Symposium on Principles of Distributed Computing (PODC). ;
2015:343-344. doi:10.1145/2767386.2767454'
apa: Markarian, C., & Meyer auf der Heide, F. (2015). Online Resource Leasing.
In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing
(PODC) (pp. 343–344). https://doi.org/10.1145/2767386.2767454
bibtex: '@inproceedings{Markarian_Meyer auf der Heide_2015, title={Online Resource
Leasing}, DOI={10.1145/2767386.2767454},
booktitle={Proceedings of the 2015 ACM Symposium on Principles of Distributed
Computing (PODC)}, author={Markarian, Christine and Meyer auf der Heide, Friedhelm},
year={2015}, pages={343–344} }'
chicago: Markarian, Christine, and Friedhelm Meyer auf der Heide. “Online Resource
Leasing.” In Proceedings of the 2015 ACM Symposium on Principles of Distributed
Computing (PODC), 343–44, 2015. https://doi.org/10.1145/2767386.2767454.
ieee: C. Markarian and F. Meyer auf der Heide, “Online Resource Leasing,” in Proceedings
of the 2015 ACM Symposium on Principles of Distributed Computing (PODC), 2015,
pp. 343–344.
mla: Markarian, Christine, and Friedhelm Meyer auf der Heide. “Online Resource Leasing.”
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing
(PODC), 2015, pp. 343–44, doi:10.1145/2767386.2767454.
short: 'C. Markarian, F. Meyer auf der Heide, in: Proceedings of the 2015 ACM Symposium
on Principles of Distributed Computing (PODC), 2015, pp. 343–344.'
date_created: 2017-10-17T12:41:44Z
date_updated: 2022-01-06T06:57:22Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1145/2767386.2767454
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-21T09:33:11Z
date_updated: 2018-03-21T09:33:11Z
file_id: '1478'
file_name: 266-p343-markarian.pdf
file_size: 679580
relation: main_file
success: 1
file_date_updated: 2018-03-21T09:33:11Z
has_accepted_license: '1'
page: 343-344
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '16'
name: SFB 901 - Subprojekt C4
- _id: '2'
name: SFB 901 - Project Area A
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing
(PODC)
status: public
title: Online Resource Leasing
type: conference
user_id: '15504'
year: '2015'
...
---
_id: '267'
author:
- first_name: Christine
full_name: Markarian, Christine
id: '37612'
last_name: Markarian
citation:
ama: Markarian C. Online Resource Leasing. Universität Paderborn; 2015.
apa: Markarian, C. (2015). Online Resource Leasing. Universität Paderborn.
bibtex: '@book{Markarian_2015, title={Online Resource Leasing}, publisher={Universität
Paderborn}, author={Markarian, Christine}, year={2015} }'
chicago: Markarian, Christine. Online Resource Leasing. Universität Paderborn,
2015.
ieee: C. Markarian, Online Resource Leasing. Universität Paderborn, 2015.
mla: Markarian, Christine. Online Resource Leasing. Universität Paderborn,
2015.
short: C. Markarian, Online Resource Leasing, Universität Paderborn, 2015.
date_created: 2017-10-17T12:41:44Z
date_updated: 2022-01-06T06:57:26Z
ddc:
- '040'
department:
- _id: '63'
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-21T09:33:41Z
date_updated: 2018-03-21T09:33:41Z
file_id: '1479'
file_name: 267-Dissertation_-_Markarian.pdf
file_size: 1328685
relation: main_file
success: 1
file_date_updated: 2018-03-21T09:33:41Z
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
related_material:
link:
- relation: confirmation
url: http://nbn-resolving.de/urn:nbn:de:hbz:466:2-16656
status: public
supervisor:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
title: Online Resource Leasing
type: dissertation
user_id: '15415'
year: '2015'
...
---
_id: '320'
abstract:
- lang: eng
text: 'We consider structural and algorithmic questions related to the Nash dynamics
of weighted congestion games. In weighted congestion games with linear latency
functions, the existence of pure Nash equilibria is guaranteed by a potential
function argument. Unfortunately, this proof of existence is inefficient and computing
pure Nash equilibria in such games is a PLS-hard problem even when all players
have unit weights. The situation gets worse when superlinear (e.g., quadratic)
latency functions come into play; in this case, the Nash dynamics of the game
may contain cycles and pure Nash equilibria may not even exist. Given these obstacles,
we consider approximate pure Nash equilibria as alternative solution concepts.
A ρ--approximate pure Nash equilibrium is a state of a (weighted congestion) game
from which no player has any incentive to deviate in order to improve her cost
by a multiplicative factor higher than ρ. Do such equilibria exist for small values
of ρ? And if so, can we compute them efficiently?We provide positive answers to
both questions for weighted congestion games with polynomial latency functions
by exploiting an “approximation” of such games by a new class of potential games
that we call Ψ-games. This allows us to show that these games have d!-approximate
pure Nash equilibria, where d is the maximum degree of the latency functions.
Our main technical contribution is an efficient algorithm for computing O(1)-approximate
pure Nash equilibria when d is a constant. For games with linear latency functions,
the approximation guarantee is 3+√5/2 + Oγ for arbitrarily small γ > 0; for latency
functions with maximum degree d≥ 2, it is d2d+o(d). The running time is polynomial
in the number of bits in the representation of the game and 1/γ. As a byproduct
of our techniques, we also show the following interesting structural statement
for weighted congestion games with polynomial latency functions of maximum degree
d ≥ 2: polynomially-long sequences of best-response moves from any initial state
to a dO(d2)-approximate pure Nash equilibrium exist and can be efficiently identified
in such games as long as d is a constant.To the best of our knowledge, these are
the first positive algorithmic results for approximate pure Nash equilibria in
weighted congestion games. Our techniques significantly extend our recent work
on unweighted congestion games through the use of Ψ-games. The concept of approximating
nonpotential games by potential ones is interesting in itself and might have further
applications.'
article_number: '2'
author:
- first_name: Ioannis
full_name: Caragiannis, Ioannis
last_name: Caragiannis
- first_name: Angelo
full_name: Fanelli, Angelo
last_name: Fanelli
- first_name: Nick
full_name: Gravin, Nick
last_name: Gravin
- first_name: Alexander
full_name: Skopalik, Alexander
id: '40384'
last_name: Skopalik
citation:
ama: 'Caragiannis I, Fanelli A, Gravin N, Skopalik A. Approximate Pure Nash Equilibria
in Weighted Congestion Games: Existence, Efficient Computation, and Structure.
Transactions on Economics and Computation. 2015;3(1). doi:10.1145/2614687'
apa: 'Caragiannis, I., Fanelli, A., Gravin, N., & Skopalik, A. (2015). Approximate
Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation,
and Structure. Transactions on Economics and Computation, 3(1).
https://doi.org/10.1145/2614687'
bibtex: '@article{Caragiannis_Fanelli_Gravin_Skopalik_2015, title={Approximate Pure
Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation,
and Structure}, volume={3}, DOI={10.1145/2614687},
number={12}, journal={Transactions on Economics and Computation}, publisher={ACM},
author={Caragiannis, Ioannis and Fanelli, Angelo and Gravin, Nick and Skopalik,
Alexander}, year={2015} }'
chicago: 'Caragiannis, Ioannis, Angelo Fanelli, Nick Gravin, and Alexander Skopalik.
“Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient
Computation, and Structure.” Transactions on Economics and Computation
3, no. 1 (2015). https://doi.org/10.1145/2614687.'
ieee: 'I. Caragiannis, A. Fanelli, N. Gravin, and A. Skopalik, “Approximate Pure
Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation,
and Structure,” Transactions on Economics and Computation, vol. 3, no.
1, 2015.'
mla: 'Caragiannis, Ioannis, et al. “Approximate Pure Nash Equilibria in Weighted
Congestion Games: Existence, Efficient Computation, and Structure.” Transactions
on Economics and Computation, vol. 3, no. 1, 2, ACM, 2015, doi:10.1145/2614687.'
short: I. Caragiannis, A. Fanelli, N. Gravin, A. Skopalik, Transactions on Economics
and Computation 3 (2015).
date_created: 2017-10-17T12:41:54Z
date_updated: 2022-01-06T06:59:04Z
ddc:
- '040'
department:
- _id: '63'
- _id: '541'
doi: 10.1145/2614687
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-20T07:40:55Z
date_updated: 2018-03-20T07:40:55Z
file_id: '1433'
file_name: 320-a2-caragiannis.pdf
file_size: 260503
relation: main_file
success: 1
file_date_updated: 2018-03-20T07:40:55Z
has_accepted_license: '1'
intvolume: ' 3'
issue: '1'
language:
- iso: eng
project:
- _id: '1'
name: SFB 901
- _id: '7'
name: SFB 901 - Subprojekt A3
- _id: '2'
name: SFB 901 - Project Area A
publication: Transactions on Economics and Computation
publisher: ACM
status: public
title: 'Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence,
Efficient Computation, and Structure'
type: journal_article
user_id: '477'
volume: 3
year: '2015'
...
---
_id: '316'
author:
- first_name: Jannis
full_name: Pautz, Jannis
last_name: Pautz
citation:
ama: Pautz J. Budget Games with Priced Strategies. Universität Paderborn;
2015.
apa: Pautz, J. (2015). Budget Games with priced strategies. Universität Paderborn.
bibtex: '@book{Pautz_2015, title={Budget Games with priced strategies}, publisher={Universität
Paderborn}, author={Pautz, Jannis}, year={2015} }'
chicago: Pautz, Jannis. Budget Games with Priced Strategies. Universität
Paderborn, 2015.
ieee: J. Pautz, Budget Games with priced strategies. Universität Paderborn,
2015.
mla: Pautz, Jannis. Budget Games with Priced Strategies. Universität Paderborn,
2015.
short: J. Pautz, Budget Games with Priced Strategies, Universität Paderborn, 2015.
date_created: 2017-10-17T12:41:53Z
date_updated: 2022-01-06T06:59:01Z
department:
- _id: '63'
- _id: '541'
project:
- _id: '1'
name: SFB 901
- _id: '7'
name: SFB 901 - Subprojekt A3
- _id: '2'
name: SFB 901 - Project Area A
publisher: Universität Paderborn
status: public
supervisor:
- first_name: Alexander
full_name: Skopalik, Alexander
id: '40384'
last_name: Skopalik
title: Budget Games with priced strategies
type: bachelorsthesis
user_id: '14052'
year: '2015'
...
---
_id: '317'
author:
- first_name: Claudius
full_name: Jähn, Claudius
last_name: Jähn
citation:
ama: Jähn C. Bewertung von Renderingalgorithmen für komplexe 3-D-Szenen.
Universität Paderborn; 2015.
apa: Jähn, C. (2015). Bewertung von Renderingalgorithmen für komplexe 3-D-Szenen.
Universität Paderborn.
bibtex: '@book{Jähn_2015, title={Bewertung von Renderingalgorithmen für komplexe
3-D-Szenen}, publisher={Universität Paderborn}, author={Jähn, Claudius}, year={2015}
}'
chicago: Jähn, Claudius. Bewertung von Renderingalgorithmen für komplexe 3-D-Szenen.
Universität Paderborn, 2015.
ieee: C. Jähn, Bewertung von Renderingalgorithmen für komplexe 3-D-Szenen.
Universität Paderborn, 2015.
mla: Jähn, Claudius. Bewertung von Renderingalgorithmen für komplexe 3-D-Szenen.
Universität Paderborn, 2015.
short: C. Jähn, Bewertung von Renderingalgorithmen für komplexe 3-D-Szenen, Universität
Paderborn, 2015.
date_created: 2017-10-17T12:41:53Z
date_updated: 2022-01-06T06:59:02Z
ddc:
- '040'
department:
- _id: '63'
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-21T09:20:34Z
date_updated: 2018-03-21T09:20:34Z
file_id: '1462'
file_name: 317-Dissertation_ClaudiusJaehn.pdf
file_size: 20442332
relation: main_file
success: 1
file_date_updated: 2018-03-21T09:20:34Z
has_accepted_license: '1'
language:
- iso: ger
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: Bewertung von Renderingalgorithmen für komplexe 3-D-Szenen
type: dissertation
user_id: '14052'
year: '2015'
...
---
_id: '270'
author:
- first_name: Sebastian
full_name: Abshoff, Sebastian
last_name: Abshoff
citation:
ama: Abshoff S. On the Complexity of Fundamental Problems in Dynamic Ad-Hoc Networks.
Universität Paderborn; 2015.
apa: Abshoff, S. (2015). On the Complexity of Fundamental Problems in Dynamic
Ad-hoc Networks. Universität Paderborn.
bibtex: '@book{Abshoff_2015, title={On the Complexity of Fundamental Problems in
Dynamic Ad-hoc Networks}, publisher={Universität Paderborn}, author={Abshoff,
Sebastian}, year={2015} }'
chicago: Abshoff, Sebastian. On the Complexity of Fundamental Problems in Dynamic
Ad-Hoc Networks. Universität Paderborn, 2015.
ieee: S. Abshoff, On the Complexity of Fundamental Problems in Dynamic Ad-hoc
Networks. Universität Paderborn, 2015.
mla: Abshoff, Sebastian. On the Complexity of Fundamental Problems in Dynamic
Ad-Hoc Networks. Universität Paderborn, 2015.
short: S. Abshoff, On the Complexity of Fundamental Problems in Dynamic Ad-Hoc Networks,
Universität Paderborn, 2015.
date_created: 2017-10-17T12:41:44Z
date_updated: 2022-01-06T06:57:32Z
ddc:
- '040'
department:
- _id: '63'
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-21T09:30:02Z
date_updated: 2018-03-21T09:30:02Z
file_id: '1476'
file_name: 270-Dissertation_-_Abshoff.pdf
file_size: 448614
relation: main_file
success: 1
file_date_updated: 2018-03-21T09:30:02Z
has_accepted_license: '1'
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
supervisor:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
title: On the Complexity of Fundamental Problems in Dynamic Ad-hoc Networks
type: dissertation
user_id: '477'
year: '2015'
...
---
_id: '271'
abstract:
- lang: eng
text: In \emph{bandwidth allocation games} (BAGs), the strategy of a player consists
of various demands on different resources. The player's utility is at most the
sum of these demands, provided they are fully satisfied. Every resource has a
limited capacity and if it is exceeded by the total demand, it has to be split
between the players. Since these games generally do not have pure Nash equilibria,
we consider approximate pure Nash equilibria, in which no player can improve her
utility by more than some fixed factor $\alpha$ through unilateral strategy changes.
There is a threshold $\alpha_\delta$ (where $\delta$ is a parameter that limits
the demand of each player on a specific resource) such that $\alpha$-approximate
pure Nash equilibria always exist for $\alpha \geq \alpha_\delta$, but not for
$\alpha < \alpha_\delta$. We give both upper and lower bounds on this threshold
$\alpha_\delta$ and show that the corresponding decision problem is ${\sf NP}$-hard.
We also show that the $\alpha$-approximate price of anarchy for BAGs is $\alpha+1$.
For a restricted version of the game, where demands of players only differ slightly
from each other (e.g. symmetric games), we show that approximate Nash equilibria
can be reached (and thus also be computed) in polynomial time using the best-response
dynamic. Finally, we show that a broader class of utility-maximization games (which
includes BAGs) converges quickly towards states whose social welfare is close
to the optimum.
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. On Existence and Properties of
Approximate Pure Nash Equilibria in Bandwidth Allocation Games. In: Proceedings
of the 8th International Symposium on Algorithmic Game Theory (SAGT). Lecture
Notes in Computer Science. ; 2015:178-189. doi:10.1007/978-3-662-48433-3_14'
apa: Drees, M., Feldotto, M., Riechers, S., & Skopalik, A. (2015). On Existence
and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games.
In Proceedings of the 8th International Symposium on Algorithmic Game Theory
(SAGT) (pp. 178–189). https://doi.org/10.1007/978-3-662-48433-3_14
bibtex: '@inproceedings{Drees_Feldotto_Riechers_Skopalik_2015, series={Lecture Notes
in Computer Science}, title={On Existence and Properties of Approximate Pure Nash
Equilibria in Bandwidth Allocation Games}, DOI={10.1007/978-3-662-48433-3_14},
booktitle={Proceedings of the 8th International Symposium on Algorithmic Game
Theory (SAGT)}, author={Drees, Maximilian and Feldotto, Matthias and Riechers,
Sören and Skopalik, Alexander}, year={2015}, pages={178–189}, collection={Lecture
Notes in Computer Science} }'
chicago: Drees, Maximilian, Matthias Feldotto, Sören Riechers, and Alexander Skopalik.
“On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth
Allocation Games.” In Proceedings of the 8th International Symposium on Algorithmic
Game Theory (SAGT), 178–89. Lecture Notes in Computer Science, 2015. https://doi.org/10.1007/978-3-662-48433-3_14.
ieee: M. Drees, M. Feldotto, S. Riechers, and A. Skopalik, “On Existence and Properties
of Approximate Pure Nash Equilibria in Bandwidth Allocation Games,” in Proceedings
of the 8th International Symposium on Algorithmic Game Theory (SAGT), 2015,
pp. 178–189.
mla: Drees, Maximilian, et al. “On Existence and Properties of Approximate Pure
Nash Equilibria in Bandwidth Allocation Games.” Proceedings of the 8th International
Symposium on Algorithmic Game Theory (SAGT), 2015, pp. 178–89, doi:10.1007/978-3-662-48433-3_14.
short: 'M. Drees, M. Feldotto, S. Riechers, A. Skopalik, in: Proceedings of the
8th International Symposium on Algorithmic Game Theory (SAGT), 2015, pp. 178–189.'
date_created: 2017-10-17T12:41:45Z
date_updated: 2022-01-06T06:57:34Z
ddc:
- '040'
department:
- _id: '63'
- _id: '541'
doi: 10.1007/978-3-662-48433-3_14
external_id:
arxiv:
- '1507.02908'
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-21T09:29:34Z
date_updated: 2018-03-21T09:29:34Z
file_id: '1475'
file_name: 271-chp_3A10.1007_2F978-3-662-48433-3_14.pdf
file_size: 256718
relation: main_file
success: 1
file_date_updated: 2018-03-21T09:29:34Z
has_accepted_license: '1'
page: 178-189
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 8th International Symposium on Algorithmic Game Theory
(SAGT)
series_title: Lecture Notes in Computer Science
status: public
title: On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth
Allocation Games
type: conference
user_id: '14052'
year: '2015'
...
---
_id: '274'
abstract:
- lang: eng
text: Consider the problem in which n jobs that are classified into k types are
to be scheduled on m identical machines without preemption. A machine requires
a proper setup taking s time units before processing jobs of a given type. The
objective is to minimize the makespan of the resulting schedule. We design and
analyze an approximation algorithm that runs in time polynomial in n,m and k and
computes a solution with an approximation factor that can be made arbitrarily
close to 3/2.
author:
- first_name: Alexander
full_name: Mäcker, Alexander
id: '13536'
last_name: Mäcker
- first_name: Manuel
full_name: Malatyali, Manuel
last_name: Malatyali
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Sören
full_name: Riechers, Sören
last_name: Riechers
citation:
ama: 'Mäcker A, Malatyali M, Meyer auf der Heide F, Riechers S. Non-preemptive Scheduling
on Machines with Setup Times. In: Dehne F, Sack JR, Stege U, eds. Algorithms
and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada,
August 5-7, 2015. Proceedings. Lecture Notes in Computer Science. ; 2015:542--553.
doi:10.1007/978-3-319-21840-3_45'
apa: 'Mäcker, A., Malatyali, M., Meyer auf der Heide, F., & Riechers, S. (2015).
Non-preemptive Scheduling on Machines with Setup Times. In F. Dehne, J. R. Sack,
& U. Stege (Eds.), Algorithms and Data Structures: 14th International Symposium,
WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings (pp. 542--553).
https://doi.org/10.1007/978-3-319-21840-3_45'
bibtex: '@inproceedings{Mäcker_Malatyali_Meyer auf der Heide_Riechers_2015, series={Lecture
Notes in Computer Science}, title={Non-preemptive Scheduling on Machines with
Setup Times}, DOI={10.1007/978-3-319-21840-3_45},
booktitle={Algorithms and Data Structures: 14th International Symposium, WADS
2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings}, author={Mäcker, Alexander
and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören},
editor={Dehne, Frank and Sack, Jörg Rüdiger and Stege, UlrikeEditors}, year={2015},
pages={542--553}, collection={Lecture Notes in Computer Science} }'
chicago: 'Mäcker, Alexander, Manuel Malatyali, Friedhelm Meyer auf der Heide, and
Sören Riechers. “Non-Preemptive Scheduling on Machines with Setup Times.” In Algorithms
and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada,
August 5-7, 2015. Proceedings, edited by Frank Dehne, Jörg Rüdiger Sack, and
Ulrike Stege, 542--553. Lecture Notes in Computer Science, 2015. https://doi.org/10.1007/978-3-319-21840-3_45.'
ieee: 'A. Mäcker, M. Malatyali, F. Meyer auf der Heide, and S. Riechers, “Non-preemptive
Scheduling on Machines with Setup Times,” in Algorithms and Data Structures:
14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015.
Proceedings, 2015, pp. 542--553.'
mla: 'Mäcker, Alexander, et al. “Non-Preemptive Scheduling on Machines with Setup
Times.” Algorithms and Data Structures: 14th International Symposium, WADS
2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, edited by Frank
Dehne et al., 2015, pp. 542--553, doi:10.1007/978-3-319-21840-3_45.'
short: 'A. Mäcker, M. Malatyali, F. Meyer auf der Heide, S. Riechers, in: F. Dehne,
J.R. Sack, U. Stege (Eds.), Algorithms and Data Structures: 14th International
Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, 2015,
pp. 542--553.'
date_created: 2017-10-17T12:41:45Z
date_updated: 2022-01-06T06:57:39Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-319-21840-3_45
editor:
- first_name: Frank
full_name: Dehne, Frank
last_name: Dehne
- first_name: Jörg Rüdiger
full_name: Sack, Jörg Rüdiger
last_name: Sack
- first_name: Ulrike
full_name: Stege, Ulrike
last_name: Stege
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-21T09:28:34Z
date_updated: 2018-03-21T09:28:34Z
file_id: '1473'
file_name: 274-chp_3A10.1007_2F978-3-319-21840-3_45.pdf
file_size: 215498
relation: main_file
success: 1
file_date_updated: 2018-03-21T09:28:34Z
has_accepted_license: '1'
page: 542--553
project:
- _id: '1'
name: SFB 901
- _id: '16'
name: SFB 901 - Subprojekt C4
- _id: '4'
name: SFB 901 - Project Area C
publication: 'Algorithms and Data Structures: 14th International Symposium, WADS 2015,
Victoria, BC, Canada, August 5-7, 2015. Proceedings'
series_title: Lecture Notes in Computer Science
status: public
title: Non-preemptive Scheduling on Machines with Setup Times
type: conference
user_id: '15504'
year: '2015'
...
---
_id: '275'
abstract:
- lang: eng
text: 'We investigate a non-cooperative game-theoretic model for the formation of
communication networks by selfish agents. Each agent aims for a central position
at minimum cost for creating edges. In particular, the general model (Fabrikant
et al., PODC''03) became popular for studying the structure of the Internet or
social networks. Despite its significance, locality in this game was first studied
only recently (Bilò et al., SPAA''14), where a worst case locality model was presented,
which came with a high efficiency loss in terms of quality of equilibria. Our
main contribution is a new and more optimistic view on locality: agents are limited
in their knowledge and actions to their local view ranges, but can probe different
strategies and finally choose the best. We study the influence of our locality
notion on the hardness of computing best responses, convergence to equilibria,
and quality of equilibria. Moreover, we compare the strength of local versus non-local
strategy changes. Our results address the gap between the original model and the
worst case locality variant. On the bright side, our efficiency results are in
line with observations from the original model, yet we have a non-constant lower
bound on the Price of Anarchy.'
author:
- first_name: Andreas
full_name: Cord-Landwehr, Andreas
last_name: Cord-Landwehr
- first_name: Pascal
full_name: Lenzner, Pascal
last_name: Lenzner
citation:
ama: 'Cord-Landwehr A, Lenzner P. Network Creation Games: Think Global - Act Local.
In: Proceedings of the 40th Conference on Mathematical Foundations of Computer
Science (MFCS). LNCS. ; 2015:248--260. doi:10.1007/978-3-662-48054-0_21'
apa: 'Cord-Landwehr, A., & Lenzner, P. (2015). Network Creation Games: Think
Global - Act Local. In Proceedings of the 40th Conference on Mathematical Foundations
of Computer Science (MFCS) (pp. 248--260). https://doi.org/10.1007/978-3-662-48054-0_21'
bibtex: '@inproceedings{Cord-Landwehr_Lenzner_2015, series={LNCS}, title={Network
Creation Games: Think Global - Act Local}, DOI={10.1007/978-3-662-48054-0_21},
booktitle={Proceedings of the 40th Conference on Mathematical Foundations of Computer
Science (MFCS)}, author={Cord-Landwehr, Andreas and Lenzner, Pascal}, year={2015},
pages={248--260}, collection={LNCS} }'
chicago: 'Cord-Landwehr, Andreas, and Pascal Lenzner. “Network Creation Games: Think
Global - Act Local.” In Proceedings of the 40th Conference on Mathematical
Foundations of Computer Science (MFCS), 248--260. LNCS, 2015. https://doi.org/10.1007/978-3-662-48054-0_21.'
ieee: 'A. Cord-Landwehr and P. Lenzner, “Network Creation Games: Think Global -
Act Local,” in Proceedings of the 40th Conference on Mathematical Foundations
of Computer Science (MFCS), 2015, pp. 248--260.'
mla: 'Cord-Landwehr, Andreas, and Pascal Lenzner. “Network Creation Games: Think
Global - Act Local.” Proceedings of the 40th Conference on Mathematical Foundations
of Computer Science (MFCS), 2015, pp. 248--260, doi:10.1007/978-3-662-48054-0_21.'
short: 'A. Cord-Landwehr, P. Lenzner, in: Proceedings of the 40th Conference on
Mathematical Foundations of Computer Science (MFCS), 2015, pp. 248--260.'
date_created: 2017-10-17T12:41:45Z
date_updated: 2022-01-06T06:57:40Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-662-48054-0_21
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-21T09:27:12Z
date_updated: 2018-03-21T09:27:12Z
file_id: '1472'
file_name: 275-978-3-662-48054-0_21.pdf
file_size: 279995
relation: main_file
success: 1
file_date_updated: 2018-03-21T09:27:12Z
has_accepted_license: '1'
language:
- iso: eng
page: 248--260
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 40th Conference on Mathematical Foundations of Computer
Science (MFCS)
series_title: LNCS
status: public
title: 'Network Creation Games: Think Global - Act Local'
type: conference
user_id: '477'
year: '2015'
...
---
_id: '277'
author:
- first_name: Nils
full_name: Kothe, Nils
last_name: Kothe
citation:
ama: Kothe N. Multilevel Netzwerk Spiele mit konstanten Entfernungen im Highspeed-Netzwerk.
Universität Paderborn; 2015.
apa: Kothe, N. (2015). Multilevel Netzwerk Spiele mit konstanten Entfernungen
im Highspeed-Netzwerk. Universität Paderborn.
bibtex: '@book{Kothe_2015, title={Multilevel Netzwerk Spiele mit konstanten Entfernungen
im Highspeed-Netzwerk}, publisher={Universität Paderborn}, author={Kothe, Nils},
year={2015} }'
chicago: Kothe, Nils. Multilevel Netzwerk Spiele mit konstanten Entfernungen
im Highspeed-Netzwerk. Universität Paderborn, 2015.
ieee: N. Kothe, Multilevel Netzwerk Spiele mit konstanten Entfernungen im Highspeed-Netzwerk.
Universität Paderborn, 2015.
mla: Kothe, Nils. Multilevel Netzwerk Spiele mit konstanten Entfernungen im Highspeed-Netzwerk.
Universität Paderborn, 2015.
short: N. Kothe, Multilevel Netzwerk Spiele mit konstanten Entfernungen im Highspeed-Netzwerk,
Universität Paderborn, 2015.
date_created: 2017-10-17T12:41:46Z
date_updated: 2022-01-06T06:57:44Z
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: Multilevel Netzwerk Spiele mit konstanten Entfernungen im Highspeed-Netzwerk
type: bachelorsthesis
user_id: '14052'
year: '2015'
...
---
_id: '17425'
author:
- first_name: 'Jan '
full_name: 'Berssenbrügge, Jan '
last_name: Berssenbrügge
- first_name: Olga
full_name: Wiederkehr, Olga
last_name: Wiederkehr
- first_name: Claudius
full_name: Jähn, Claudius
last_name: Jähn
- first_name: Matthias
full_name: Fischer, Matthias
id: '146'
last_name: Fischer
citation:
ama: 'Berssenbrügge J, Wiederkehr O, Jähn C, Fischer M. Anbindung des Virtuellen
Prototypen an die Partialmodelle intelligenter technischer Systeme. In: 12.
Paderborner Workshop Augmented & Virtual Reality in Der Produktentstehung.
Vol 343. Verlagsschriftenreihe des Heinz Nixdorf Instituts; 2015:65-78.'
apa: Berssenbrügge, J., Wiederkehr, O., Jähn, C., & Fischer, M. (2015). Anbindung
des Virtuellen Prototypen an die Partialmodelle intelligenter technischer Systeme.
12. Paderborner Workshop Augmented & Virtual Reality in Der Produktentstehung,
343, 65–78.
bibtex: '@inproceedings{Berssenbrügge_Wiederkehr_Jähn_Fischer_2015, place={Paderborn},
title={Anbindung des Virtuellen Prototypen an die Partialmodelle intelligenter
technischer Systeme}, volume={343}, booktitle={12. Paderborner Workshop Augmented
& Virtual Reality in der Produktentstehung}, publisher={Verlagsschriftenreihe
des Heinz Nixdorf Instituts}, author={Berssenbrügge, Jan and Wiederkehr, Olga
and Jähn, Claudius and Fischer, Matthias}, year={2015}, pages={65–78} }'
chicago: 'Berssenbrügge, Jan , Olga Wiederkehr, Claudius Jähn, and Matthias Fischer.
“Anbindung Des Virtuellen Prototypen an Die Partialmodelle Intelligenter Technischer
Systeme.” In 12. Paderborner Workshop Augmented & Virtual Reality in Der
Produktentstehung, 343:65–78. Paderborn: Verlagsschriftenreihe des Heinz Nixdorf
Instituts, 2015.'
ieee: J. Berssenbrügge, O. Wiederkehr, C. Jähn, and M. Fischer, “Anbindung des Virtuellen
Prototypen an die Partialmodelle intelligenter technischer Systeme,” in 12.
Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung,
2015, vol. 343, pp. 65–78.
mla: Berssenbrügge, Jan, et al. “Anbindung Des Virtuellen Prototypen an Die Partialmodelle
Intelligenter Technischer Systeme.” 12. Paderborner Workshop Augmented &
Virtual Reality in Der Produktentstehung, vol. 343, Verlagsschriftenreihe
des Heinz Nixdorf Instituts, 2015, pp. 65–78.
short: 'J. Berssenbrügge, O. Wiederkehr, C. Jähn, M. Fischer, in: 12. Paderborner
Workshop Augmented & Virtual Reality in Der Produktentstehung, Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn, 2015, pp. 65–78.'
date_created: 2020-07-28T09:49:42Z
date_updated: 2022-01-06T06:53:11Z
department:
- _id: '63'
- _id: '26'
intvolume: ' 343'
language:
- iso: eng
page: 65-78
place: Paderborn
publication: 12. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung
publisher: Verlagsschriftenreihe des Heinz Nixdorf Instituts
status: public
title: Anbindung des Virtuellen Prototypen an die Partialmodelle intelligenter technischer
Systeme
type: conference
user_id: '15415'
volume: 343
year: '2015'
...
---
_id: '17427'
author:
- first_name: Claudius
full_name: Jähn, Claudius
last_name: Jähn
- first_name: Matthias
full_name: Fischer, Matthias
id: '146'
last_name: Fischer
- first_name: Maria
full_name: Gerges, Maria
last_name: Gerges
- first_name: Jan
full_name: Berssenbrügge, Jan
last_name: Berssenbrügge
citation:
ama: 'Jähn C, Fischer M, Gerges M, Berssenbrügge J. Automatische Ableitung geometrischer
Eigenschaften von Bauteilen aus dem 3-D-Polygonmodell. In: 12. Paderborner
Workshop Augmented & Virtual Reality in Der Produktentstehung. Vol 342.
Verlagsschriftenreihe des Heinz Nixdorf Instituts; 2015:107-120.'
apa: Jähn, C., Fischer, M., Gerges, M., & Berssenbrügge, J. (2015). Automatische
Ableitung geometrischer Eigenschaften von Bauteilen aus dem 3-D-Polygonmodell.
12. Paderborner Workshop Augmented & Virtual Reality in Der Produktentstehung,
342, 107–120.
bibtex: '@inproceedings{Jähn_Fischer_Gerges_Berssenbrügge_2015, place={Paderborn},
title={Automatische Ableitung geometrischer Eigenschaften von Bauteilen aus dem
3-D-Polygonmodell}, volume={342}, booktitle={12. Paderborner Workshop Augmented
& Virtual Reality in der Produktentstehung}, publisher={Verlagsschriftenreihe
des Heinz Nixdorf Instituts}, author={Jähn, Claudius and Fischer, Matthias and
Gerges, Maria and Berssenbrügge, Jan}, year={2015}, pages={107–120} }'
chicago: 'Jähn, Claudius, Matthias Fischer, Maria Gerges, and Jan Berssenbrügge.
“Automatische Ableitung Geometrischer Eigenschaften von Bauteilen Aus Dem 3-D-Polygonmodell.”
In 12. Paderborner Workshop Augmented & Virtual Reality in Der Produktentstehung,
342:107–20. Paderborn: Verlagsschriftenreihe des Heinz Nixdorf Instituts, 2015.'
ieee: C. Jähn, M. Fischer, M. Gerges, and J. Berssenbrügge, “Automatische Ableitung
geometrischer Eigenschaften von Bauteilen aus dem 3-D-Polygonmodell,” in 12.
Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung,
2015, vol. 342, pp. 107–120.
mla: Jähn, Claudius, et al. “Automatische Ableitung Geometrischer Eigenschaften
von Bauteilen Aus Dem 3-D-Polygonmodell.” 12. Paderborner Workshop Augmented
& Virtual Reality in Der Produktentstehung, vol. 342, Verlagsschriftenreihe
des Heinz Nixdorf Instituts, 2015, pp. 107–20.
short: 'C. Jähn, M. Fischer, M. Gerges, J. Berssenbrügge, in: 12. Paderborner Workshop
Augmented & Virtual Reality in Der Produktentstehung, Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn, 2015, pp. 107–120.'
date_created: 2020-07-28T10:23:18Z
date_updated: 2022-01-06T06:53:11Z
department:
- _id: '63'
- _id: '26'
intvolume: ' 342'
language:
- iso: eng
page: 107-120
place: Paderborn
publication: 12. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung
publisher: Verlagsschriftenreihe des Heinz Nixdorf Instituts
status: public
title: Automatische Ableitung geometrischer Eigenschaften von Bauteilen aus dem 3-D-Polygonmodell
type: conference
user_id: '15415'
volume: 342
year: '2015'
...
---
_id: '17431'
citation:
ama: 'Gausemeier J, Grafe M, Meyer auf der Heide F, eds. Augmented & Virtual
Reality in Der Produktentstehung: Grundlagen, Methoden Und Werkzeuge; Interaktions-
Und Visualisierungstechniken, Virtual Prototyping Intelligenter Technischer Systeme
Mit AR/VR. Vol 342. 12. Paderborner Workshop Augmented & Virtual Reality
in der Produktentstehung. Verlagsschriftenreihe des Heinz Nixdorf Instituts; 2015.'
apa: 'Gausemeier, J., Grafe, M., & Meyer auf der Heide, F. (Eds.). (2015). Augmented
& Virtual Reality in der Produktentstehung: Grundlagen, Methoden und Werkzeuge;
Interaktions- und Visualisierungstechniken, Virtual Prototyping intelligenter
technischer Systeme mit AR/VR (12. Paderborner Workshop Augmented & Virtual
Reality in der Produktentstehung, Vol. 342). Verlagsschriftenreihe des Heinz Nixdorf
Instituts.'
bibtex: '@book{Gausemeier_Grafe_Meyer auf der Heide_2015, place={Paderborn}, edition={12.
Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung},
title={Augmented & Virtual Reality in der Produktentstehung: Grundlagen, Methoden
und Werkzeuge; Interaktions- und Visualisierungstechniken, Virtual Prototyping
intelligenter technischer Systeme mit AR/VR}, volume={342}, publisher={Verlagsschriftenreihe
des Heinz Nixdorf Instituts}, year={2015} }'
chicago: 'Gausemeier, Jürgen, Michael Grafe, and Friedhelm Meyer auf der Heide,
eds. Augmented & Virtual Reality in Der Produktentstehung: Grundlagen,
Methoden Und Werkzeuge; Interaktions- Und Visualisierungstechniken, Virtual Prototyping
Intelligenter Technischer Systeme Mit AR/VR. 12. Paderborner Workshop Augmented
& Virtual Reality in der Produktentstehung. Vol. 342. Paderborn: Verlagsschriftenreihe
des Heinz Nixdorf Instituts, 2015.'
ieee: 'J. Gausemeier, M. Grafe, and F. Meyer auf der Heide, Eds., Augmented &
Virtual Reality in der Produktentstehung: Grundlagen, Methoden und Werkzeuge;
Interaktions- und Visualisierungstechniken, Virtual Prototyping intelligenter
technischer Systeme mit AR/VR, 12. Paderborner Workshop Augmented & Virtual
Reality in der Produktentstehung., vol. 342. Paderborn: Verlagsschriftenreihe
des Heinz Nixdorf Instituts, 2015.'
mla: 'Gausemeier, Jürgen, et al., editors. Augmented & Virtual Reality in
Der Produktentstehung: Grundlagen, Methoden Und Werkzeuge; Interaktions- Und Visualisierungstechniken,
Virtual Prototyping Intelligenter Technischer Systeme Mit AR/VR. 12. Paderborner
Workshop Augmented & Virtual Reality in der Produktentstehung, vol. 342, Verlagsschriftenreihe
des Heinz Nixdorf Instituts, 2015.'
short: 'J. Gausemeier, M. Grafe, F. Meyer auf der Heide, eds., Augmented & Virtual
Reality in Der Produktentstehung: Grundlagen, Methoden Und Werkzeuge; Interaktions-
Und Visualisierungstechniken, Virtual Prototyping Intelligenter Technischer Systeme
Mit AR/VR, 12. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung,
Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2015.'
date_created: 2020-07-28T13:39:25Z
date_updated: 2022-01-06T06:53:12Z
department:
- _id: '63'
- _id: '26'
edition: 12. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung
editor:
- first_name: Jürgen
full_name: Gausemeier, Jürgen
last_name: Gausemeier
- first_name: Michael
full_name: Grafe, Michael
last_name: Grafe
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
intvolume: ' 342'
language:
- iso: eng
place: Paderborn
publisher: Verlagsschriftenreihe des Heinz Nixdorf Instituts
status: public
title: 'Augmented & Virtual Reality in der Produktentstehung: Grundlagen, Methoden
und Werkzeuge; Interaktions- und Visualisierungstechniken, Virtual Prototyping intelligenter
technischer Systeme mit AR/VR'
type: book_editor
user_id: '15415'
volume: 342
year: '2015'
...
---
_id: '17657'
abstract:
- lang: eng
text: Inter-datacenter transfers of non-interactive but timely large flows over
a private (managed) network is an important problem faced by many cloud service
providers. The considered flows are non-interactive because they do not explicitly
target the end users. However, most of them must be performed on a timely basis
and are associated with a deadline. We propose to schedule these flows by a centralized
controller, which determines when to transmit each flow and which path to use.
Two scheduling models are presented in this paper. In the first, the controller
also determines the rate of each flow, while in the second bandwidth is assigned
by the network according to the TCP rules. We develop scheduling algorithms for
both models and compare their complexity and performance.
author:
- first_name: R.
full_name: Cohen, R.
last_name: Cohen
- first_name: Gleb
full_name: Polevoy, Gleb
id: '83983'
last_name: Polevoy
citation:
ama: Cohen R, Polevoy G. Inter-Datacenter Scheduling of Large Data Flows. Cloud
Computing, IEEE Transactions on. 2015;PP(99):1-1. doi:10.1109/TCC.2015.2487964
apa: Cohen, R., & Polevoy, G. (2015). Inter-Datacenter Scheduling of Large Data
Flows. Cloud Computing, IEEE Transactions On, PP(99), 1–1. https://doi.org/10.1109/TCC.2015.2487964
bibtex: '@article{Cohen_Polevoy_2015, title={Inter-Datacenter Scheduling of Large
Data Flows}, volume={PP}, DOI={10.1109/TCC.2015.2487964},
number={99}, journal={Cloud Computing, IEEE Transactions on}, author={Cohen, R.
and Polevoy, Gleb}, year={2015}, pages={1–1} }'
chicago: 'Cohen, R., and Gleb Polevoy. “Inter-Datacenter Scheduling of Large Data
Flows.” Cloud Computing, IEEE Transactions On PP, no. 99 (2015): 1–1. https://doi.org/10.1109/TCC.2015.2487964.'
ieee: R. Cohen and G. Polevoy, “Inter-Datacenter Scheduling of Large Data Flows,”
Cloud Computing, IEEE Transactions on, vol. PP, no. 99, pp. 1–1, 2015.
mla: Cohen, R., and Gleb Polevoy. “Inter-Datacenter Scheduling of Large Data Flows.”
Cloud Computing, IEEE Transactions On, vol. PP, no. 99, 2015, pp. 1–1,
doi:10.1109/TCC.2015.2487964.
short: R. Cohen, G. Polevoy, Cloud Computing, IEEE Transactions On PP (2015) 1–1.
date_created: 2020-08-06T15:20:58Z
date_updated: 2022-01-06T06:53:16Z
department:
- _id: '63'
- _id: '541'
doi: 10.1109/TCC.2015.2487964
extern: '1'
issue: '99'
keyword:
- Approximation algorithms
- Approximation methods
- Bandwidth
- Cloud computing
- Routing
- Schedules
- Scheduling
language:
- iso: eng
page: 1-1
publication: Cloud Computing, IEEE Transactions on
publication_identifier:
issn:
- 2168-7161
status: public
title: Inter-Datacenter Scheduling of Large Data Flows
type: journal_article
user_id: '83983'
volume: PP
year: '2015'
...
---
_id: '17658'
abstract:
- lang: eng
text: 'Abstract We study the problem of bandwidth allocation with multiple interferences.
In this problem the input consists of a set of users and a set of base stations.
Each user has a list of requests, each consisting of a base station, a frequency
demand, and a profit that may be gained by scheduling this request. The goal is
to find a maximum profit set of user requests S that satisfies the following conditions:
(i) S contains at most one request per user, (ii) the frequency sets allotted
to requests in S that correspond to the same base station are pairwise non-intersecting,
and (iii) the QoS received by any user at any frequency is reasonable according
to an interference model. In this paper we consider two variants of bandwidth
allocation with multiple interferences. In the first each request specifies a
demand that can be satisfied by any subset of frequencies that is large enough.
In the second each request specifies a specific frequency interval. Furthermore,
we consider two interference models, multiplicative and additive. We show that
these problems are extremely hard to approximate if the interferences depend on
both the interfered and the interfering base stations. On the other hand, we provide
constant factor approximation algorithms for both variants of bandwidth allocation
with multiple interferences for the case where the interferences depend only on
the interfering base stations. We also consider a restrictive special case that
is closely related to the Knapsack problem. We show that this special case is
NP-hard and that it admits an FPTAS. '
author:
- first_name: Reuven
full_name: Bar-Yehuda, Reuven
last_name: Bar-Yehuda
- first_name: Gleb
full_name: Polevoy, Gleb
id: '83983'
last_name: Polevoy
- first_name: Dror
full_name: Rawitz, Dror
last_name: Rawitz
citation:
ama: Bar-Yehuda R, Polevoy G, Rawitz D. Bandwidth allocation in cellular networks
with multiple interferences. Discrete Applied Mathematics . 2015;194:23-36.
doi:http://dx.doi.org/10.1016/j.dam.2015.05.013
apa: Bar-Yehuda, R., Polevoy, G., & Rawitz, D. (2015). Bandwidth allocation
in cellular networks with multiple interferences. Discrete Applied Mathematics
, 194, 23–36. http://dx.doi.org/10.1016/j.dam.2015.05.013
bibtex: '@article{Bar-Yehuda_Polevoy_Rawitz_2015, title={Bandwidth allocation in
cellular networks with multiple interferences}, volume={194}, DOI={http://dx.doi.org/10.1016/j.dam.2015.05.013},
journal={Discrete Applied Mathematics }, publisher={Elsevier}, author={Bar-Yehuda,
Reuven and Polevoy, Gleb and Rawitz, Dror}, year={2015}, pages={23–36} }'
chicago: 'Bar-Yehuda, Reuven, Gleb Polevoy, and Dror Rawitz. “Bandwidth Allocation
in Cellular Networks with Multiple Interferences.” Discrete Applied Mathematics
194 (2015): 23–36. http://dx.doi.org/10.1016/j.dam.2015.05.013.'
ieee: R. Bar-Yehuda, G. Polevoy, and D. Rawitz, “Bandwidth allocation in cellular
networks with multiple interferences,” Discrete Applied Mathematics , vol.
194, pp. 23–36, 2015.
mla: Bar-Yehuda, Reuven, et al. “Bandwidth Allocation in Cellular Networks with
Multiple Interferences.” Discrete Applied Mathematics , vol. 194, Elsevier,
2015, pp. 23–36, doi:http://dx.doi.org/10.1016/j.dam.2015.05.013.
short: R. Bar-Yehuda, G. Polevoy, D. Rawitz, Discrete Applied Mathematics 194 (2015)
23–36.
date_created: 2020-08-06T15:21:15Z
date_updated: 2022-01-06T06:53:16Z
department:
- _id: '63'
- _id: '541'
doi: http://dx.doi.org/10.1016/j.dam.2015.05.013
extern: '1'
intvolume: ' 194'
keyword:
- Local ratio
language:
- iso: eng
page: 23 - 36
publication: 'Discrete Applied Mathematics '
publication_identifier:
issn:
- 0166-218X
publisher: Elsevier
status: public
title: Bandwidth allocation in cellular networks with multiple interferences
type: journal_article
user_id: '83983'
volume: 194
year: '2015'
...
---
_id: '240'
abstract:
- lang: eng
text: We consider online leasing problems in which demands arrive over time and
need to be served by leasing resources. We introduce a new model for these problems
such that a resource can be leased for K different durations each incurring a
different cost (longer leases cost less per time unit). Each demand i can be served
anytime between its arrival ai and its deadline ai+di by a leased resource. The
objective is to meet all deadlines while minimizing the total leasing costs. This
model is a natural generalization of Meyerson’s ParkingPermitProblem (FOCS 2005)
in which di=0 for all i. We propose an online algorithm that is Θ(K+dmaxlmin)-competitive
where dmax and lmin denote the largest di and the shortest available lease length,
respectively. We also extend the SetCoverLeasing problem by deadlines and give
a competitive online algorithm which also improves on existing solutions for the
original SetCoverLeasing problem.
author:
- first_name: Shouwei
full_name: Li, Shouwei
last_name: Li
- first_name: Alexander
full_name: Mäcker, Alexander
id: '13536'
last_name: Mäcker
- first_name: Christine
full_name: Markarian, Christine
id: '37612'
last_name: Markarian
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Sören
full_name: Riechers, Sören
last_name: Riechers
citation:
ama: 'Li S, Mäcker A, Markarian C, Meyer auf der Heide F, Riechers S. Towards Flexible
Demands in Online Leasing Problems. In: Proceedings of the 21st Annual International
Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer
Science. ; 2015:277--288. doi:10.1007/978-3-319-21398-9_22'
apa: Li, S., Mäcker, A., Markarian, C., Meyer auf der Heide, F., & Riechers,
S. (2015). Towards Flexible Demands in Online Leasing Problems. In Proceedings
of the 21st Annual International Computing and Combinatorics Conference (COCOON)
(pp. 277--288). https://doi.org/10.1007/978-3-319-21398-9_22
bibtex: '@inproceedings{Li_Mäcker_Markarian_Meyer auf der Heide_Riechers_2015, series={Lecture
Notes in Computer Science}, title={Towards Flexible Demands in Online Leasing
Problems}, DOI={10.1007/978-3-319-21398-9_22},
booktitle={Proceedings of the 21st Annual International Computing and Combinatorics
Conference (COCOON)}, author={Li, Shouwei and Mäcker, Alexander and Markarian,
Christine and Meyer auf der Heide, Friedhelm and Riechers, Sören}, year={2015},
pages={277--288}, collection={Lecture Notes in Computer Science} }'
chicago: Li, Shouwei, Alexander Mäcker, Christine Markarian, Friedhelm Meyer auf
der Heide, and Sören Riechers. “Towards Flexible Demands in Online Leasing Problems.”
In Proceedings of the 21st Annual International Computing and Combinatorics
Conference (COCOON), 277--288. Lecture Notes in Computer Science, 2015. https://doi.org/10.1007/978-3-319-21398-9_22.
ieee: S. Li, A. Mäcker, C. Markarian, F. Meyer auf der Heide, and S. Riechers, “Towards
Flexible Demands in Online Leasing Problems,” in Proceedings of the 21st Annual
International Computing and Combinatorics Conference (COCOON), 2015, pp. 277--288.
mla: Li, Shouwei, et al. “Towards Flexible Demands in Online Leasing Problems.”
Proceedings of the 21st Annual International Computing and Combinatorics Conference
(COCOON), 2015, pp. 277--288, doi:10.1007/978-3-319-21398-9_22.
short: 'S. Li, A. Mäcker, C. Markarian, F. Meyer auf der Heide, S. Riechers, in:
Proceedings of the 21st Annual International Computing and Combinatorics Conference
(COCOON), 2015, pp. 277--288.'
date_created: 2017-10-17T12:41:38Z
date_updated: 2022-01-06T06:56:05Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-319-21398-9_22
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-21T10:28:50Z
date_updated: 2018-03-21T10:28:50Z
file_id: '1498'
file_name: 240-chp_3A10.1007_2F978-3-319-21398-9_22.pdf
file_size: 264482
relation: main_file
success: 1
file_date_updated: 2018-03-21T10:28:50Z
has_accepted_license: '1'
page: 277--288
project:
- _id: '1'
name: SFB 901
- _id: '16'
name: SFB 901 - Subprojekt C4
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '2'
name: SFB 901 - Project Area A
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the 21st Annual International Computing and Combinatorics
Conference (COCOON)
series_title: Lecture Notes in Computer Science
status: public
title: Towards Flexible Demands in Online Leasing Problems
type: conference
user_id: '15504'
year: '2015'
...
---
_id: '16449'
abstract:
- lang: eng
text: "We consider the following variant of the two dimensional gathering problem\r\nfor
swarms of robots: Given a swarm of $n$ indistinguishable, point shaped\r\nrobots
on a two dimensional grid. Initially, the robots form a closed chain on\r\nthe
grid and must keep this connectivity during the whole process of their\r\ngathering.
Connectivity means, that neighboring robots of the chain need to be\r\npositioned
at the same or neighboring points of the grid. In our model,\r\ngathering means
to keep shortening the chain until the robots are located\r\ninside a $2\\times
2$ subgrid. Our model is completely local (no global control,\r\nno global coordinates,
no compass, no global communication or vision, \\ldots).\r\nEach robot can only
see its next constant number of left and right neighbors on\r\nthe chain. This
fixed constant is called the \\emph{viewing path length}. All\r\nits operations
and detections are restricted to this constant number of robots.\r\nOther robots,
even if located at neighboring or the same grid point cannot be\r\ndetected. Only
based on the relative positions of its detectable chain\r\nneighbors, a robot
can decide to obtain a certain state. Based on this state\r\nand their local knowledge,
the robots do local modifications to the chain by\r\nmoving to neighboring grid
points without breaking the chain. These\r\nmodifications are performed without
the knowledge whether they lead to a global\r\nprogress or not. We assume the
fully synchronous $\\mathcal{FSYNC}$ model. For\r\nthis problem, we present a
gathering algorithm which needs linear time. This\r\nresult generalizes the result
from \\cite{hopper}, where an open chain with\r\nspecified distinguishable (and
fixed) endpoints is considered."
author:
- first_name: Sebastian
full_name: Abshoff, Sebastian
last_name: Abshoff
- first_name: 'Andreas '
full_name: 'Cord-Landwehr, Andreas '
last_name: Cord-Landwehr
- 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: Abshoff S, Cord-Landwehr A, Fischer M, Jung D, Meyer auf der Heide F. Gathering
a Closed Chain of Robots on a Grid. arXiv:151005454. 2015.
apa: Abshoff, S., Cord-Landwehr, A., Fischer, M., Jung, D., & Meyer auf der
Heide, F. (2015). Gathering a Closed Chain of Robots on a Grid. ArXiv:1510.05454.
bibtex: '@article{Abshoff_Cord-Landwehr_Fischer_Jung_Meyer auf der Heide_2015, title={Gathering
a Closed Chain of Robots on a Grid}, journal={arXiv:1510.05454}, author={Abshoff,
Sebastian and Cord-Landwehr, Andreas and Fischer, Matthias and Jung, Daniel and
Meyer auf der Heide, Friedhelm}, year={2015} }'
chicago: Abshoff, Sebastian, Andreas Cord-Landwehr, Matthias Fischer, Daniel Jung,
and Friedhelm Meyer auf der Heide. “Gathering a Closed Chain of Robots on a Grid.”
ArXiv:1510.05454, 2015.
ieee: S. Abshoff, A. Cord-Landwehr, M. Fischer, D. Jung, and F. Meyer auf der Heide,
“Gathering a Closed Chain of Robots on a Grid,” arXiv:1510.05454. 2015.
mla: Abshoff, Sebastian, et al. “Gathering a Closed Chain of Robots on a Grid.”
ArXiv:1510.05454, 2015.
short: S. Abshoff, A. Cord-Landwehr, M. Fischer, D. Jung, F. Meyer auf der Heide,
ArXiv:1510.05454 (2015).
date_created: 2020-04-07T07:20:46Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
external_id:
arxiv:
- '1510.05454'
language:
- iso: eng
publication: arXiv:1510.05454
status: public
title: Gathering a Closed Chain of Robots on a Grid
type: preprint
user_id: '15415'
year: '2015'
...
---
_id: '16452'
abstract:
- lang: eng
text: "We consider the problem of dominating set-based virtual backbone used for\r\nrouting
in asymmetric wireless ad-hoc networks. These networks have non-uniform\r\ntransmission
ranges and are modeled using the well-established disk graphs. The\r\ncorresponding
graph theoretic problem seeks a strongly connected\r\ndominating-absorbent set
of minimum cardinality in a digraph. A subset of nodes\r\nin a digraph is a strongly
connected dominating-absorbent set if the subgraph\r\ninduced by these nodes is
strongly connected and each node in the graph is\r\neither in the set or has both
an in-neighbor and an out-neighbor in it.\r\nDistributed algorithms for this problem
are of practical significance due to\r\nthe dynamic nature of ad-hoc networks.
We present a first distributed\r\napproximation algorithm, with a constant approximation
factor and O(Diam)\r\nrunning time, where Diam is the diameter of the graph. Moreover
we present a\r\nsimple heuristic algorithm and conduct an extensive simulation
study showing\r\nthat our heuristic outperforms previously known approaches for
the problem."
author:
- first_name: 'Faisal N. '
full_name: 'Abu-Khzam, Faisal N. '
last_name: Abu-Khzam
- 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: Michael
full_name: Schubert, Michael
last_name: Schubert
citation:
ama: Abu-Khzam FN, Markarian C, Meyer auf der Heide F, Schubert M. Approximation
and Heuristic Algorithms for Computing Backbones in Asymmetric Ad-Hoc Networks.
arXiv:151001866. 2015.
apa: Abu-Khzam, F. N., Markarian, C., Meyer auf der Heide, F., & Schubert, M.
(2015). Approximation and Heuristic Algorithms for Computing Backbones in Asymmetric
Ad-Hoc Networks. ArXiv:1510.01866.
bibtex: '@article{Abu-Khzam_Markarian_Meyer auf der Heide_Schubert_2015, title={Approximation
and Heuristic Algorithms for Computing Backbones in Asymmetric Ad-Hoc Networks},
journal={arXiv:1510.01866}, author={Abu-Khzam, Faisal N. and Markarian, Christine
and Meyer auf der Heide, Friedhelm and Schubert, Michael}, year={2015} }'
chicago: Abu-Khzam, Faisal N. , Christine Markarian, Friedhelm Meyer auf der Heide,
and Michael Schubert. “Approximation and Heuristic Algorithms for Computing Backbones
in Asymmetric Ad-Hoc Networks.” ArXiv:1510.01866, 2015.
ieee: F. N. Abu-Khzam, C. Markarian, F. Meyer auf der Heide, and M. Schubert, “Approximation
and Heuristic Algorithms for Computing Backbones in Asymmetric Ad-Hoc Networks,”
arXiv:1510.01866. 2015.
mla: Abu-Khzam, Faisal N., et al. “Approximation and Heuristic Algorithms for Computing
Backbones in Asymmetric Ad-Hoc Networks.” ArXiv:1510.01866, 2015.
short: F.N. Abu-Khzam, C. Markarian, F. Meyer auf der Heide, M. Schubert, ArXiv:1510.01866
(2015).
date_created: 2020-04-07T12:22:48Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
external_id:
arxiv:
- '1510.01866'
language:
- iso: eng
publication: arXiv:1510.01866
status: public
title: Approximation and Heuristic Algorithms for Computing Backbones in Asymmetric
Ad-Hoc Networks
type: preprint
user_id: '15415'
year: '2015'
...