At most 3.55nstable matchings

Cory Palmer, Domotor Palvolgyi

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

We improve the upper bound for the maximum possible number of stable matchings among n jobs and n applicants from 131072n+ O(1) to 3.55n+ O(1). To establish this bound, we state a novel formulation of a certain entropy bound that is easy to apply and may be of independent interest in counting other combinatorial objects.

Original languageEnglish
Title of host publicationProceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021
PublisherIEEE Computer Society
Pages217-227
Number of pages11
ISBN (Electronic)9781665420556
DOIs
StatePublished - 2022
Event62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 - Virtual, Online, United States
Duration: Feb 7 2022Feb 10 2022

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2022-February
ISSN (Print)0272-5428

Conference

Conference62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021
Country/TerritoryUnited States
CityVirtual, Online
Period02/7/2202/10/22

Keywords

  • entropy
  • stable matchings

Fingerprint

Dive into the research topics of 'At most 3.55nstable matchings'. Together they form a unique fingerprint.

Cite this