TY - CONF
AU - Biermeier, Felix
AU - Feldkord, Björn
AU - Malatyali, Manuel
AU - Meyer auf der Heide, Friedhelm
ID - 16348
T2 - Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)
TI - A Communication-Efficient Distributed Data Structure for Top-k and k-Select Queries
ER -
TY - CONF
AU - Markarian, Christine
ID - 2851
T2 - International Conference on Operations Research (OR)
TI - Leasing with Uncertainty
ER -
TY - JOUR
AU - Althaus, Ernst
AU - Brinkmann, Andre
AU - Kling, Peter
AU - Meyer auf der Heide, Friedhelm
AU - Nagel, Lars
AU - Riechers, Sören
AU - Sgall, Jiri
AU - Suess, Tim
ID - 63
JF - Journal of Scheduling
TI - Scheduling Shared Continuous Resources on Many-Cores
ER -
TY - GEN
AU - Nowack, Joshua
ID - 695
TI - On-The-Fly Konstruktion zusammenhängender Straßennetze aus gegebenen Einzelteilen
ER -
TY - CONF
AU - Feldkord, Björn
AU - Markarian, Christine
AU - Meyer auf der Heide, Friedhelm
ID - 70
T2 - Proceedings of the 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA)
TI - Price Fluctuations in Online Leasing
ER -
TY - CONF
AB - Many graph problems such as maximum cut, chromatic number, hamiltonian cycle, and edge dominating set are known to be fixed-parameter tractable (FPT) when parameterized by the treewidth of the input graphs, but become W-hard with respect to the clique-width parameter. Recently, Gajarský et al. proposed a new parameter called modular-width using the notion of modular decomposition of graphs. They showed that the chromatic number problem and the partitioning into paths problem, and hence hamiltonian path and hamiltonian cycle, are FPT when parameterized by this parameter. In this paper, we study modular-width in parameterized parallel complexity and show that the weighted maximum clique problem and the maximum matching problem are fixed-parameter parallel-tractable (FPPT) when parameterized by this parameter.
AU - Abu-Khzam, Faisal N.
AU - Li, Shouwei
AU - Markarian, Christine
AU - Meyer auf der Heide, Friedhelm
AU - Podlipyan, Pavel
ID - 82
T2 - Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW)
TI - Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity
ER -
TY - BOOK
AU - Gausemeier, Jürgen
AU - Bodden, Eric
AU - Dressler, Falko
AU - Dumitrescu, Roman
AU - Meyer auf der Heide, Friedhelm
AU - Scheytt, Christoph
AU - Trächtler, Ansgar
ID - 16444
TI - Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)
ER -
TY - THES
AU - Podlipyan, Pavel
ID - 703
TI - Local Algorithms for the Continuous Gathering Problem
ER -
TY - JOUR
AB - We consider an extension of the dynamic speed scaling scheduling model introduced by Yao et al.: A set of jobs, each with a release time, deadline, and workload, has to be scheduled on a single, speed-scalable processor. Both the maximum allowed speed of the processor and the energy costs may vary continuously over time. The objective is to find a feasible schedule that minimizes the total energy costs. Theoretical algorithm design for speed scaling problems often tends to discretize problems, as our tools in the discrete realm are often better developed or understood. Using the above speed scaling variant with variable, continuous maximal processor speeds and energy prices as an example, we demonstrate that a more direct approach via tools from variational calculus can not only lead to a very concise and elegant formulation and analysis, but also avoids the “explosion of variables/constraints” that often comes with discretizing. Using well-known tools from calculus of variations, we derive combinatorial optimality characteristics for our continuous problem and provide a quite concise and simple correctness proof.
AU - Antoniadis, Antonios
AU - Kling, Peter
AU - Ott, Sebastian
AU - Riechers, Sören
ID - 110
JF - Theoretical Computer Science
TI - Continuous Speed Scaling with Variability: A Simple and Direct Approach
ER -
TY - CONF
AB - Many university students struggle with motivational problems, and gamification has the potential to address these problems. However, gamification is hardly used in education, because current approaches to gamification require instructors to engage in the time-consuming preparation of their course contents for use in quizzes, mini-games and the like. Drawing on research on limited attention and present bias, we propose a "lean" approach to gamification, which relies on gamifying learning activities (rather than learning contents) and increasing their salience. In this paper, we present the app StudyNow that implements such a lean gamification approach. With this app, we aim to enable more students and instructors to benefit from the advantages of gamification.
AU - Feldotto, Matthias
AU - John, Thomas
AU - Kundisch, Dennis
AU - Hemsen, Paul
AU - Klingsieck, Katrin
AU - Skopalik, Alexander
ID - 1094
T2 - Proceedings of the 12th International Conference on Design Science Research in Information Systems and Technology (DESRIST)
TI - Making Gamification Easy for the Professor: Decoupling Game and Content with the StudyNow Mobile App
ER -
TY - CONF
AU - Podlipyan, Pavel
AU - Li, Shouwei
AU - Markarian, Christine
AU - Meyer auf der Heide, Friedhelm
ID - 16349
T2 - Proceedings of the 13th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS)
TI - A Continuous Strategy for Collisionless Gathering
ER -
TY - THES
AU - Riechers, Sören
ID - 704
TI - Scheduling with Scarce Resources
ER -
TY - GEN
AB - 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.
AU - Fischer, Matthias
AU - Jung, Daniel
AU - Meyer auf der Heide, Friedhelm
ID - 17811
T2 - arXiv:1702.03400
TI - Gathering Anonymous, Oblivious Robots on a Grid
ER -
TY - CONF
AB - 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.
AU - John, Thomas
AU - Feldotto, Matthias
AU - Hemsen, Paul
AU - Klingsieck, Katrin
AU - Kundisch, Dennis
AU - Langendorf, Mike
ID - 1095
T2 - Proceedings of the 25th European Conference on Information Systems (ECIS)
TI - Towards a Lean Approach for Gamifying Education
ER -
TY - CONF
AB - 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.
AU - Brandt, Sascha
AU - Fischer, Matthias
AU - Gerges, Maria
AU - Jähn, Claudius
AU - Berssenbrügge, Jan
ID - 16338
SN - 9780791858110
T2 - Volume 1: 37th Computers and Information in Engineering Conference
TI - Automatic Derivation of Geometric Properties of Components From 3D Polygon Models
VL - 1
ER -
TY - CONF
AB - 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].
AU - Abu-Khzam, Faisal N.
AU - Li, Shouwei
AU - Markarian, Christine
AU - Meyer auf der Heide, Friedhelm
AU - Podlipyan, Pavel
ID - 143
T2 - Proceedings of the 22nd International Conference on Computing and Combinatorics (COCOON)
TI - The Monotone Circuit Value Problem with Bounded Genus Is in NC
ER -
TY - CONF
AU - Li, Shouwei
AU - Meyer auf der Heide, Friedhelm
AU - Podlipyan, Pavel
ID - 16358
T2 - Algorithms for Sensor Systems, Proceedings of the 12th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS)
TI - The impact of the Gabriel subgraph of the visibility graph on the gathering of mobile autonomous robots
ER -
TY - GEN
AB - 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})$.
AU - Mäcker, Alexander
AU - Malatyali, Manuel
AU - Meyer auf der Heide, Friedhelm
AU - Riechers, Sören
ID - 16396
T2 - arXiv:1609.01184
TI - Cost-efficient Scheduling on Machines from the Cloud
ER -
TY - CONF
AB - 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.
AU - Abshoff, Sebastian
AU - Cord-Landwehr, Andreas
AU - Fischer, Matthias
AU - Jung, Daniel
AU - Meyer auf der Heide, Friedhelm
ID - 16360
T2 - Proceedings of the 30th International Parallel and Distributed Processing Symposium (IPDPS)
TI - Gathering a Closed Chain of Robots on a Grid
ER -
TY - CONF
AB - 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(√α).
AU - Drees, Maximilian
AU - Feldkord, Björn
AU - Skopalik, Alexander
ID - 149
T2 - Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)
TI - Strategic Online Facility Location
ER -