@phdthesis{1209,
author = {Jung, Daniel},
publisher = {Universität Paderborn},
title = {{Local Strategies for Swarm Formations on a Grid}},
doi = {10.17619/UNIPB/1-271},
year = {2018},
}
@inproceedings{2485,
author = {Feldkord, Björn and Meyer auf der Heide, Friedhelm},
booktitle = {Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
location = {Wien},
pages = {373 -- 381 },
publisher = {ACM},
title = {{Online Facility Location with Mobile Facilities}},
doi = {10.1145/3210377.3210389},
year = {2018},
}
@misc{3851,
author = {Koop, Samuel},
publisher = {Universität Paderborn},
title = {{Congestion Games mit gewichteten Strategien}},
year = {2018},
}
@inproceedings{4563,
abstract = {Routing is a challenging problem for wireless ad hoc networks, especially when the nodes are mobile and spread so widely that in most cases multiple hops are needed to route a message from one node to another. In fact, it is known that any online routing protocol has a poor performance in the worst case, in a sense that there is a distribution of nodes resulting in bad routing paths for that protocol, even if the nodes know their geographic positions and the geographic position of the destination of a message is known. The reason for that is that radio holes in the ad hoc network may require messages to take long detours in order to get to a destination, which are hard to find in an online fashion.
In this paper, we assume that the wireless ad hoc network can make limited use of long-range links provided by a global communication infrastructure like a cellular infrastructure or a satellite in order to compute an abstraction of the wireless ad hoc network that allows the messages to be sent along near-shortest paths in the ad hoc network. We present distributed algorithms that compute an abstraction of the ad hoc network in $\mathcal{O}\left(\log ^2 n\right)$ time using long-range links, which results in $c$-competitive routing paths between any two nodes of the ad hoc network for some constant $c$ if the convex hulls of the radio holes do not intersect. We also show that the storage needed for the abstraction just depends on the number and size of the radio holes in the wireless ad hoc network and is independent on the total number of nodes, and this information just has to be known to a few nodes for the routing to work.
},
author = {Jung, Daniel and Kolb, Christina and Scheideler, Christian and Sundermeier, Jannik},
booktitle = {Proceedings of the 14th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS) },
keyword = {greedy routing, ad hoc networks, convex hulls, c-competitiveness},
location = {Helsinki},
publisher = {Springer},
title = {{Competitive Routing in Hybrid Communication Networks}},
year = {2018},
}
@misc{5403,
author = {Geromel, Marcel},
title = {{Mobile Facility Leasing}},
year = {2018},
}
@inproceedings{112,
abstract = {We study a model of selfish resource allocation that seeks to incorporate dependencies among resources as they exist in in modern networked environments. Our model is inspired by utility functions with constant elasticity of substitution (CES) which is a well-studied model in economics. We consider congestion games with different aggregation functions. In particular, we study $L_p$ norms and analyze the existence and complexity of (approximate) pure Nash equilibria. Additionally, we give an almost tight characterization based on monotonicity properties to describe the set of aggregation functions that guarantee the existence of pure Nash equilibria.},
author = {Feldotto, Matthias and Leder, Lennart and Skopalik, Alexander},
booktitle = {Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC)},
pages = {222----233},
title = {{Congestion Games with Complementarities}},
doi = {10.1007/978-3-319-57586-5_19},
year = {2017},
}
@inproceedings{16339,
abstract = {In der CAD-unterstützten Entwicklung von technischen Systemen (Maschinen, Anlagen etc.) werden virtuelle Prototypen im Rahmen eines virtuellen Design-Reviews mit Hilfe eines VR-Systems gesamtheitlich betrachtet, um frühzeitig Fehler und Verbesserungsbedarf zu erkennen. Ein wichtiger Untersuchungsgegenstand ist dabei die Analyse von Transportwegen für den Materialtransport mittels Fließbändern, Förderketten oder schienenbasierten Transportsystemen. Diese Transportwege werden im VR-System animiert. Problematisch dabei ist, dass derartige Transportsysteme im zugrundeliegenden CAD-Modell in der Praxis oft nicht modelliert und nur exemplarisch angedeutet werden, da diese für die Konstruktion nicht relevant sind (z.B. der Fördergurt eines Förderbandes, oder die Kette einer Förderkette), oder die Informationen über den Verlauf bei der Konvertierung der Daten in das VR-System verloren gehen. Bei der Animation dieser Transportsysteme in einem VR-System muss der Transportweg also aufwändig, manuell nachgearbeitet werden. Das Ziel dieser Arbeit ist die Reduzierung des notwendigen manuellen Nachbearbeitungsaufwandes für das Design-Review durch eine automatische Berechnung der Animationspfade entlang eines Transportsystems. Es wird ein Algorithmus vorgestellt, der es ermöglicht mit nur geringem zeitlichem Benutzeraufwand den Animationspfad aus den reinen polygonalen dreidimensionalen Daten eines Transportsystems automatisch zu rekonstruieren.},
author = {Brandt, Sascha and Fischer, Matthias},
booktitle = {Wissenschaftsforum Intelligente Technische Systeme (WInTeSys) 2017},
location = {Paderborn},
pages = {415--427},
publisher = {Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn},
title = {{Automatische Ableitung der Transportwege von Transportsystemen aus dem 3D-Polygonmodell}},
volume = {369},
year = {2017},
}
@inproceedings{59,
abstract = {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 = {Kling, Peter and Mäcker, Alexander and Riechers, Sören and Skopalik, Alexander},
booktitle = {Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
pages = {123----132},
title = {{Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource}},
doi = {10.1145/3087556.3087578},
year = {2017},
}
@inproceedings{66,
abstract = {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 = {Drees, Maximilian and Feldotto, Matthias and Riechers, Sören and Skopalik, Alexander},
booktitle = {Proceedings of the 23rd International Computing and Combinatorics Conference (COCOON)},
pages = {175----187},
title = {{Pure Nash Equilibria in Restricted Budget Games}},
doi = {10.1007/978-3-319-62389-4_15},
year = {2017},
}
@article{706,
author = {Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören},
journal = {Journal of Combinatorial Optimization},
number = {4},
pages = {1168--1194},
publisher = {Springer},
title = {{Cost-efficient Scheduling on Machines from the Cloud}},
doi = {10.1007/s10878-017-0198-x},
volume = {36},
year = {2017},
}
@inbook{16461,
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 Riechers, Sören and Schaefer, Johannes and Sundermeier, Jannik},
booktitle = {Structural Information and Communication Complexity},
isbn = {9783319720494},
issn = {0302-9743},
title = {{Monitoring of Domain-Related Problems in Distributed Data Streams}},
doi = {10.1007/978-3-319-72050-0_13},
year = {2017},
}
@misc{1080,
author = {Bürmann, Jan},
publisher = {Universität Paderborn},
title = {{Complexity of Signalling in Routing Games under Uncertainty}},
year = {2017},
}
@misc{1073,
author = {Nachtigall, Simon},
publisher = {Universität Paderborn},
title = {{Sortieren dynamischer Daten}},
year = {2017},
}
@inproceedings{113,
abstract = {We study the computation of approximate pure Nash equilibria in Shapley value (SV) weighted congestion games, introduced in [19]. This class of games considers weighted congestion games in which Shapley values are used as an alternative (to proportional shares) for distributing the total cost of each resource among its users. We focus on the interesting subclass of such games with polynomial resource cost functions and present an algorithm that computes approximate pure Nash equilibria with a polynomial number of strategy updates. Since computing a single strategy update is hard, we apply sampling techniques which allow us to achieve polynomial running time. The algorithm builds on the algorithmic ideas of [7], however, to the best of our knowledge, this is the first algorithmic result on computation of approximate equilibria using other than proportional shares as player costs in this setting. We present a novel relation that approximates the Shapley value of a player by her proportional share and vice versa. As side results, we upper bound the approximate price of anarchy of such games and significantly improve the best known factor for computing approximate pure Nash equilibria in weighted congestion games of [7].},
author = {Feldotto, Matthias and Gairing, Martin and Kotsialou, Grammateia and Skopalik, Alexander},
booktitle = {Proceedings of the 13th International Conference on Web and Internet Economics (WINE)},
title = {{Computing Approximate Pure Nash Equilibria in Shapley Value Weighted Congestion Games}},
doi = {10.1007/978-3-319-71924-5_14},
year = {2017},
}
@inproceedings{16347,
author = {Fischer, Matthias and Jung, Daniel and Meyer auf der Heide, Friedhelm},
booktitle = {Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, {ALGOSENSORS}},
editor = {Fernández Anta, Antonio and Jurdzinski, Tomasz and Mosteiro, Miguel A. and Zhang, Yanyong},
pages = {168--181},
publisher = {Springer},
title = {{Gathering Anonymous, Oblivious Robots on a Grid}},
doi = {10.1007/978-3-319-72751-6_13},
volume = {10718},
year = {2017},
}
@inproceedings{55,
abstract = {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 = {Feldkord, Björn and Meyer auf der Heide, Friedhelm},
booktitle = {Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
pages = {313--319},
title = {{The Mobile Server Problem}},
doi = {10.1145/3087556.3087575},
year = {2017},
}
@inproceedings{79,
abstract = {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 = {Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören},
booktitle = {Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)},
pages = {207--222},
publisher = {Springer},
title = {{Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times}},
doi = {10.1007/978-3-319-89441-6},
volume = {10787},
year = {2017},
}
@misc{1081,
author = {Vijayalakshmi, Vipin Ravindran},
publisher = {Universität Paderborn},
title = {{Bounding the Inefficiency of Equilibria in Congestion Games under Taxation}},
year = {2017},
}
@misc{1074,
author = {Pukrop, Simon},
publisher = {Universität Paderborn},
title = {{Robuste Optimierung in Congestion Games}},
year = {2017},
}
@inproceedings{16348,
author = {Biermeier, Felix and Feldkord, Björn and Malatyali, Manuel and Meyer auf der Heide, Friedhelm},
booktitle = {Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)},
pages = {285 -- 300},
publisher = {Springer},
title = {{A Communication-Efficient Distributed Data Structure for Top-k and k-Select Queries}},
doi = {10.1007/978-3-319-89441-6_21},
year = {2017},
}