6 citations · 11 across the 20 of their papers we have counts for
24 papers · 1 filter
Combinatorial Perpetual Scheduling: Existence and Computation of Low-Height Schedules
Mirabel Mendoza-Cadena, Arturo Merino, Mads Anker Nielsen +1
This paper considers a framework for combinatorial variants of perpetual-scheduling problems. Given an independence system , a schedule consists of an independent…
Forwarding Packets Greedily on the Line
Joan Boyar, Lene M. Favrholdt, Kim S. Larsen +2
We consider the problem of forwarding packets arriving online with their destinations in a line network. In each time step, each router can forward one packet along the edge to its…
Approximating Matroid Basis Testing for Partition Matroids using Budget-In-Expectation
Lisa Hellerstein, Benedikt M. Plank, Kevin Schewior
We consider the following Stochastic Boolean Function Evaluation problem, which is closely related to several problems from the literature. A matroid (in compact repr…
Non-Adaptive Evaluation of -of- Functions: Tight Gap and a Unit-Cost PTAS
Mads Anker Nielsen, Lars Rohwedder, Kevin Schewior
We consider the Stochastic Boolean Function Evaluation (SBFE) problem in the well-studied case of -of- functions: There are independent Boolean random variables $x_1,\dots,x_…
Stochastic scheduling with Bernoulli-type jobs through policy stratification
Antonios Antoniadis, Ruben Hoeksma, Kevin Schewior +1
This paper addresses the problem of computing a scheduling policy that minimizes the total expected completion time of a set of jobs with stochastic processing times on par…
Scheduling on a Stochastic Number of Machines
Moritz Buchem, Franziska Eberle, Hugo Kooki Kasuya Rosado +2
We consider a new scheduling problem on parallel identical machines in which the number of machines is initially not known, but it follows a given probability distribution. Only af…
Quickly Determining Who Won an Election
Lisa Hellerstein, Naifeng Liu, Kevin Schewior
This paper considers elections in which voters choose one candidate each, independently according to known probability distributions. A candidate receiving a strict majority (absol…
Clustering Graphs of Bounded Treewidth to Minimize the Sum of Radius-Dependent Costs
Lukas Drexler, Jan Höckendorff, Joshua Könen +1
We consider the following natural problem that generalizes min-sum-radii clustering: Given is as well as some metric space where for facilities…
Trading Prophets
José Correa, Andrés Cristi, Paul Dütting +3
In this work we initiate the study of buy-and-sell prophet inequalities. We start by considering what is arguably the most fundamental setting. In this setting the online algorithm…
Incremental Maximization via Continuization
Yann Disser, Max Klimm, Kevin Schewior +1
We consider the problem of finding an incremental solution to a cardinality-constrained maximization problem that not only captures the solution for a fixed cardinality, but also d…
Improved Approximation Algorithms for the Expanding Search Problem
Svenja M. Griesbach, Felix Hommelsheim, Max Klimm +1
A searcher is tasked with exploring a graph with edge lengths and vertex weights, starting from a designated vertex. Initially, only the starting vertex is considered explored. At…
Simple Algorithms for Stochastic Score Classification with Small Approximation Ratios
Benedikt M. Plank, Kevin Schewior
We revisit the Stochastic Score Classification (SSC) problem introduced by Gkenosis et al. (ESA 2018): We are given tests. Each test can be conducted at cost , and it…
Knapsack Secretary Through Boosting
Andreas Abels, Leon Ladewig, Kevin Schewior +1
We revisit the knapsack-secretary problem (Babaioff et al.; APPROX 2007), a generalization of the classic secretary problem in which items have different sizes and multiple items m…
A Stronger Impossibility for Fully Online Matching
Alexander Eckl, Anja Kirschbaum, Marilena Leichter +1
We revisit the fully online matching model (Huang et al., J.\ ACM, 2020), an extension of the classic online matching model due to Karp, Vazirani, and Vazirani (STOC 1990), which h…
Speed-Robust Scheduling -- Sand, Bricks, and Rocks
Franziska Eberle, Ruben Hoeksma, Nicole Megow +3
The speed-robust scheduling problem is a two-stage problem where given machines, jobs must be grouped into at most bags while the processing speeds of the given machine…
Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility
José Correa, Paul Dütting, Felix Fischer +2
A prophet inequality states, for some , that the expected value achievable by a gambler who sequentially observes random variables and selects one of the…
An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
Chien-Chung Huang, Mathieu Mari, Claire Mathieu +2
We devise a constant-factor approximation algorithm for the maximization version of the edge-disjoint paths problem if the supply graph together with the demand edges form a planar…
Online Throughput Maximization on Unrelated Machines: Commitment is No Burden
Franziska Eberle, Nicole Megow, Kevin Schewior
We consider a fundamental online scheduling problem in which jobs with processing times and deadlines arrive online over time at their release dates. The task is to determine a fea…
Online Multistage Subset Maximization Problems
Evripidis Bampis, Bruno Escoffier, Kevin Schewior +1
Numerous combinatorial optimization problems (knapsack, maximum-weight matching, etc.) can be expressed as \emph{subset maximization problems}: One is given a ground set $N=\{1,\do…
A general framework for handling commitment in online throughput maximization
Lin Chen, Franziska Eberle, Nicole Megow +2
We study a fundamental online job admission problem where jobs with deadlines arrive online over time at their release dates, and the task is to determine a preemptive single-serve…
Prophet Inequalities for I.I.D. Random Variables from an Unknown Distribution
José R. Correa, Paul Dütting, Felix Fischer +1
A central object in optimal stopping theory is the single-choice prophet inequality for independent, identically distributed random variables: Given a sequence of random variables…
A PTAS for Euclidean TSP with Hyperplane Neighborhoods
Antonios Antoniadis, Krzysztof Fleszar, Ruben Hoeksma +1
In the Traveling Salesperson Problem with Neighborhoods (TSPN), we are given a collection of geometric regions in some space. The goal is to output a tour of minimum length that vi…
An O(m^2 log m)-Competitive Algorithm for Online Machine Minimization
Lin Chen, Nicole Megow, Kevin Schewior
We consider the online machine minimization problem in which jobs with hard deadlines arrive online over time at their release dates. The task is to determine a feasible schedule o…
New Results on Online Resource Minimization
Lin Chen, Nicole Megow, Kevin Schewior
We consider the online resource minimization problem in which jobs with hard deadlines arrive online over time at their release dates. The task is to determine a feasible schedule…