@inproceedings{16349,
author = {Podlipyan, Pavel and Li, Shouwei and Markarian, Christine and Meyer auf der Heide, Friedhelm},
booktitle = {Proceedings of the 13th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS)},
pages = {182--197},
title = {{A Continuous Strategy for Collisionless Gathering}},
doi = {10.1007/978-3-319-72751-6_14 },
year = {2017},
}
@phdthesis{704,
author = {Riechers, Sören},
publisher = {Universität Paderborn},
title = {{Scheduling with Scarce Resources}},
doi = {10.17619/UNIPB/1-231},
year = {2017},
}
@inproceedings{17652,
author = {Polevoy, Gleb and Trajanovski, Stojan and Grosso, Paola and de Laat, Cees},
booktitle = {Combinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I},
isbn = {978-3-319-71150-8},
keyword = {flow, filter, MMSA, set cover, approximation, local ratio algorithm},
pages = {3--17},
publisher = {Springer International Publishing},
title = {{Filtering Undesirable Flows in Networks}},
doi = {10.1007/978-3-319-71150-8_1},
year = {2017},
}
@unpublished{17811,
abstract = {We consider a swarm of $n$ autonomous mobile robots, distributed on a
2-dimensional grid. A basic task for such a swarm is the gathering process: All
robots have to gather at one (not predefined) place. A common local model for
extremely simple robots is the following: The robots do not have a common
compass, only have a constant viewing radius, are autonomous and
indistinguishable, can move at most a constant distance in each step, cannot
communicate, are oblivious and do not have flags or states. The only gathering
algorithm under this robot model, with known runtime bounds, needs
$\mathcal{O}(n^2)$ rounds and works in the Euclidean plane. The underlying time
model for the algorithm is the fully synchronous $\mathcal{FSYNC}$ model. On
the other side, in the case of the 2-dimensional grid, the only known gathering
algorithms for the same time and a similar local model additionally require a
constant memory, states and "flags" to communicate these states to neighbors in
viewing range. They gather in time $\mathcal{O}(n)$.
In this paper we contribute the (to the best of our knowledge) first
gathering algorithm on the grid that works under the same simple local model as
the above mentioned Euclidean plane strategy, i.e., without memory (oblivious),
"flags" and states. We prove its correctness and an $\mathcal{O}(n^2)$ time
bound in the fully synchronous $\mathcal{FSYNC}$ time model. This time bound
matches the time bound of the best known algorithm for the Euclidean plane
mentioned above. We say gathering is done if all robots are located within a
$2\times 2$ square, because in $\mathcal{FSYNC}$ such configurations cannot be
solved.},
author = {Fischer, Matthias and Jung, Daniel and Meyer auf der Heide, Friedhelm},
booktitle = {arXiv:1702.03400},
title = {{Gathering Anonymous, Oblivious Robots on a Grid}},
year = {2017},
}
@inproceedings{1095,
abstract = {Many university students struggle with motivational problems, and gamification has the potential to address these problems. However, using gamification currently is rather tedious and time-consuming for instructors because current approaches to gamification require instructors to engage in the time-consuming preparation of course contents (e.g., for quizzes or mini-games). In reply to this issue, we propose a “lean” approach to gamification, which relies on gamifying learning activities rather than learning contents. The learning activities that are gamified in the lean approach can typically be drawn from existing course syllabi (e.g., attend certain lectures, hand in assignments, read book chapters and articles). Hence, compared to existing approaches, lean gamification substantially lowers the time requirements posed on instructors for gamifying a given course. Drawing on research on limited attention and the present bias, we provide the theoretical foundation for the lean gamification approach. In addition, we present a mobile application that implements lean gamification and outline a mixed-methods study that is currently under way for evaluating whether lean gamification does indeed have the potential to increase students’ motivation. We thereby hope to allow more students and instructors to benefit from the advantages of gamification. },
author = {John, Thomas and Feldotto, Matthias and Hemsen, Paul and Klingsieck, Katrin and Kundisch, Dennis and Langendorf, Mike},
booktitle = {Proceedings of the 25th European Conference on Information Systems (ECIS)},
pages = {2970--2979},
title = {{Towards a Lean Approach for Gamifying Education}},
year = {2017},
}
@inproceedings{16338,
abstract = {To detect errors or find potential for improvement during the CAD-supported development of a complex technical system like modern industrial machines, the system’s virtual prototype can be examined in virtual reality (VR) in the context of virtual design reviews. Besides exploring the static shape of the examined system, observing the machines’ mechanics (e.g., motor-driven mechanisms) and transport routes for the material transport (e.g., via conveyor belts or chains, or rail-based transport systems) can play an equally important role in such a review. In practice it is often the case, that the relevant information about transport routes, or kinematic properties is either not consequently modeled in the CAD data or is lost during conversion processes. To significantly reduce the manual effort and costs for creating animations of the machines complex behavior with such limited input data for a design review, we present a set of algorithms to automatically determine geometrical properties of machine parts based only on their triangulated surfaces. The algorithms allow to detect the course of transport systems, the orientation of objects in 3d space, rotation axes of cylindrical objects and holes, the number of tooth of gears, as well as the tooth spacing of toothed racks. We implemented the algorithms in the VR system PADrend and applied them to animate virtual prototypes of real machines.},
author = {Brandt, Sascha and Fischer, Matthias and Gerges, Maria and Jähn, Claudius and Berssenbrügge, Jan},
booktitle = {Volume 1: 37th Computers and Information in Engineering Conference},
isbn = {9780791858110},
location = {Cleveland, USA},
pages = {91:1--91:10},
title = {{Automatic Derivation of Geometric Properties of Components From 3D Polygon Models}},
doi = {10.1115/detc2017-67528},
volume = {1},
year = {2017},
}
@phdthesis{19604,
author = {Li, Shouwei},
title = {{Parallel fixed parameter tractable problems}},
doi = {10.17619/UNIPB/1-252},
year = {2017},
}
@inproceedings{17653,
author = {Polevoy, Gleb and de Weerdt, M.M.},
booktitle = {Proceedings of the 29th Benelux Conference on Artificial Intelligence},
keyword = {interaction, reciprocation, contribute, shared effort, curbing, convergence, threshold, Nash equilibrium, social welfare, efficiency, price of anarchy, price of stability},
publisher = {Springer},
title = {{Reciprocation Effort Games}},
year = {2017},
}
@inproceedings{143,
abstract = {We present an efficient parallel algorithm for the general Monotone Circuit Value Problem (MCVP) with n gates and an underlying graph of bounded genus k. Our algorithm generalizes a recent result by Limaye et al. who showed that MCVP with toroidal embedding (genus 1) is in NC when the input contains a toroidal embedding of the circuit. In addition to extending this result from genus 1 to any bounded genus k, and unlike the work reported by Limaye et al., we do not require a precomputed embedding to be given. Most importantly, our results imply that given a P-complete problem, it is possible to find an algorithm that makes the problem fall into NC by fixing one or more parameters. Hence, we deduce the interesting analogy: Fixed Parameter Parallelizable (FPP) is with respect to P-complete what Fixed Parameter Tractable (FPT) is with respect to NP-complete. Similar work that uses treewidth as parameter was also presented by Elberfeld et al. in [6].},
author = {Abu-Khzam, Faisal N. and Li, Shouwei and Markarian, Christine and Meyer auf der Heide, Friedhelm and Podlipyan, Pavel},
booktitle = {Proceedings of the 22nd International Conference on Computing and Combinatorics (COCOON)},
pages = {92--102},
title = {{The Monotone Circuit Value Problem with Bounded Genus Is in NC}},
doi = {10.1007/978-3-319-42634-1_8},
year = {2016},
}
@inproceedings{16358,
author = {Li, Shouwei and Meyer auf der Heide, Friedhelm and Podlipyan, Pavel},
booktitle = {Algorithms for Sensor Systems, Proceedings of the 12th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS)},
publisher = {Springer},
title = {{The impact of the Gabriel subgraph of the visibility graph on the gathering of mobile autonomous robots}},
doi = {10.1007/978-3-319-53058-1_5 },
year = {2016},
}
@unpublished{16396,
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 < s$
no finite competitiveness is possible, our main result is an
$O(\frac{c}{\varepsilon} + \frac{1}{\varepsilon^3})$-competitive online
algorithm for $\beta = (1+\varepsilon)s$ with $\frac{1}{s} \leq \varepsilon
\leq 1$, where $s$ and $c$ denotes the largest setup time and the cost ratio of
the machine-types, respectively. It is complemented by a lower bound of
$\Omega(\frac{c}{\varepsilon})$.},
author = {Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören},
booktitle = {arXiv:1609.01184},
title = {{Cost-efficient Scheduling on Machines from the Cloud}},
year = {2016},
}
@inproceedings{20001,
author = {von Mammen, Sebastian and Hamann, Heiko and Heider, Michael},
booktitle = {ACM Symposium on Virtual Reality Software and Technology (VRST)},
isbn = {9781450344913},
title = {{Robot Gardens: An Augmented Reality Prototype for Plant-Robot Biohybrid Systems}},
doi = {10.1145/2993369.2993400},
year = {2016},
}
@inproceedings{16360,
abstract = {We consider the following variant of the two dimensional gathering problem for swarms of robots: Given a swarm of n indistinguishable, point shaped robots on a two dimensional grid. Initially, the robots form a closed chain on the grid and must keep this connectivity during the whole process of their gathering. Connectivity means, that neighboring robots of the chain need to be positioned at the same or neighboring points of the grid. In our model, gathering means to keep shortening the chain until the robots are located inside a 2*2 subgrid. Our model is completely local (no global control, no global coordinates, no compass, no global communication or vision, ...). Each robot can only see its next constant number of left and right neighbors on the chain. This fixed constant is called the viewing path length. All its operations and detections are restricted to this constant number of robots. Other robots, even if located at neighboring or the same grid point cannot be detected. Only based on the relative positions of its detectable chain neighbors, a robot can decide to obtain a certain state. Based on this state and their local knowledge, the robots do local modifications to the chain by moving to neighboring grid points without breaking the chain. These modifications are performed without the knowledge whether they lead to a global progress or not. We assume the fully synchronous FSYNC model. For this problem, we present a gathering algorithm which needs linear time. This result generalizes a result, where an open chain with specified distinguishable (and fixed) endpoints is considered. },
author = {Abshoff, Sebastian and Cord-Landwehr, Andreas and Fischer, Matthias and Jung, Daniel and Meyer auf der Heide, Friedhelm},
booktitle = {Proceedings of the 30th International Parallel and Distributed Processing Symposium (IPDPS)},
pages = {689--699},
publisher = {IEEE},
title = {{Gathering a Closed Chain of Robots on a Grid}},
doi = {10.1109/IPDPS.2016.51},
year = {2016},
}
@inproceedings{149,
abstract = {In this paper we consider a strategic variant of the online facility location problem. Given is a graph in which each node serves two roles: it is a strategic client stating requests as well as a potential location for a facility. In each time step one client states a request which induces private costs equal to the distance to the closest facility. Before serving, the clients may collectively decide to open new facilities, sharing the corresponding price. Instead of optimizing the global costs, each client acts selfishly. The prices of new facilities vary between nodes and also change over time, but are always bounded by some fixed value α. Both the requests as well as the facility prices are given by an online sequence and are not known in advance.We characterize the optimal strategies of the clients and analyze their overall performance in comparison to a centralized offline solution. If all players optimize their own competitiveness, the global performance of the system is O(√α⋅α) times worse than the offline optimum. A restriction to a natural subclass of strategies improves this result to O(α). We also show that for fixed facility costs, we can find strategies such that this bound further improves to O(√α).},
author = {Drees, Maximilian and Feldkord, Björn and Skopalik, Alexander},
booktitle = {Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)},
pages = {593----607},
title = {{Strategic Online Facility Location}},
doi = {10.1007/978-3-319-48749-6_43},
year = {2016},
}
@proceedings{163,
editor = {Dressler, Falko and Meyer auf der Heide, Friedhelm},
location = {Paderborn, Germany},
publisher = {ACM},
title = {{Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)}},
doi = {10.1145/2942358},
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},
}
@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{19961,
abstract = {The self-organizing bio-hybrid collaboration ofrobots and natural plants allows for a variety of interestingapplications. As an example we investigate how robots can beused to control the growth and motion of a natural plant, using LEDs to provide stimuli. We follow an evolutionaryrobotics approach where task performance is determined bymonitoring the plant's reaction. First, we do initial plantexperiments with simple, predetermined controllers. Then weuse image sampling data as a model of the dynamics ofthe plant tip xy position. Second, we use this approach toevolve robot controllers in simulation. The task is to makethe plant approach three predetermined, distinct points in anxy-plane. Finally, we test the evolved controllers in real plantexperiments and find that we cross the reality gap successfully. We shortly describe how we have extended from plant tipto many points on the plant, for a model of the plant stemdynamics. Future work will extend to two-axes image samplingfor a 3-d approach.},
author = {Wahby, Mostafa and Hofstadler, Daniel Nicolas and Heinrich, Mary Katherine and Zahadat, Payam and Hamann, Heiko},
booktitle = {Proc. of the 10th International Conference on Self-Adaptive and Self-Organizing Systems},
isbn = {9781509035342},
title = {{An Evolutionary Robotics Approach to the Control of Plant Growth and Motion: Modeling Plants and Crossing the Reality Gap}},
doi = {10.1109/saso.2016.8},
year = {2016},
}
@inproceedings{20002,
author = {Rybář, Milan and Hamann, Heiko},
booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2016)},
isbn = {9781450342063},
title = {{Inspiration-Triggered Search: Towards Higher Complexities by Mimicking Creative Processes}},
doi = {10.1145/2908812.2908815},
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},
keyword = {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},
}