Performance of the smallest-variance-first rule in appointment sequencing

Preprintprobability
Madelon A. de Kemp, Michel Mandjes, Neil Olver
Preprint (arXiv:18212.01467)

A classical problem in appointment scheduling, with applications in health care, concerns the determination of the patients’ arrival times that minimize a cost function that is a weighted sum of mean waiting times and mean idle times. Part of this problem is the sequencing problem, which focuses on ordering the patients. We assess the performance of the smallest-variance-first (SVF) rule, which sequences patients in order of increasing variance of their service
durations. While it was known that SVF is not always optimal, many papers have found that it performs well in practice and simulation. We give theoretical justification for these observations by proving quantitative worst-case bounds
on the ratio between the cost incurred by the SVF rule and the minimum attainable cost, in a number of settings. We also show that under quite general conditions, this ratio approaches 1 as the number of patients grows large, showing that the SVF rule is asymptotically optimal. While this viewpoint in terms of approximation ratio is a standard approach in many algorithmic
settings, our results appear to be the first of this type in the appointment scheduling literature.

Approximate Multi-Matroid Intersection via Iterative Refinement

approximationPreprint
André Linhares, Neil Olver, Chaitanya Swamy, Rico Zenklusen
Preprint (arXiv:1811.09027)

We introduce a new iterative rounding technique to round a point in a matroid polytope subject to further matroid constraints. This technique returns an independent set in one matroid with limited violations of the other ones. On top of the classical steps of iterative relaxation approaches, we iteratively refine/split involved matroid constraints to obtain a more restrictive constraint system, that is amenable to iterative relaxation techniques. Hence, throughout the iterations, we both tighten constraints and later relax them by dropping constrains under certain conditions. Due to the refinement step, we can deal with considerably more general constraint classes than existing iterative relaxation/rounding methods, which typically round on one matroid polytope with additional simple cardinality constraints that do not overlap too much.

We show how our rounding method, combined with an application of a matroid intersection algorithm, yields the first 2-approximation for finding a maximum-weight common independent set in 3 matroids. Moreover, our 2-approximation is LP-based, and settles the integrality gap for the natural relaxation of the problem. Prior to our work, no better upper bound than 3 was known for the integrality gap, which followed from the greedy algorithm. We also discuss various other applications of our techniques, including an extension that allows us to handle a mixture of matroid and knapsack constraints.

A Duality-based 2-approximation algorithm for maximum agreement forest

approximationPreprint
N. Olver, F. Schalekamp, S. van der Ster, L. Stougie and A. van Zuylen
Preprint (arXiv:1811.05916)