Competitive query minimization for stable matching with one-sided uncertainty

DOI10.4230/LIPICS.APPROX/RANDOM.2024.17MaRDI QIDQ6920827zbMATH OpenFDO

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

Publication date 6 October 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX/RANDOM.2024.17

zbMATH Keywords

uncertaintymatching under preferencesstable marriagequery-competitive algorithms

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites work

• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 48303 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 7075885 (Why is no real title available?)
• scientific article; zbMATH DE number 7740865 (Why is no real title available?)
• A stable marriage requires communication
• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• An adversarial model for scheduling with testing
• Approximating minimum feedback sets and multicuts in directed graphs
• College Admissions and the Stability of Marriage
• Competitive query minimization for stable matching with one-sided uncertainty
• Computing minimum spanning trees with uncertainty
• Lower Bounds for the Stable Marriage Problem and Its Variants
• Matching markets under (in)complete information
• Pareto optimal allocation under uncertain preferences: uncertainty models, algorithms, and complexity
• Query-Competitive Sorting with Uncertainty.
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
• Reducibility among combinatorial problems
• Stable matching with uncertain linear preferences

Cited in

(1)

• Competitive query minimization for stable matching with one-sided uncertainty

This page was built for publication: Competitive query minimization for stable matching with one-sided uncertainty

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6920827)