@misc{5406,
author = {Bülling, Jonas},
title = {{Parallelisierung von Algorithmen zur IR-Luftbildanalyse von Laubholzmischbeständen zur Verifizierung der Ausbreitung von Eichenkomplexschäden}},
year = {2016},
}
@misc{688,
author = {Kutzias, Damian},
publisher = {Universität Paderborn},
title = {{Friendship Processes in Network Creation Games}},
year = {2016},
}
@misc{1082,
author = {Handirk, Tobias},
publisher = {Universität Paderborn},
title = {{Über die Rolle von Informationen in Verkehrsnetzwerken}},
year = {2016},
}
@article{139,
abstract = {We consider online optimization problems in which certain goods have to be acquired in order to provide a service or infrastructure. Classically, decisions for such problems are considered as final: one buys the goods. However, in many real world applications, there is a shift away from the idea of buying goods. Instead, leasing is often a more flexible and lucrative business model. Research has realized this shift and recently initiated the theoretical study of leasing models (Anthony and Gupta in Proceedings of the integer programming and combinatorial optimization: 12th International IPCO Conference, Ithaca, NY, USA, June 25–27, 2007; Meyerson in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23–25 Oct 2005, Pittsburgh, PA, USA, 2005; Nagarajan and Williamson in Discret Optim 10(4):361–370, 2013) We extend this line of work and suggest a more systematic study of leasing aspects for a class of online optimization problems. We provide two major technical results. We introduce the leasing variant of online set multicover and give an O(log(mK)logn)-competitive algorithm (with n, m, and K being the number of elements, sets, and leases, respectively). Our results also imply improvements for the non-leasing variant of online set cover. Moreover, we extend results for the leasing variant of online facility location. Nagarajan and Williamson (Discret Optim 10(4):361–370, 2013) gave an O(Klogn)-competitive algorithm for this problem (with n and K being the number of clients and leases, respectively). We remove the dependency on n (and, thereby, on time). In general, this leads to a bound of O(lmaxloglmax) (with the maximal lease length lmax). For many natural problem instances, the bound improves to O(K2).},
author = {Abshoff, Sebastian and Kling, Peter and Markarian, Christine and Meyer auf der Heide, Friedhelm and Pietrzyk, Peter },
journal = {Journal of Combinatorial Optimization},
number = {4},
pages = { 1197----1216},
publisher = {Springer},
title = {{Towards the price of leasing online}},
doi = {10.1007/s10878-015-9915-5},
year = {2016},
}
@inproceedings{16351,
author = {Fischer, Matthias and Jähn, Claudius and Meyer auf der Heide, Friedhelm and Petring, Ralf},
booktitle = {Algorithm Engineering},
editor = {Kliemann, Lasse and Sanders, Peter},
pages = {226--244},
publisher = {Springer},
title = {{Algorithm Engineering Aspects of Real-Time Rendering Algorithms}},
doi = {10.1007/978-3-319-49487-6_7 },
volume = {9220},
year = {2016},
}
@inproceedings{177,
abstract = {Efficiently parallelizable parameterized problems have been classified as being either in the class FPP (fixed-parameter parallelizable) or the class PNC (parameterized analog of NC), which contains FPP as a subclass. In this paper, we propose a more restrictive class of parallelizable parameterized problems called fixed-parameter parallel-tractable (FPPT). For a problem to be in FPPT, it should possess an efficient parallel algorithm not only from a theoretical standpoint but in practice as well. The primary distinction between FPPT and FPP is the parallel processor utilization, which is bounded by a polynomial function in the case of FPPT. We initiate the study of FPPT with the well-known k-vertex cover problem. In particular, we present a parallel algorithm that outperforms the best known parallel algorithm for this problem: using O(m) instead of O(n2) parallel processors, the running time improves from 4logn+O(kk) to O(k⋅log3n), where m is the number of edges, n is the number of vertices of the input graph, and k is an upper bound of the size of the sought vertex cover. We also note that a few P-complete problems fall into FPPT including the monotone circuit value problem (MCV) when the underlying graphs are bounded by a constant Euler genus.},
author = {Abu-Khzam, Faisal N. and Li, Shouwei and Markarian, Christine and Meyer auf der Heide, Friedhelm and Podlipyan, Pavel},
booktitle = {Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA)},
pages = {477--488},
title = {{On the Parameterized Parallel Complexity and the Vertex Cover Problem}},
doi = {10.1007/978-3-319-48749-6_35},
year = {2016},
}
@inproceedings{209,
abstract = {We study a new class of games which generalizes congestion games and its bottleneck variant. We introduce congestion games with mixed objectives to model network scenarios in which players seek to optimize for latency and bandwidths alike. We characterize the existence of pure Nash equilibria (PNE) and the convergence of improvement dynamics. For games that do not possess PNE we give bounds on the approximation ratio of approximate pure Nash equilibria.},
author = {Feldotto, Matthias and Leder, Lennart and Skopalik, Alexander},
booktitle = {Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)},
pages = {655----669},
title = {{Congestion Games with Mixed Objectives}},
doi = {10.1007/978-3-319-48749-6_47},
year = {2016},
}
@misc{5407,
author = {Koepe, Jörn},
title = {{Price-Based Allocation Games}},
year = {2016},
}
@misc{689,
author = {Schaefer, Johannes Sebastian},
publisher = {Universität Paderborn},
title = {{Routing Algorithms on Delayed Networks for Disaster Management Support}},
year = {2016},
}
@phdthesis{154,
author = {Cord Landwehr, Andreas},
publisher = {Universität Paderborn},
title = {{Selfish Network Creation - On Variants of Network Creation Games}},
year = {2016},
}
@article{159,
abstract = {Abstract—Max-min fairness (MMF) is a widely known approachto a fair allocation of bandwidth to each of the usersin a network. This allocation can be computed by uniformlyraising the bandwidths of all users without violating capacityconstraints. We consider an extension of these allocations byraising the bandwidth with arbitrary and not necessarily uniformtime-depending velocities (allocation rates). These allocationsare used in a game-theoretic context for routing choices, whichwe formalize in progressive filling games (PFGs). We present avariety of results for equilibria in PFGs. We show that these gamespossess pure Nash and strong equilibria. While computation ingeneral is NP-hard, there are polynomial-time algorithms forprominent classes of Max-Min-Fair Games (MMFG), includingthe case when all users have the same source-destination pair.We characterize prices of anarchy and stability for pure Nashand strong equilibria in PFGs and MMFGs when players havedifferent or the same source-destination pairs. In addition, weshow that when a designer can adjust allocation rates, it is possibleto design games with optimal strong equilibria. Some initial resultson polynomial-time algorithms in this direction are also derived.},
author = {Harks, Tobias and Höfer, Martin and Schewior, Kevin and Skopalik, Alexander},
journal = {IEEE/ACM Transactions on Networking},
number = {4},
pages = {2553 -- 2562},
publisher = {IEEE},
title = {{Routing Games With Progressive Filling}},
doi = {10.1109/TNET.2015.2468571},
year = {2016},
}
@inproceedings{16364,
author = {Macker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm},
booktitle = {2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS)},
isbn = {9781509021406},
title = {{On Competitive Algorithms for Approximations of Top-k-Position Monitoring of Distributed Streams}},
doi = {10.1109/ipdps.2016.91},
year = {2016},
}
@phdthesis{200,
author = {Drees, Maximilian},
publisher = {Universität Paderborn},
title = {{Existence and Properties of Pure Nash Equilibria in Budget Games}},
year = {2016},
}
@article{16391,
author = {Degener, Bastian and Kempkes, Barbara and Kling, Peter and Meyer auf der Heide, Friedhelm},
issn = {2329-4949},
journal = {ACM Transactions on Parallel Computing},
pages = {1--18},
title = {{Linear and Competitive Strategies for Continuous Robot Formation Problems}},
doi = {10.1145/2742341},
year = {2015},
}
@misc{251,
author = {Pfannschmidt, Karlson},
publisher = {Universität Paderborn},
title = {{Solving the aggregated bandits problem}},
year = {2015},
}
@inproceedings{275,
abstract = {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 = {Cord-Landwehr, Andreas and Lenzner, Pascal},
booktitle = {Proceedings of the 40th Conference on Mathematical Foundations of Computer Science (MFCS)},
pages = {248----260},
title = {{Network Creation Games: Think Global - Act Local}},
doi = {10.1007/978-3-662-48054-0_21},
year = {2015},
}
@phdthesis{270,
author = {Abshoff, Sebastian},
publisher = {Universität Paderborn},
title = {{On the Complexity of Fundamental Problems in Dynamic Ad-hoc Networks}},
year = {2015},
}
@unpublished{16397,
abstract = {In the gathering problem, n autonomous robots have to meet on a single point.
We consider the gathering of a closed chain of point-shaped, anonymous robots
on a grid. The robots only have local knowledge about a constant number of
neighboring robots along the chain in both directions. Actions are performed in
the fully synchronous time model FSYNC. Every robot has a limited memory that
may contain one timestamp of the global clock, also visible to its direct
neighbors. In this synchronous time model, there is no limited view gathering
algorithm known to perform better than in quadratic runtime. The configurations
that show the quadratic lower bound are closed chains. In this paper, we
present the first sub-quadratic---in fact linear time---gathering algorithm for
closed chains on a grid.},
author = {Abshoff, Sebastian and Andreas Cord-Landwehr, Andreas and Jung, Daniel and Meyer auf der Heide, Friedhelm},
booktitle = {ArXiv: 1501.04877},
title = {{Towards Gathering Robots with Limited View in Linear Time: The Closed Chain Case}},
year = {2015},
}
@inproceedings{240,
abstract = {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 = {Li, Shouwei and Mäcker, Alexander and Markarian, Christine and Meyer auf der Heide, Friedhelm and Riechers, Sören},
booktitle = {Proceedings of the 21st Annual International Computing and Combinatorics Conference (COCOON)},
pages = {277----288},
title = {{Towards Flexible Demands in Online Leasing Problems}},
doi = {10.1007/978-3-319-21398-9_22},
year = {2015},
}
@inproceedings{271,
abstract = {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 = {Drees, Maximilian and Feldotto, Matthias and Riechers, Sören and Skopalik, Alexander},
booktitle = {Proceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT)},
pages = {178--189},
title = {{On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games}},
doi = {10.1007/978-3-662-48433-3_14},
year = {2015},
}