MAPSP 2022 Accepted Papers

Georg von der Brüggen, Sergey Bozhko, Kuan-Hsun Chen, Jian-Jia Chen and Björn B. Brandenburg. Probabilistic Real-Time Scheduling
Elena Rener, Stefan Lendl, Ulrich Pferschy, Fabio Salassa and Vincent T'Kindt. Rescheduling with new orders under a maximum completion time disruption constraint
Freija van Lent, Julian Golak and Alexander Grigoriev. Allocation and pricing of planetarium seats
Moritz Buchem, Linda Kleist and Daniel Schmidt Genannt Waldschmidt. Scheduling with Machine Conflicts
Claire Hanen and Zdenek Hanzalek. Relations between Periodic Scheduling with Harmonic Periods and 2D Packing
Antonios Antoniadis, Matthias Englert, Nicolaos Matsakis and Pavel Veselý. Breaking the Barrier of 2 for the Competitiveness of Longest Queue Drop
Matej Lieskovský and Jiří Sgall. Graph burning and non-uniform $k$-centers for small treewidth
Pontus Ekberg and Sanjoy Baruah. Complexity of partitioned scheduling for periodic tasks
Sören Schmitt, Rob van Stee, Jiří Sgall, Matej Lieskovský and Martin Böhm. A Multi-Phase Algorithm for Bin Stretching with Stretching Factor below 1.5
Ben Hermans, Alessandro Agnetis, Mario Benini, Paolo Detti and Marco Pranzo. An approximation algorithm for sequencing unreliable jobs on parallel machines with job duplication
Martin Farach-Colton. Paging and the Address-Translation Problem
Woo-Hyung Cho, David Shmoys and Shane Henderson. SPT optimality via linear programming
Antonios Antoniadis, Ruben Hoeksma, Sandor Kisfaludi-Bak and Kevin Schewior. The High-Dimensional Cow-Path Problem
Jose Correa, Andrés Cristi, Laurent Feuilloley, Tim Oosterwijk and Alexandros Tsigonias-Dimitriadis. Independent Sampling for the Secretary Problem
Danny Blom, Rudi Pendavingh and Frits Spieksma. Filling a Theater During the COVID-19 Pandemic
Alexander Lindermayr and Nicole Megow. Non-Clairvoyant Scheduling with Predictions Revisited
Valentin Honoré, Bertrand Simon and Frédéric Suter. An Exact Algorithm for the Linear Tape Scheduling Problem
Daniel DeLayo, Kenny Zhang, Kunal Agrawal, Michael Bender, Jonathan Berry, Rathish Das, Ben Moseley and Cynthia Phillips. Automatic HBM Management: Models and Algorithms
Peter Gyorgyi, Tamas Kis, Tímea Tamási and József Békési. Joint replenishment meets scheduling
Gabrijela Obradovic, Ann-Brith Strömberg and Kristian Lundberg. Replacement and Repair of Common Components in Systems Subject to Operations Planning
Sebastian Berndt, Max Deppert, Klaus Jansen and Lars Rohwedder. Load Balancing: The Long Road from Theory to Practice
Britta Peis, Niklas Rieken, José Verschae and Andreas Wierz. A Primal-Dual and Primal-Greedy Approximation Framework for Weighted Covering Problems
Claire Hanen, Maher Mallem and Alix Munier Kordon. Parameterized Complexity of Single-machine Scheduling with Precedence, Release Dates and Deadlines
Vipin Ravindran Vijayalakshmi and Alexander Skopalik. Towards hardness of approximate pure equilibria
Emmanuel Hebrard, Christian Artigues, Pierre Lopez, Arnaud Lusson, Steve Chien, Adrien Maillard and Gregg Rabideau. Data transfer scheduling for deep space exploration
Evripidis Bampis, Konstantinos Dogeas, Alexander Kononov, Giorgio Lucarelli and Fanny Pascual. Speed Scaling with Explorable Uncertainty
Martin Durand and Fanny Pascual. Collective schedules: how to find a consensus schedule?
Michal Sinai and Tami Tamir. Minimizing Tardiness in a Scheduling Environment with Jobs' Dominance Hierarchy
Joanna Berlińska. Makespan minimization in tree data gathering networks with memory limits
Vít Koštejn and Jíří Sgall. Periodic scheduling with shared resources
Kunal Agrawal, Sanjoy Baruah, Alan Burns, Jeremy Fineman and Zhe Wang. Static schedules for fault-tolerant transmission
Marek Chrobak, Łukasz Jeż and Jiří Sgall. Randomized Item Collecting from Weight-Monotone Queues
Roel Lambers, Frits Spieksma, Viresh Patel, Jop Briët and Mehmet Yildiz. Orthogonal schedules in Round Robin competitions
Kunal Agrawal, Michael A. Bender, Rathish Das, William Kuszmaul, Enoch Peserico and Michele Scquizzato. Tight Bounds for Parallel Paging and Green Paging
Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak and Bertrand Simon. Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds
Moritz Buchem, Lars Rohwedder, Tjark Vredeveld and Andreas Wiese. Additive Approximation Schemes for Load Balancing Problems
Ya-Chun Liang, Kuan-Yun Lai, Ho-Lin Chen, Kazuo Iwama and Chung-Shou Liao. Tight Competitive Analyses of Online Car-sharing Problems
Franziska Eberle, Ruben Hoeksma, Nicole Megow, Lukas Nölke, Kevin Schewior and Bertrand Simon. Speed-Robust Scheduling: Sand, Bricks, and Rocks
Felix Höhne and Rob van Stee. Buffer minimization with conflicts on a line
Roel Brouwer, Marjan van den Akker and Han Hoogeveen. A hybrid local search algorithm for the Continuous Energy-Constrained Scheduling Problem
Neda Abbasi Shahkooh, Martin Böhm and Lukasz Jez. An alternative barely-random algorithm for Online Scheduling with Equal Job Sizes
Michael A. Bender, Samuel McCauley, Bertrand Simon, Shikha Singh and Frédéric Vivian. Resource Optimization for Program Committee Members: A Subreview Article
Eric Balkanski, Clifford Stein, Hao-Ting Wei and Tingting Ou. Scheduling with Speed Predictions
John Kuszmaul. Bamboo Trimming Revisited: Simple Algorithms Can Do Well Too
Martin Böhm, Ruben Hoeksma, Nicole Megow, Lukas Nölke and Bertrand Simon. On Hop-Constrained Steiner Trees in Tree-Like Metrics
Michele Barbato, Alberto Ceselli, Giovanni Righini and Antonio Belotti. Multi-Purpose Machine Scheduling: An Application to Smart Cosmetic Manufacturing
Sai Mali Ananthanarayanan, Charles Branas, Adam Elmachtoub, Clifford Stein and Yeqing Zhou. Queuing Safely for Elevator Systems amidst a Pandemic
Felix Höhne and Rob van Stee. On the bamboo garden trimming problem
Benjamin Moseley, Kirk Pruhs, Clifford Stein and Rudy Zhou. A Competitive Algorithm for Throughout Maximization on Identical Machines
Yulia Zakharova and Alexander Kononov. Scheduling Parallel Jobs in Two-processor Systems with Energy Constraint
Benjamín Rubio, José Baboun, Isabelle Beaundry, Mauricio Castro, Alejandro Jara and José Verschae. Methods for Planning the Search of Infected Nodes in Uncertain Graphs
Michael A. Bender and William Kuszmaul. Randomized Cup Game Algorithms Against Strong Adversaries
Sami Davies, Samir Khuller and Shirley Zhang. Balancing Flow Time and Energy Consumption
Alessandro Druetto and Andrea Grosso. Polynomial-Size ILP formulations for the Total Completion Time Problem on a Parallel Batching Machine
Olivier Ploton and T'Kindt Vincent. An Inclusion-Exclusion based algorithm for permutation flowshop scheduling with job precedences
Franziska Eberle, Alexander Lindermayr, Nicole Megow, Lukas Nölke and Jens Schlöter. Robustification of Online Graph Exploration Methods
Alexander Kononov and Marina Pakulich. On Flow Shop Scheduling with Job-Dependent Storage Requirements
Tom Demeulemeester, Dries Goossens, Ben Hermans and Roel Leus. On the selection probabilities of optimal solutions in binary linear programs
Nicola Morandi, Roel Leus and Hande Yaman. Arc-retraversing Solutions to the Traveling Salesman Problem with Drones
Bala Kalyanasundaram and Mahe Velauthapillai. Scheduling Messages towards Detecting Monochromatic Pattern on a Bounded Degree Network
Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley and Sergei Vassilvitskii. Faster Matchings via Learned Duals
Spyros Angelopoulos and Shahin Kamali. Contract Scheduling with Predictions
Federico Della Croce, Andrea Grosso and Vincent T'Kindt. Operating rooms scheduling with a shared resource: a red-blue knapsack modeling approach
Wouter Fokkema and Matthias Walter. The rectangle covering bound on the extension complexity of small cut polytopes
Alexander Souza, Raphael Haemmerli, Denys Trieskunov and Hsuan-Pin Wu. A parametric flow-based algorithm for crew diagramming: a pragmatic large-scale approach at the Swiss railways
Hsiang-Hsuan Liu and Jonathan Toole-Charignon. The Power of Amortized Recourse on Online Graph Problems
Bartłomiej Przybylski, Paweł Żuk and Krzysztof Rzadca. Data-driven scheduling in serverless computing to reduce response time
Maurizio Boccia, Andrea Mancuso, Adriano Masone and Claudio Sterle. The parallel AGV Scheduling Problem with Battery Constraints: exact and heuristic approaches
Julian Mestre, Sergey Pupyrev and Seeun William Umboh. On the Extended TSP Problem
Martijn van Ee. A 12/7-approximation algorithm for the discrete Bamboo Garden Trimming problem
Mauro Dell'Amico and Dario Bezzi. Solving a real-life assembly problem with lobster precedence and workforce constraint
Matej Lieskovský. Better Algorithms for Online Bin Stretching via Computer Search
Nikhil Bansal, Lars Rohwedder and Ola Svensson. Flow Time Scheduling and Prex Beck-Fiala
David Van Bulck and Dries Goossens. Using Benders' cuts to backtrack in sports timetabling
Julian Golak, Freija van Lent, Alexander Grigoriev and Tom Van der Zanden. The Periodic Lock Scheduling Problem
Thi Huyen Chau Nguyen, Werner Grass and Klaus Jansen. Exact Polynomial Time Algorithm for the Response Time Analysis of Harmonic Tasks
Guillaume Sagnol and Daniel Schmidt Genannt Waldschmidt. Restricted Adaptivity in Stochastic Scheduling
Shaul Rosner and Tami Tamir. Scheduling Games with Rank-Based Utilities
Vipin Ravindran Vijayalakshmi, Marc Schroder and Tami Tamir. Scheduling games with machine-dependent priority lists