@inproceedings{20004,
author = {{Valentini, Gabriele and Brambilla, Davide and Hamann, Heiko and Dorigo, Marco}},
booktitle = {{10th Int. Conf. on Swarm Intelligence, ANTS 2016}},
isbn = {{9783319444260}},
issn = {{0302-9743}},
title = {{{Collective Perception of Environmental Features in a Robot Swarm}}},
doi = {{10.1007/978-3-319-44427-7_6}},
year = {{2016}},
}
@misc{210,
author = {{Leder, Lennart}},
publisher = {{Universität Paderborn}},
title = {{{Congestion Games with Mixed Objectives}}},
year = {{2016}},
}
@inproceedings{215,
abstract = {{We present three robust overlay networks: First, we present a network that organizes the nodes into an expander and is resistant to even massive adversarial churn. Second, we develop a network based on the hypercube that maintains connectivity under adversarial DoS-attacks. For the DoS-attacks we use the notion of a Omega(log log n)-late adversary which only has access to topological information that is at least Omega(log log n) rounds old. Finally, we develop a network that combines both churn- and DoS-resistance. The networks gain their robustness through constant network reconfiguration, i.e., the topology of the networks changes constantly. Our reconguration algorithms are based on node sampling primitives for expanders and hypercubes that allow each node to sample a logarithmic number of nodes uniformly at random in O(log log n) communication rounds. These primitives are specific to overlay networks and their optimal runtime represents an exponential improvement over known techniques. Our results have a wide range of applications, for example in the area of scalable and robust peer-to-peer systems.}},
author = {{Drees, Maximilian and Gmyr, Robert and Scheideler, Christian}},
booktitle = {{Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}},
pages = {{417----427}},
title = {{{Churn- and DoS-resistant Overlay Networks Based on Network Reconfiguration}}},
doi = {{10.1145/2935764.2935783}},
year = {{2016}},
}
@inproceedings{17655,
author = {{Polevoy, Gleb and de Weerdt, M.M. and Jonker, C.M.}},
booktitle = {{Proceedings of the 2016 European Conference on Artificial Intelligence}},
keywords = {{agents, action, repeated reciprocation, fixed, floating, network, Nash equilibrium, social welfare, price of anarchy, price of stability, convex combination}},
pages = {{417--425}},
title = {{{The Game of Reciprocation Habits}}},
doi = {{10.3233/978-1-61499-672-9-417}},
volume = {{Volume 285: ECAI 2016}},
year = {{2016}},
}
@inproceedings{17656,
author = {{Polevoy, Gleb and de Weerdt, Mathijs and Jonker, Catholijn}},
booktitle = {{Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems}},
isbn = {{978-1-4503-4239-1}},
keywords = {{agent's influence, behavior, convergence, perron-frobenius, reciprocal interaction, repeated reciprocation}},
pages = {{1431--1432}},
publisher = {{International Foundation for Autonomous Agents and Multiagent Systems}},
title = {{{The Convergence of Reciprocation}}},
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}},
}
@misc{187,
booktitle = {{Transactions on Parallel Computing (TOPC)}},
editor = {{Meyer auf der Heide, Friedhelm}},
number = {{1}},
pages = {{1}},
title = {{{Introduction to the Special Issue on SPAA 2014}}},
doi = {{10.1145/2936716}},
year = {{2016}},
}
@inproceedings{207,
abstract = {{We consider a scheduling problem where machines need to be rented from the cloud in order to process jobs. There are two types of machines available which can be rented for machine-type dependent prices and for arbitrary durations. However, a machine-type dependent setup time is required before a machine is available for processing. Jobs arrive online over time, have machine-type dependent sizes and have individual deadlines. The objective is to rent machines and schedule jobs so as to meet all deadlines while minimizing the rental cost. Since we observe the slack of jobs to have a fundamental influence on the competitiveness, we study the model when instances are parameterized by their (minimum) slack. An instance is called to have a slack of $\beta$ if, for all jobs, the difference between the job's release time and the latest point in time at which it needs to be started is at least $\beta$. While for $\beta series = {LNCS}}},
author = {{Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören}},
booktitle = {{Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)}},
pages = {{578----592}},
title = {{{Cost-efficient Scheduling on Machines from the Cloud}}},
doi = {{10.1007/978-3-319-48749-6_42}},
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{5406,
author = {{Bülling, Jonas}},
title = {{{Parallelisierung von Algorithmen zur IR-Luftbildanalyse von Laubholzmischbeständen zur Verifizierung der Ausbreitung von Eichenkomplexschäden}}},
year = {{2016}},
}