16 resultados para Almost Contact Manifold
Filtro por publicador
- Abertay Research Collections - Abertay University’s repository (1)
- Applied Math and Science Education Repository - Washington - USA (1)
- Aquatic Commons (2)
- ArchiMeD - Elektronische Publikationen der Universität Mainz - Alemanha (1)
- Archive of European Integration (1)
- Archivo Digital para la Docencia y la Investigación - Repositorio Institucional de la Universidad del País Vasco (4)
- Aston University Research Archive (2)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (BDPI/USP) (18)
- Biblioteca Digital de la Universidad Católica Argentina (1)
- Biblioteca Digital de Teses e Dissertações Eletrônicas da UERJ (4)
- Boston University Digital Common (4)
- Brock University, Canada (6)
- Bulgarian Digital Mathematics Library at IMI-BAS (8)
- CaltechTHESIS (3)
- Cámara de Comercio de Bogotá, Colombia (2)
- Cambridge University Engineering Department Publications Database (117)
- CentAUR: Central Archive University of Reading - UK (41)
- Center for Jewish History Digital Collections (4)
- Chinese Academy of Sciences Institutional Repositories Grid Portal (63)
- Cochin University of Science & Technology (CUSAT), India (5)
- CORA - Cork Open Research Archive - University College Cork - Ireland (2)
- Dalarna University College Electronic Archive (2)
- Deakin Research Online - Australia (193)
- DI-fusion - The institutional repository of Université Libre de Bruxelles (2)
- Digital Commons at Florida International University (2)
- DRUM (Digital Repository at the University of Maryland) (1)
- Duke University (2)
- eResearch Archive - Queensland Department of Agriculture; Fisheries and Forestry (1)
- eScholarship Repository - University of California (1)
- Gallica, Bibliotheque Numerique - Bibliothèque nationale de France (French National Library) (BnF), France (3)
- Greenwich Academic Literature Archive - UK (1)
- Helda - Digital Repository of University of Helsinki (16)
- Indian Institute of Science - Bangalore - Índia (84)
- Instituto Politécnico do Porto, Portugal (5)
- Massachusetts Institute of Technology (3)
- Ministerio de Cultura, Spain (4)
- QSpace: Queen's University - Canada (1)
- QUB Research Portal - Research Directory and Institutional Repository for Queen's University Belfast (163)
- Queensland University of Technology - ePrints Archive (183)
- Repositório Científico do Instituto Politécnico de Lisboa - Portugal (2)
- Repositório Institucional da Universidade de Aveiro - Portugal (2)
- RUN (Repositório da Universidade Nova de Lisboa) - FCT (Faculdade de Cienecias e Technologia), Universidade Nova de Lisboa (UNL), Portugal (4)
- SAPIENTIA - Universidade do Algarve - Portugal (1)
- School of Medicine, Washington University, United States (2)
- Universidad del Rosario, Colombia (3)
- Universidade Complutense de Madrid (1)
- Universidade do Algarve (1)
- Universitat de Girona, Spain (1)
- Universitätsbibliothek Kassel, Universität Kassel, Germany (2)
- Université de Lausanne, Switzerland (6)
- Université de Montréal, Canada (10)
- University of Michigan (1)
- University of Southampton, United Kingdom (1)
- University of Washington (1)
- WestminsterResearch - UK (1)
- Worcester Research and Publications - Worcester Research and Publications - UK (2)
Resumo:
We show that the ratio of matched individuals to blocking pairs grows linearly with the number of propose–accept rounds executed by the Gale–Shapley algorithm for the stable marriage problem. Consequently, the participants can arrive at an almost stable matching even without full information about the problem instance; for each participant, knowing only its local neighbourhood is enough. In distributed-systems parlance, this means that if each person has only a constant number of acceptable partners, an almost stable matching emerges after a constant number of synchronous communication rounds. We apply our results to give a distributed (2 + ε)-approximation algorithm for maximum-weight matching in bicoloured graphs and a centralised randomised constant-time approximation scheme for estimating the size of a stable matching.