TY - CONF AU - Pukrop, Simon AU - Mäcker, Alexander AU - Meyer auf der Heide, Friedhelm ID - 13868 T2 - Proceedings of the 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM) TI - Approximating Weighted Completion Time for Order Scheduling with Setup Times ER - TY - CONF AU - Jansen, Klaus AU - Maack, Marten AU - Mäcker, Alexander ID - 8866 T2 - Proceedings of the 33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS) TI - Scheduling on (Un-)Related Machines with Setup Times ER - TY - THES AU - Mäcker, Alexander ID - 14851 TI - On Scheduling with Setup Times ER - TY - JOUR AU - König, Jürgen AU - Mäcker, Alexander AU - Meyer auf der Heide, Friedhelm AU - Riechers, Sören ID - 3551 IS - 4 JF - Journal of Combinatorial Optimization TI - Scheduling with interjob communication on parallel processors VL - 36 ER - TY - CONF AB - Consider a problem in which $n$ jobs that are classified into $k$ types arrive over time at their release times and are to be scheduled on a single machine so as to minimize the maximum flow time.The machine requires a setup taking $s$ time units whenever it switches from processing jobs of one type to jobs of a different type.We consider the problem as an online problem where each job is only known to the scheduler as soon as it arrives and where the processing time of a job only becomes known upon its completion (non-clairvoyance).We are interested in the potential of simple ``greedy-like'' algorithms.We analyze a modification of the FIFO strategy and show its competitiveness to be $\Theta(\sqrt{n})$, which is optimal for the considered class of algorithms.For $k=2$ types it achieves a constant competitiveness.Our main insight is obtained by an analysis of the smoothed competitiveness.If processing times $p_j$ are independently perturbed to $\hat p_j = (1+X_j)p_j$, we obtain a competitiveness of $O(\sigma^{-2} \log^2 n)$ when $X_j$ is drawn from a uniform or a (truncated) normal distribution with standard deviation $\sigma$.The result proves that bad instances are fragile and ``practically'' one might expect a much better performance than given by the $\Omega(\sqrt{n})$-bound. AU - Mäcker, Alexander AU - Malatyali, Manuel AU - Meyer auf der Heide, Friedhelm AU - Riechers, Sören ID - 79 T2 - Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA) TI - Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times VL - 10787 ER - TY - CONF AB - We consider a scheduling problem on $m$ identical processors sharing an arbitrarily divisible resource. In addition to assigning jobs to processors, the scheduler must distribute the resource among the processors (e.g., for three processors in shares of 20\%, 15\%, and 65\%) and adjust this distribution over time. Each job $j$ comes with a size $p_j \in \mathbb{R}$ and a resource requirement $r_j > 0$. Jobs do not benefit when receiving a share larger than $r_j$ of the resource. But providing them with a fraction of the resource requirement causes a linear decrease in the processing efficiency. We seek a (non-preemptive) job and resource assignment minimizing the makespan.Our main result is an efficient approximation algorithm which achieves an approximation ratio of $2 + 1/(m-2)$. It can be improved to an (asymptotic) ratio of $1 + 1/(m-1)$ if all jobs have unit size. Our algorithms also imply new results for a well-known bin packing problem with splittable items and a restricted number of allowed item parts per bin.Based upon the above solution, we also derive an approximation algorithm with similar guarantees for a setting in which we introduce so-called tasks each containing several jobs and where we are interested in the average completion time of tasks (a task is completed when all its jobs are completed). AU - Kling, Peter AU - Mäcker, Alexander AU - Riechers, Sören AU - Skopalik, Alexander ID - 59 T2 - Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) TI - Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource ER - TY - JOUR AU - Mäcker, Alexander AU - Malatyali, Manuel AU - Meyer auf der Heide, Friedhelm AU - Riechers, Sören ID - 706 IS - 4 JF - Journal of Combinatorial Optimization TI - Cost-efficient Scheduling on Machines from the Cloud VL - 36 ER - TY - CHAP AU - Bemmann, Pascal AU - Biermeier, Felix AU - Bürmann, Jan AU - Kemper, Arne AU - Knollmann, Till AU - Knorr, Steffen AU - Kothe, Nils AU - Mäcker, Alexander AU - Malatyali, Manuel AU - Meyer auf der Heide, Friedhelm AU - Riechers, Sören AU - Schaefer, Johannes Sebastian AU - Sundermeier, Jannik ID - 16461 SN - 0302-9743 T2 - Structural Information and Communication Complexity TI - Monitoring of Domain-Related Problems in Distributed Data Streams ER - TY - CONF 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 series = {LNCS} AU - Mäcker, Alexander AU - Malatyali, Manuel AU - Meyer auf der Heide, Friedhelm AU - Riechers, Sören ID - 207 T2 - Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA) TI - Cost-efficient Scheduling on Machines from the Cloud ER - TY - CONF AB - Consider a scheduling problem in which a set of jobs with interjob communication, canonically represented by a weighted tree, needs to be scheduled on m parallel processors interconnected by a shared communication channel. In each time step, we may allow any processed job to use a certain capacity of the channel in order to satisfy (parts of) its communication demands to adjacent jobs processed in parallel. The goal is to find a schedule that minimizes the makespan and in which communication demands of all jobs are satisfied.We show that this problem is NP-hard in the strong sense even if the number of processors and the maximum degree of the underlying tree is constant.Consequently, we design and analyze simple approximation algorithms with asymptotic approximation ratio 2-2/m in case of paths and a ratio of 5/2 in case of arbitrary trees. AU - König, Jürgen AU - Mäcker, Alexander AU - Meyer auf der Heide, Friedhelm AU - Riechers, Sören ID - 157 T2 - Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA) TI - Scheduling with Interjob Communication on Parallel Processors 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 - Consider the problem in which n jobs that are classified into k types are to be scheduled on m identical machines without preemption. A machine requires a proper setup taking s time units before processing jobs of a given type. The objective is to minimize the makespan of the resulting schedule. We design and analyze an approximation algorithm that runs in time polynomial in n,m and k and computes a solution with an approximation factor that can be made arbitrarily close to 3/2. AU - Mäcker, Alexander AU - Malatyali, Manuel AU - Meyer auf der Heide, Friedhelm AU - Riechers, Sören ED - Dehne, Frank ED - Sack, Jörg Rüdiger ED - Stege, Ulrike ID - 274 T2 - Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings TI - Non-preemptive Scheduling on Machines with Setup Times ER - TY - CONF AB - 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. AU - Li, Shouwei AU - Mäcker, Alexander AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm AU - Riechers, Sören ID - 240 T2 - Proceedings of the 21st Annual International Computing and Combinatorics Conference (COCOON) TI - Towards Flexible Demands in Online Leasing Problems ER - TY - CONF AB - Online social networks are attracting billions of nowadays, both on a global scale as well as in social enterprise networks. Using distributed hash tables and peer-to-peer technology allows online social networks to be operated securely and efficiently only by using the resources of the user devices, thus alleviating censorship or data misuse by a single network operator. In this paper, we address the challenges that arise in implementing reliably and conveniently to use distributed data structures, such as lists or sets, in such a distributed hash-tablebased online social network. We present a secure, distributed list data structure that manages the list entries in several buckets in the distributed hash table. The list entries are authenticated, integrity is maintained and access control for single users and also groups is integrated. The approach for secure distributed lists is also applied for prefix trees and sets, and implemented and evaluated in a peer-to-peer framework for social networks. Evaluation shows that the distributed data structure is convenient and efficient to use and that the requirements on security hold. AU - Janiuk, Jens AU - Mäcker, Alexander AU - Graffi, Kalman ID - 367 T2 - Proceedings of the International Conference on Collaboration Technologies and Systems (CTS) TI - Secure Distributed Data Structures for Peer-to-Peer-based Social Networks ER - TY - CONF AB - Network creation games model the creation and usage costs of networks formed by n selfish nodes. Each node v can buy a set of edges, each for a fixed price α > 0. Its goal is to minimize its private costs, i.e., the sum (SUM-game, Fabrikant et al., PODC 2003) or maximum (MAX-game, Demaine et al., PODC 2007) of distances from v to all other nodes plus the prices of the bought edges. The above papers show the existence of Nash equilibria as well as upper and lower bounds for the prices of anarchy and stability. In several subsequent papers, these bounds were improved for a wide range of prices α. In this paper, we extend these models by incorporating quality-of-service aspects: Each edge cannot only be bought at a fixed quality (edge length one) for a fixed price α. Instead, we assume that quality levels (i.e., edge lengths) are varying in a fixed interval [βˇ,β^] , 0 series = {LNCS} AU - Cord-Landwehr, Andreas AU - Mäcker, Alexander AU - Meyer auf der Heide, Friedhelm ID - 380 T2 - Proceedings of the 10th International Conference on Web and Internet Economics (WINE) TI - Quality of Service in Network Creation Games ER - TY - GEN AU - Mäcker, Alexander ID - 526 TI - Greedy Network Creation With Heavy And Light Edges ER -