5 Search Results for "Manlove, David"

Document
DOI: 10.4230/LIPIcs.ESA.2022.36
Multi-Dimensional Stable Roommates in 2-Dimensional Euclidean Space

Authors: Jiehua Chen and Sanjukta Roy

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

Abstract
We investigate the Euclidean 𝖽-Dimensional Stable Roommates problem, which asks whether a given set V of 𝖽⋅ n points from the 2-dimensional Euclidean space can be partitioned into n disjoint (unordered) subsets Π = {V₁,…,V_{n}} with |V_i| = 𝖽 for each V_i ∈ Π such that Π is {stable}. Here, {stability} means that no point subset W ⊆ V is blocking Π, and W is said to be {blocking} Π if |W| = 𝖽 such that ∑_{w' ∈ W}δ(w,w') < ∑_{v ∈ Π(w)}δ(w,v) holds for each point w ∈ W, where Π(w) denotes the subset V_i ∈ Π which contains w and δ(a,b) denotes the Euclidean distance between points a and b. Complementing the existing known polynomial-time result for 𝖽 = 2, we show that such polynomial-time algorithms cannot exist for any fixed number 𝖽 ≥ 3 unless P=NP. Our result for 𝖽 = 3 answers a decade-long open question in the theory of Stable Matching and Hedonic Games [Iwama et al., 2007; Arkin et al., 2009; Vladimir G. Deineko and Gerhard J. Woeginger, 2013; Vladimir G. Deineko and Gerhard J. Woeginger, 2013; David F. Manlove, 2013].
Cite as

Jiehua Chen and Sanjukta Roy. Multi-Dimensional Stable Roommates in 2-Dimensional Euclidean Space. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ESA.2022.36,
  author =	{Chen, Jiehua and Roy, Sanjukta},
  title =	{{Multi-Dimensional Stable Roommates in 2-Dimensional Euclidean Space}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{36:1--36:16},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.36},
  URN =		{urn:nbn:de:0030-drops-169741},
  doi =		{10.4230/LIPIcs.ESA.2022.36},
  annote =	{Keywords: stable matchings, multidimensional stable roommates, Euclidean preferences, coalition formation games, stable cores, NP-hardness}
}
Document
DOI: 10.4230/LIPIcs.SEA.2020.19
An Algorithm for the Exact Treedepth Problem

Authors: James Trimble

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract
We present a novel algorithm for the minimum-depth elimination tree problem, which is equivalent to the optimal treedepth decomposition problem. Our algorithm makes use of two cheaply-computed lower bound functions to prune the search tree, along with symmetry-breaking and domination rules. We present an empirical study showing that the algorithm outperforms the current state-of-the-art solver (which is based on a SAT encoding) by orders of magnitude on a range of graph classes.
Cite as

James Trimble. An Algorithm for the Exact Treedepth Problem. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{trimble:LIPIcs.SEA.2020.19,
  author =	{Trimble, James},
  title =	{{An Algorithm for the Exact Treedepth Problem}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.19},
  URN =		{urn:nbn:de:0030-drops-120938},
  doi =		{10.4230/LIPIcs.SEA.2020.19},
  annote =	{Keywords: Treedepth, Elimination Tree, Graph Algorithms}
}
Document
DOI: 10.4230/LIPIcs.SEA.2020.20
Algorithms for New Types of Fair Stable Matchings

Authors: Frances Cooper and David Manlove

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract
We study the problem of finding "fair" stable matchings in the Stable Marriage problem with Incomplete lists (SMI). For an instance I of SMI there may be many stable matchings, providing significantly different outcomes for the sets of men and women. We introduce two new notions of fairness in SMI. Firstly, a regret-equal stable matching minimises the difference in ranks of a worst-off man and a worst-off woman, among all stable matchings. Secondly, a min-regret sum stable matching minimises the sum of ranks of a worst-off man and a worst-off woman, among all stable matchings. We present two new efficient algorithms to find stable matchings of these types. Firstly, the Regret-Equal Degree Iteration Algorithm finds a regret-equal stable matching in O(d₀ nm) time, where d₀ is the absolute difference in ranks between a worst-off man and a worst-off woman in the man-optimal stable matching, n is the number of men or women, and m is the total length of all preference lists. Secondly, the Min-Regret Sum Algorithm finds a min-regret sum stable matching in O(d_s m) time, where d_s is the difference in the ranks between a worst-off man in each of the woman-optimal and man-optimal stable matchings. Experiments to compare several types of fair optimal stable matchings were conducted and show that the Regret-Equal Degree Iteration Algorithm produces matchings that are competitive with respect to other fairness objectives. On the other hand, existing types of "fair" stable matchings did not provide as close an approximation to regret-equal stable matchings.
Cite as

Frances Cooper and David Manlove. Algorithms for New Types of Fair Stable Matchings. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 20:1-20:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cooper_et_al:LIPIcs.SEA.2020.20,
  author =	{Cooper, Frances and Manlove, David},
  title =	{{Algorithms for New Types of Fair Stable Matchings}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{20:1--20:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.20},
  URN =		{urn:nbn:de:0030-drops-120945},
  doi =		{10.4230/LIPIcs.SEA.2020.20},
  annote =	{Keywords: Stable marriage, Algorithms, Optimality, Fair stable matchings, Regret-equality, Min-regret sum}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.21
Pairwise Preferences in the Stable Marriage Problem

Authors: Ágnes Cseh and Attila Juhos

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
We study the classical, two-sided stable marriage problem under pairwise preferences. In the most general setting, agents are allowed to express their preferences as comparisons of any two of their edges and they also have the right to declare a draw or even withdraw from such a comparison. This freedom is then gradually restricted as we specify six stages of orderedness in the preferences, ending with the classical case of strictly ordered lists. We study all cases occurring when combining the three known notions of stability - weak, strong and super-stability - under the assumption that each side of the bipartite market obtains one of the six degrees of orderedness. By designing three polynomial algorithms and two NP-completeness proofs we determine the complexity of all cases not yet known, and thus give an exact boundary in terms of preference structure between tractable and intractable cases.
Cite as

Ágnes Cseh and Attila Juhos. Pairwise Preferences in the Stable Marriage Problem. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cseh_et_al:LIPIcs.STACS.2019.21,
  author =	{Cseh, \'{A}gnes and Juhos, Attila},
  title =	{{Pairwise Preferences in the Stable Marriage Problem}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{21:1--21:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.21},
  URN =		{urn:nbn:de:0030-drops-102603},
  doi =		{10.4230/LIPIcs.STACS.2019.21},
  annote =	{Keywords: stable marriage, intransitivity, acyclic preferences, poset, weakly stable matching, strongly stable matching, super stable matching}
}
Document
DOI: 10.4230/LIPIcs.SEA.2018.8
A 3/2-Approximation Algorithm for the Student-Project Allocation Problem

Authors: Frances Cooper and David Manlove

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

Abstract
The Student-Project Allocation problem with lecturer preferences over Students (SPA-S) comprises three sets of agents, namely students, projects and lecturers, where students have preferences over projects and lecturers have preferences over students. In this scenario we seek a stable matching, that is, an assignment of students to projects such that there is no student and lecturer who have an incentive to deviate from their assignee/s. We study SPA-ST, the extension of SPA-S in which the preference lists of students and lecturers need not be strictly ordered, and may contain ties. In this scenario, stable matchings may be of different sizes, and it is known that MAX SPA-ST, the problem of finding a maximum stable matching in SPA-ST, is NP-hard. We present a linear-time 3/2-approximation algorithm for MAX SPA-ST and an Integer Programming (IP) model to solve MAX SPA-ST optimally. We compare the approximation algorithm with the IP model experimentally using randomly-generated data. We find that the performance of the approximation algorithm easily surpassed the 3/2 bound, constructing a stable matching within 92% of optimal in all cases, with the percentage being far higher for many instances.
Cite as

Frances Cooper and David Manlove. A 3/2-Approximation Algorithm for the Student-Project Allocation Problem. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cooper_et_al:LIPIcs.SEA.2018.8,
  author =	{Cooper, Frances and Manlove, David},
  title =	{{A 3/2-Approximation Algorithm for the Student-Project Allocation Problem}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{8:1--8:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.8},
  URN =		{urn:nbn:de:0030-drops-89439},
  doi =		{10.4230/LIPIcs.SEA.2018.8},
  annote =	{Keywords: Matching problems, Approximation, Algorithms, Stability}
}
  • Refine by Author
  • 2 Cooper, Frances
  • 2 Manlove, David
  • 1 Chen, Jiehua
  • 1 Cseh, Ágnes
  • 1 Juhos, Attila
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Design and analysis of algorithms
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Algorithm design techniques
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Problems, reductions and completeness
  • Show More...

  • Refine by Keyword
  • 2 Algorithms
  • 1 Approximation
  • 1 Elimination Tree
  • 1 Euclidean preferences
  • 1 Fair stable matchings
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2020
  • 1 2018
  • 1 2019
  • 1 2022

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 Imprint Privacy Contact