Second Lightning Session

Second Lightning Session (14:00 - 14:30)

  • Towards a Better Understanding of the Running Time of Local Search Heuristics

    Speaker: Jesse van Rhijn (University of Twente)

    Abstract: Local search is a powerful paradigm for solving combinatorial optimization problems when exact methods are not effective. In this setting, an initial solution is iteratively improved by some efficient operation until no more improvements are possible. These heuristics often have poor worst-case running time, but much better performance in average-case settings. However, even the best average-case analyses of local search heuristics typically display a gap with their running times in experiments. In this talk, I will briefly propose a possible direction into which further improvements to known average-case running times may be found.

  • Accelerating Matroid Optimization through Fast Imprecise Oracles

    Speaker: Jens Schlöter (CWI Amsterdam)

    Abstract: Querying complex models for precise information (e.g. traffic models, database systems, large ML models) often entails intense computations and results in long response times. Thus, weaker models that give imprecise results quickly can be advantageous, provided inaccuracies can be resolved using few queries to a stronger model. In the fundamental problem of computing a maximum-weight basis of a matroid, a well-known generalization of many combinatorial optimization problems, algorithms have access to a clean oracle to query matroid information. We additionally equip algorithms with a fast but dirty oracle. We design and analyze practical algorithms that only use few clean queries w.r.t. the quality of the dirty oracle, while maintaining robustness against arbitrarily poor dirty oracles, approaching the performance of classic algorithms for the given problem. Notably, we prove that our algorithms are, in many respects, best-possible. The talk is based on a joint work with Franziska Eberle, Felix Hommelsheim, Alexander Lindermayr, Nicole Megow, and Zhenwei Liu.

  • Computing Balanced Solutions for International Kidney Exchange Schemes

    Speaker: Daniel Paulusma (Durham University)

    Abstract: In kidney exchange programmes (KEP) patients may swap their incompatible donors leading to cycles of kidney transplants. Nowadays, countries try to merge their national patient-donor pools to international KEPs (IKEPs). Long-term stability of an IKEP can be achieved through a credit-based system. In each round, every country is prescribed a ``fair'' initial allocation of kidney transplants. The initial allocation, which is obtained by using solution concepts from cooperative game theory, is adjusted by incorporating credits from the previous round, yielding the target allocation. The goal is to find, in each round, an optimal solution that closely approximates the target allocation. We give a brief survey of current results and explain the main computational challenges.

  • Assignment Mechanisms with Predictions in the Private Graph Model

    Speaker: Artem Tsikiridis (CWI Amsterdam)

    Abstract: The realm of algorithms with predictions has led to the development of several new algorithms that leverage (potentially erroneous) predictions to enhance their performance guarantees. The challenge is to devise algorithms that achieve optimal approximation guarantees as the prediction quality varies from perfect (consistency) to imperfect (robustness). This framework is particularly appealing in mechanism design contexts, where predictions might convey private information about the agents. In this paper, we design strategyproof mechanisms that leverage predictions to achieve improved approximation guarantees for several variants of the Generalized Assignment Problem (GAP) in the private graph model. In this model, first introduced by Dughmi & Ghosh (2010), the set of resources that an agent is compatible with is private information. For the Bipartite Matching Problem (BMP), we give a deterministic group-strategyproof (GSP) mechanism that is (1+1/γ)-consistent and (1+γ)-robust, where γ≥1 is some confidence parameter. We also prove that this is best possible. Remarkably, our mechanism draws inspiration from the renowned Gale-Shapley algorithm, incorporating predictions as a crucial element. Additionally, we give a randomized mechanism that is universally GSP and improves on the guarantees in expectation. The other GAP variants that we consider all make use of a unified greedy mechanism that adds edges to the assignment according to a specific order. Our universally GSP mechanism randomizes over the greedy mechanism, our mechanism for BMP and the predicted assignment, leading to (1+3/γ)-consistency and (3+γ)-robustness in expectation. All our mechanisms also provide more fine-grained approximation guarantees that interpolate between the consistency and the robustness, depending on some natural error measure of the prediction.

    Joint work with Riccardo Colini-Baldeschi (Meta), Sophie Klumper (CWI & University of Amsterdam) and Guido Schaefer (CWI & University of Amsterdam).

    The paper is available here: https://arxiv.org/abs/2403.03725

  • Safe and Effective Use of Optimistic Period Predictions in Real-Time Scheduling

    Speaker: Leen Stougie (CWI Amsterdam / VU Amsterdam)

    Abstract: A real-time scheduling system has tasks emitting recurring jobs over time with relative deadlines and the question is if all jobs can be scheduled on a single machine such as to meet their deadlines. In the system we consider each task τi is characterized by a triple (Ci, Ti, Pi), with Ci the processing time of each job emitted by the task, Ti is the minimum amount of time that must elapse between the release times of two consecutive jobs of task τi, which is equal to the relative deadline of these jobs (a so-called implicit deadline system). New here is the parameter Pi, a prediction on the time that elapses between two consecutive job releases, which is usually much more optimistic than Ti.

    We design a pseudo-polynomial time algorithm that computes approximately the minimum speed of the machine that guarantees no deadline miss when the system is consistent with the predictions and that is sufficient to have no deadline miss upon non-consistent behavior by turning the machine on full speed (say speed 1).

    This is joint work with Sanjoy Baruah, Pontius Ekberg, Alexander Lindermayr, Alberto Marchetti-Spaccamela, and Nicole Megow.

  • The Secretary Problem with Independent Sampling

    Speaker: Tim Oosterwijk (VU Amsterdam)

    Abstract: The secretary problem is probably the most well-studied optimal stopping problem with many applications in economics and management. In the secretary problem, a decision maker faces an unknown sequence of values, revealed successively, and has to make irrevocable take-it-or-leave-it decisions. Her goal is to select the maximum value in the sequence. Although in the classic secretary problem the values of upcoming elements are entirely unknown, in many realistic situations, the decision maker has access to some information, for example, from past data. In this talk, we take a sampling approach and assume that before starting the sequence, each element is sampled independently with probability p. We study both the adversarial and the random arrival models. Our main result is to obtain the best possible algorithms for both settings and all values of p. As p grows to one, the obtained guarantees converge to the optimal guarantees in the full information case. Notably, we establish that the best possible algorithm in the adversarial order setting is a fixed threshold algorithm. In the random order setting, we characterize the best possible algorithm by a sequence of thresholds, dictating at which point in time we should accept a value. Surprisingly, this sequence is independent of p. We complement our theoretical results with numerical experiments on data of people playing the secretary problem repeatedly. Our results help explain some behavioral issues they raised and indicate that people play a strategy similar to our optimal algorithms from the start onwards, albeit slightly suboptimally.

(back)