Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
On High-Quality Synthesis Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Subquadratic Algorithms for Succinct Stable Matching

verfasst von : Daniel Moeller, Ramamohan Paturi, Stefan Schneider

Erschienen in: Computer Science – Theory and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We consider the stable matching problem when the preference lists are not given explicitly but are represented in a succinct way and ask whether the problem becomes computationally easier. We give subquadratic algorithms for finding a stable matching in special cases of two very natural succinct representations of the problem, the d-attribute and d-list models. We also give algorithms for verifying a stable matching in the same models. We further show that for \(d = \omega (\log n)\) both finding and verifying a stable matching in the d-attribute model requires quadratic time assuming the Strong Exponential Time Hypothesis. The d-attribute model is therefore as hard as the general case for large enough values of d.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Algorithmic Statistics: Normal Objects and Universal Models
Nächstes Kapitel Depth-4 Identity Testing and Noether’s Normalization Lemma
Literatur
1.
Abboud, A., Backurs, A., Williams, V.V.: Quadratic-time hardness of LCS and other sequence similarity measures. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS). IEEE (2015)
2.
3.
Alman, J., Williams, R.: Probabilistic polynomials and hamming nearest neighbors. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS). IEEE (2015)
4.
Arkin, E.M., Bae, S.W., Efrat, A., Okamoto, K., Mitchell, J.S., Polishchuk, V.: Geometric stable roommates. Inf. Process. Lett. 109(4), 219–224 (2009)MathSciNetCrossRefMATH
5.
Backurs, A., Indyk, P.: Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, 14–17 June 2015, pp. 51–58 (2015)
6.
Bartholdi, J., Trick, M.A.: Stable matching with preferences derived from a psychological model. Oper. Res. Lett. 5(4), 165–169 (1986)MathSciNetCrossRefMATH
7.
Bhatnagar, N., Greenberg, S., Randall, D.: Sampling stable marriages: why spouse-swapping won’t work. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, pp. 1223–1232 (2008)
8.
9.
Bringmann, K.: Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless seth fails. In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), pp. 661–670. IEEE (2014)
10.
Carmosino, M.L., Gao, J., Impagliazzo, R., Mihajlin, I., Paturi, R., Schneider, S.: Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pp. 261–270. ACM (2016)
11.
Chebolu, P., Goldberg, L.A., Martin, R.: The complexity of approximately counting stable matchings. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX and RANDOM 2010. LNCS, vol. 6302, pp. 81–94. Springer, Heidelberg (2010)CrossRef
12.
Dabney, J., Dean, B.C.: Adaptive stable marriage algorithms. In: Proceedings of the 48th Annual Southeast Regional Conference, p. 35. ACM (2010)
13.
Dobkin, D.P., Kirkpatrick, D.G.: A linear algorithm for determining the separation of convex polyhedra. J. Algorithms 6(3), 381–392 (1985)MathSciNetCrossRefMATH
14.
15.
Gonczarowski, Y.A., Nisan, N., Ostrovsky, R., Rosenbaum, W.: A stable marriage requires communication. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1003–1017. SIAM (2015)
16.
Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. Foundations of Computing Series. MIT Press, Cambridge (1989)MATH
17.
Hershberger, J., Suri, S.: A pedestrian approach to ray shooting: shoot a ray, take a walk. J. Algorithms 18(3), 403–431 (1995)MathSciNetCrossRefMATH
18.
19.
Impagliazzo, R., Paturi, R., Schneider, S.: A satisfiability algorithm for sparse depth two threshold circuits. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pp. 479–488. IEEE (2013)
20.
Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63, 512–530 (2001)MathSciNetCrossRefMATH
21.
Knuth, D.E.: Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms, vol. 10. American Mathematical Society, Providence (1997)
22.
23.
Matoušek, J., Schwarzkopf, O.: Linear optimization queries. In: Proceedings of the Eighth Annual Symposium on Computational Geometry, pp. 16–25. ACM (1992)
24.
Ng, C., Hirschberg, D.S.: Lower bounds for the stable marriage problem and its variants. SIAM J. Comput. 19(1), 71–77 (1990)MathSciNetCrossRefMATH
25.
Patrascu, M., Williams, R.: On the possibility of faster SAT algorithms. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, 17–19 January 2010, pp. 1065–1075 (2010)
26.
Razborov, A.A.: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Math. Notes 41(4), 333–338 (1987)MathSciNetCrossRefMATH
27.
Roth, A.E., Sotomayor, M.A.O.: Two-sided Matching: A Study in Game - Theoretic Modeling and Analysis. Econometric Society Monographs. Cambridge University, Cambridge (1990)CrossRefMATH
28.
Segal, I.: The communication requirements of social choice rules and supporting budget sets. J. Econ. Theory 136(1), 341–378 (2007)MathSciNetCrossRefMATH
29.
Smolensky, R.: Algebraic methods in the theory of lower bounds for boolean circuit complexity. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pp. 77–82. ACM (1987)
30.
Williams, R.: A new algorithm for optimal constraint satisfaction and its implications. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 1227–1237. Springer, Heidelberg (2004)CrossRef
31.
Williams, R.: Faster all-pairs shortest paths via circuit complexity. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp. 664–673. ACM (2014)
Metadaten
Titel
Subquadratic Algorithms for Succinct Stable Matching
verfasst von
Daniel Moeller
Ramamohan Paturi
Stefan Schneider
Copyright-Jahr
2016
Buch
Computer Science – Theory and Applications

Print ISBN: 978-3-319-34170-5

Electronic ISBN: 978-3-319-34171-2

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-34171-2_21