@article{63,
author = {Althaus, Ernst and Brinkmann, Andre and Kling, Peter and Meyer auf der Heide, Friedhelm and Nagel, Lars and Riechers, Sören and Sgall, Jiri and Suess, Tim},
journal = {Journal of Scheduling},
publisher = {Springer},
title = {{Scheduling Shared Continuous Resources on Many-Cores}},
doi = {10.1007/s10951-017-0518-0},
year = {2017},
}
@misc{695,
author = {Nowack, Joshua},
publisher = {Universität Paderborn},
title = {{On-The-Fly Konstruktion zusammenhängender Straßennetze aus gegebenen Einzelteilen}},
year = {2017},
}
@inproceedings{70,
author = {Feldkord, Björn and Markarian, Christine and Meyer auf der Heide, Friedhelm},
booktitle = {Proceedings of the 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA)},
pages = {17 -- 31},
title = {{Price Fluctuations in Online Leasing}},
doi = {10.1007/978-3-319-71147-8_2},
year = {2017},
}
@phdthesis{703,
author = {Podlipyan, Pavel},
publisher = {Universität Paderborn},
title = {{Local Algorithms for the Continuous Gathering Problem}},
year = {2017},
}
@inproceedings{82,
abstract = {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.},
author = {Abu-Khzam, Faisal N. and Li, Shouwei and Markarian, Christine and Meyer auf der Heide, Friedhelm and Podlipyan, Pavel},
booktitle = {Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW)},
pages = {139--150},
title = {{Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity}},
doi = {10.1007/978-3-319-59605-1_13},
year = {2017},
}
@article{110,
abstract = {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.},
author = {Antoniadis, Antonios and Kling, Peter and Ott, Sebastian and Riechers, Sören},
journal = {Theoretical Computer Science},
pages = {1--13},
publisher = {Elsevier},
title = {{Continuous Speed Scaling with Variability: A Simple and Direct Approach}},
doi = {10.1016/j.tcs.2017.03.021},
year = {2017},
}
@inproceedings{1094,
abstract = {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.},
author = {Feldotto, Matthias and John, Thomas and Kundisch, Dennis and Hemsen, Paul and Klingsieck, Katrin and Skopalik, Alexander},
booktitle = {Proceedings of the 12th International Conference on Design Science Research in Information Systems and Technology (DESRIST)},
pages = {462--467},
title = {{Making Gamification Easy for the Professor: Decoupling Game and Content with the StudyNow Mobile App}},
doi = {10.1007/978-3-319-59144-5_32},
year = {2017},
}
@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{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},
}
@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},
}
@inproceedings{16360,
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},
}
@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{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{16359,
author = {Cord-Landwehr, Andreas and Fischer, Matthias and Jung, Daniel and Meyer auf der Heide, Friedhelm},
booktitle = {Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
pages = {301--312},
publisher = {ACM},
title = {{Asymptotically Optimal Gathering on a Grid}},
doi = {10.1145/2935764.2935789},
year = {2016},
}
@unpublished{16450,
abstract = {In this paper, we solve the local gathering problem of a swarm of $n$
indistinguishable, point-shaped robots on a two dimensional grid in
asymptotically optimal time $\mathcal{O}(n)$ in the fully synchronous
$\mathcal{FSYNC}$ time model. Given an arbitrarily distributed (yet connected)
swarm of robots, the gathering problem on the grid is to locate all robots
within a $2\times 2$-sized area that is not known beforehand. Two robots are
connected if they are vertical or horizontal neighbors on the grid. The
locality constraint means that no global control, no compass, no global
communication and only local vision is available; hence, a robot can only see
its grid neighbors up to a constant $L_1$-distance, which also limits its
movements. A robot can move to one of its eight neighboring grid cells and if
two or more robots move to the same location they are \emph{merged} to be only
one robot. The locality constraint is the significant challenging issue here,
since robot movements must not harm the (only globally checkable) swarm
connectivity. For solving the gathering problem, we provide a synchronous
algorithm -- executed by every robot -- which ensures that robots merge without
breaking the swarm connectivity. In our model, robots can obtain a special
state, which marks such a robot to be performing specific connectivity
preserving movements in order to allow later merge operations of the swarm.
Compared to the grid, for gathering in the Euclidean plane for the same robot
and time model the best known upper bound is $\mathcal{O}(n^2)$.},
author = {Cord-Landwehr, Andreas and Fischer, Matthias and Jung, Daniel and Meyer auf der Heide, Friedhelm},
booktitle = {arXiv:1602.03303},
title = {{Asymptotically Optimal Gathering on a Grid}},
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},
}