MAPSP 2013 Accepted Papers

Minming Li. DVS scheduling algorithms for various models of processors: progress and open problems
Márton Drótos, Péter Györgyi and Tamas Kis. Approximation algorithms for machine scheduling with non-renewable resources
Alexander Souza and Matthias Hellwig. Approximation Algorithms for Generalized and Variable-Sized Bin Covering
Elisabeth Günther, Olaf Maurer, Nicole Megow and Andreas Wiese. A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio
Nicole Megow and José Verschae. Dual techniques for scheduling on a machine with varying speed
Marek Cygan, Fabrizio Grandoni and Monaldo Mastrolilli. How to Sell Hyperedges: The Hypermatching Assignment Problem
Mihai Burcea, Prudence W.H. Wong and Fencol C.C. Yung. Improved Results on Online Dynamic Bin Packing
Hongyang Sun and Rui Fan. Improved Semi-Online Makespan Scheduling with a Reordering Buffer
Tim Nonner and Maxim Sviridenko. An Efficient Polynomial-Time Approximation Scheme for the Joint Replenishment Problem
Sungjin Im, Benjamin Moseley and Kirk Pruhs. The Secret of Potential Functions: Breaking the Magician's Oath?
Frans Schalekamp, Rene Sitters, Suzanne van der Ster, Leen Stougie, Victor Verdugo and Anke van Zuylen. Split scheduling with uniform setup times
József Békési, Gábor Galambos, Michael Jung, Marcus Oswald and Gerhard Reinelt. Exact Algorithms for the General Coupled Task Scheduling Problem
Alberto Marchetti-Spaccamela, Cyriel Rutten, Suzanne van der Ster and Andreas Wiese. Assigning Sporadic Tasks to Unrelated Machines
Ehab Morsy. Approximating the k-Splittable Capacitated Network Design Problem
Roman Čapek, Lucie Bužková and Zdeněk Hanzálek. Constraint Programming and Evaluation Methods for Scheduling with Alternative Process Plans
Wim Vancroonenburg, Federico Della Croce, Dries Goossens and Frits Spieksma. The Red-Blue Transportation Problem
Ilya Chernykh and Sergey Sevastyanov. On the power of preemption in open shops
Tulia Herrera and Cliff Stein. Online scheduling for energy minimization with a constrained adversary
Alexander Kononov. Improved approximation algorithms for two routing open shop problems
Peter Kling and Peter Pietrzyk. Scheduling Profitably on Multiple Processors
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Łukasz Jeż, Jiří Sgall and Grzegorz Stachowiak. Online Control Message Aggregation in Chain Networks
Leah Epstein, Łukasz Jeż, Jiří Sgall and Rob van Stee. Online interval scheduling on uniformly related machines
Robert Davis and Marko Bertogna. Optimal FP Scheduling with Deferred Pre-emption
Rodrigo Carrasco, Garud Iyengar and Clifford Stein. Single Machine Scheduling with Job-Dependent Convex Cost and Arbitrary Precedence Constraints
Eyjólfur Ingi Ásgeirsson, Magnus M. Halldorsson, Pradipta Mitra, Joseph Foley, Helga Gudmundsdottir, Sveinn Fannar Kristjansson, Sindri Magnusson, Henning Ulfarsson and Ymir Vigfusson. Distributed Scheduling for Data Aggregation in Wireless Networks
György Dósa and Jiří Sgall. First Fit bin packing: A tight analysis
Bala Kalyanasundaram and Mahe Velauthapillai. Establishing A Periodic Transmission Schedule in Wireless Sensor Network for Non-Uniform Transmission Case
T'Kindt Vincent, Christophe Lenté and Mathieu Liedloff. A Study of worst-case complexity for parallel machine scheduling problems based on an extension of the Sort  & Search method
Abdoul Bitar, Stéphane Dauzère-Pérès and Claude Yugma. A genetic algorithm for a parallel machine scheduling problem with auxiliary resources and sequence dependent setup times
Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, Sebastian Stiller and Andreas Wiese. Deadline Scheduling of Jobs and Tasks in the Sporadic DAG Model
José R. Correa, Víctor Verdugo and José Verschae. Approximation algorithms for scheduling split jobs with setup times
Mordechai Shalom, Prudence W.H. Wong and Shmuel Zaks. Interval Scheduling to Maximize Bandwidth Provision
Trivikram Dokka, Yves Crama and Frits Spieksma. Approximation Algorithms for Multi-Dimensional Vector Assignment Problems
Benjamin Moseley, Kirk Pruhs and Clifford Stein. The Complexity of Scheduling for p-norms of Flow and Stretch
Leah Epstein, Asaf Levin and Gerhard J. Woeginger. Vertex cover meets multiprocessor scheduling
Leah Epstein, Asaf Levin and Rob van Stee. Unified approach to truthful scheduling on related machines
Stefan Kreter and Jürgen Zimmermann. Mixed-integer linear programming formulations for the RCPSP/max with calendars
Antonios Antoniadis, Chien-Chung Huang, Sebastian Ott and Jose Verschae. Profitable Scheduling with Energy Costs
Ammar Oulamara, Djamal Rebaine and Mehdi Serairi. Open shop scheduling problem with time-dependent resource consumption
Fidaa Abed and Chien-Chung Huang. Preemptive coordination mechanisms for unrelated machines
Giampaolo Ferraro and Julian Mestre. A Tight Analysis of the Longest Wait First Heuristic for Online Broadcast Scheduling
Morten Tiedemann and Stephan Westphal. An LP-Based Heuristic for the Flexible Job Shop Scheduling Problem
Agnès Le Roux, Odile Bellenguez-Morineau and Christelle Guéret. Valid inequalities and dominance rules for speed-dating scheduling linear models
Martijn van Brink, Alexander Grigoriev and Tjark Vredeveld. Express Delivery Problem
Quang-Chieu Ta, Jean-Charles Billaut and Jean-Louis Bouquard. Recovering beam search and Matheuristic algorithms for the F2||sum T_j scheduling problem
Jiří Sgall and Gerhard J. Woeginger. Multiprocessor jobs, preemptive schedules, and one-competitive online algorithms
Ruben Hoeksma and Marc Uetz. Two-Dimensional Optimal Mechanism Design for a Single Machine Scheduling Problem
Vitaly Strusevich and Hans Kellerer. Approximation Schemes for Convex Positive Half-Product and Its Scheduling Applications
Murat Firat, Dirk Briskorn, Stanislas Francfort and Alexandre Laugier. A two-level optical FTTH network design problem
Philippe Baptiste and Nicolas Bonifas. Generating redundant cumulative constraints to compute preemptive bounds
Aysegul Altindag and Ceyda Oguz. Variable Neighborhood Search for Order Acceptance Scheduling Problem
Safia Kedad-Sidhoum, Florence Monna, Gregory Mounie and Denis Trystram. Approximation Algorithms for a Scheduling Problem on Multi-Cores with GPUs
Jude-Thaddeus Ojiaku, Daniel Thomas and Prudence W.H. Wong. Energy-Efficient Flow Time Scheduling: An Experimental Study
Anis Kooli and Mehdi Serairi. An assignment based lower bound for the single machine with unequal release dates
Antonios Antoniadis and Chien-Chung Huang. Non-Preemptive Speed Scaling
Alexandra French, Zhishan Guo and Sanjoy Baruah. Scheduling mixed-criticality workloads upon unreliable processors
Liliana Grigoriu. Multiprocessor scheduling with fixed jobs or downtimes
Jasper de Jong, Marc Uetz and Andreas Wombacher. The (Sequential) Price of Anarchy for Throughput Scheduling
Eric Angel, Evripidis Bampis, Vincent Chau and Dimitrios Letsios. Throughput Maximization for Speed-Scaling with Agreeable Deadlines
Evripidis Bampis, Alexander Kononov, Dimitrios Letsios, Giorgio Lucarelli and Maxim Sviridenko. Energy Efficient Multiprocessor Scheduling via Configuration LP
Janardhan Kulkarni, Kamesh Munagala, Sungjin Im and Sayan Bhattacharya. Coordination Mechanisms from (almost) all Scheduling Policies
David Bunde, Michael Bender, Cynthia Phillips, Vitus Leung and Samuel Mccauley. Efficient Scheduling to Minimize Calibrations
Stefano Leonardi, Nicole Megow, Roman Rischke, Leen Stougie, Chaitanya Swamy and José Verschae. Scheduling with time-varying cost: deterministic and stochastic models
Zdenek Hanzalek and Tomas Tunys. On Non-Preemptive Mixed-Criticality Scheduling
Yakov Zinder, Samuel Walker and Claire Hanen. The Worst-Case Performance of One Class of Scheduling Algorithms for Flexible Multiprocessor Tasks
Peter Brucker and Natalia Shakhlevich. On General Methodology for Solving Inverse Scheduling Problems
Ruben van der Zwaan, Nikhil Bansal, Suzanne van der Ster, Cyriel Rutten and Tjark Vredeveld. Approximating real-time scheduling on identical machines
Ruben van der Zwaan, Sungjin Im and Viswanath Nagarajan. Minimum Latency Submodular Cover
Dorin Maxim, Liliana Cucu-Grosjean, Olivier Buffet, Luca Santinelli and Robert Davis. Optimal Priority Assignment Algorithms for Probabilistic Real-Time Systems
Deeparnab Chakrabarty and Sanjeev Khanna. A Special Case of Restricted Assignment Makespan Minimization
Sponsored by apixxo
Planning and Scheduling Solutions
Sponsored by apixxo
- Planning and Scheduling Solutions