Search Results

Documents authored by Schlöter, Jens

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.17
Competitive Query Minimization for Stable Matching with One-Sided Uncertainty

Authors: Evripidis Bampis, Konstantinos Dogeas, Thomas Erlebach, Nicole Megow, Jens Schlöter, and Amitabh Trehan

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
We study the two-sided stable matching problem with one-sided uncertainty for two sets of agents A and B, with equal cardinality. Initially, the preference lists of the agents in A are given but the preferences of the agents in B are unknown. An algorithm can make queries to reveal information about the preferences of the agents in B. We examine three query models: comparison queries, interviews, and set queries. Using competitive analysis, our aim is to design algorithms that minimize the number of queries required to solve the problem of finding a stable matching or verifying that a given matching is stable (or stable and optimal for the agents of one side). We present various upper and lower bounds on the best possible competitive ratio as well as results regarding the complexity of the offline problem of determining the optimal query set given full information.
Cite as

Evripidis Bampis, Konstantinos Dogeas, Thomas Erlebach, Nicole Megow, Jens Schlöter, and Amitabh Trehan. Competitive Query Minimization for Stable Matching with One-Sided Uncertainty. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 17:1-17:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bampis_et_al:LIPIcs.APPROX/RANDOM.2024.17,
  author =	{Bampis, Evripidis and Dogeas, Konstantinos and Erlebach, Thomas and Megow, Nicole and Schl\"{o}ter, Jens and Trehan, Amitabh},
  title =	{{Competitive Query Minimization for Stable Matching with One-Sided Uncertainty}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{17:1--17:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.17},
  URN =		{urn:nbn:de:0030-drops-210100},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.17},
  annote =	{Keywords: Matching under Preferences, Stable Marriage, Query-Competitive Algorithms, Uncertainty}
}
Document
DOI: 10.4230/DagRep.13.2.1
Scheduling (Dagstuhl Seminar 23061)

Authors: Nicole Megow, Benjamin J. Moseley, David Shmoys, Ola Svensson, Sergei Vassilvitskii, and Jens Schlöter

Published in: Dagstuhl Reports, Volume 13, Issue 2 (2023)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23061 "Scheduling". The seminar focused on the emerging models for beyond-worst case algorithm design, in particular, recent approaches that incorporate learning. This includes models for the integration of learning into algorithm design that have been proposed recently and that have already demonstrated advances in the state-of-art for various scheduling applications: (i) scheduling with error-prone learned predictions, (ii) data-driven algorithm design, and (iii) stochastic and Bayesian learning in scheduling.
Cite as

Nicole Megow, Benjamin J. Moseley, David Shmoys, Ola Svensson, Sergei Vassilvitskii, and Jens Schlöter. Scheduling (Dagstuhl Seminar 23061). In Dagstuhl Reports, Volume 13, Issue 2, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{megow_et_al:DagRep.13.2.1,
  author =	{Megow, Nicole and Moseley, Benjamin J. and Shmoys, David and Svensson, Ola and Vassilvitskii, Sergei and Schl\"{o}ter, Jens},
  title =	{{Scheduling (Dagstuhl Seminar 23061)}},
  pages =	{1--19},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{13},
  number =	{2},
  editor =	{Megow, Nicole and Moseley, Benjamin J. and Shmoys, David and Svensson, Ola and Vassilvitskii, Sergei and Schl\"{o}ter, Jens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.2.1},
  URN =		{urn:nbn:de:0030-drops-191789},
  doi =		{10.4230/DagRep.13.2.1},
  annote =	{Keywords: scheduling, mathematical optimization, approximation algorithms, learning methods, uncertainty}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.49
Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty

Authors: Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, and Jens Schlöter

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We study how to utilize (possibly erroneous) predictions in a model for computing under uncertainty in which an algorithm can query unknown data. Our aim is to minimize the number of queries needed to solve the minimum spanning tree problem, a fundamental combinatorial optimization problem that has been central also to the research area of explorable uncertainty. For all integral γ ≥ 2, we present algorithms that are γ-robust and (1+1/γ)-consistent, meaning that they use at most γOPT queries if the predictions are arbitrarily wrong and at most (1+1/γ)OPT queries if the predictions are correct, where OPT is the optimal number of queries for the given instance. Moreover, we show that this trade-off is best possible. Furthermore, we argue that a suitably defined hop distance is a useful measure for the amount of prediction error and design algorithms with performance guarantees that degrade smoothly with the hop distance. We also show that the predictions are PAC-learnable in our model. Our results demonstrate that untrusted predictions can circumvent the known lower bound of 2, without any degradation of the worst-case ratio. To obtain our results, we provide new structural insights for the minimum spanning tree problem that might be useful in the context of query-based algorithms regardless of predictions. In particular, we generalize the concept of witness sets - the key to lower-bounding the optimum - by proposing novel global witness set structures and completely new ways of adaptively using those.
Cite as

Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, and Jens Schlöter. Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 49:1-49:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{erlebach_et_al:LIPIcs.ESA.2022.49,
  author =	{Erlebach, Thomas and de Lima, Murilo Santos and Megow, Nicole and Schl\"{o}ter, Jens},
  title =	{{Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{49:1--49:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.49},
  URN =		{urn:nbn:de:0030-drops-169872},
  doi =		{10.4230/LIPIcs.ESA.2022.49},
  annote =	{Keywords: explorable uncertainty, queries, untrusted predictions}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.10
Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty

Authors: Evripidis Bampis, Christoph Dürr, Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, and Jens Schlöter

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
Given a hypergraph with uncertain node weights following known probability distributions, we study the problem of querying as few nodes as possible until the identity of a node with minimum weight can be determined for each hyperedge. Querying a node has a cost and reveals the precise weight of the node, drawn from the given probability distribution. Using competitive analysis, we compare the expected query cost of an algorithm with the expected cost of an optimal query set for the given instance. For the general case, we give a polynomial-time f(α)-competitive algorithm, where f(α) ∈ [1.618+ε,2] depends on the approximation ratio α for an underlying vertex cover problem. We also show that no algorithm using a similar approach can be better than 1.5-competitive. Furthermore, we give polynomial-time 4/3-competitive algorithms for bipartite graphs with arbitrary query costs and for hypergraphs with a single hyperedge and uniform query costs, with matching lower bounds.
Cite as

Evripidis Bampis, Christoph Dürr, Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, and Jens Schlöter. Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bampis_et_al:LIPIcs.ESA.2021.10,
  author =	{Bampis, Evripidis and D\"{u}rr, Christoph and Erlebach, Thomas and de Lima, Murilo Santos and Megow, Nicole and Schl\"{o}ter, Jens},
  title =	{{Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{10:1--10:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.10},
  URN =		{urn:nbn:de:0030-drops-145910},
  doi =		{10.4230/LIPIcs.ESA.2021.10},
  annote =	{Keywords: Explorable uncertainty, queries, stochastic optimization, graph orientation, selection problems}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact