1 resultado para convex subgraphs
em DI-fusion - The institutional repository of Université Libre de Bruxelles
Filtro por publicador
- Aberystwyth University Repository - Reino Unido (8)
- Academic Archive On-line (Stockholm University; Sweden) (1)
- Acceda, el repositorio institucional de la Universidad de Las Palmas de Gran Canaria. España (1)
- Adam Mickiewicz University Repository (1)
- AMS Tesi di Dottorato - Alm@DL - Università di Bologna (6)
- AMS Tesi di Laurea - Alm@DL - Università di Bologna (1)
- Aquatic Commons (1)
- ArchiMeD - Elektronische Publikationen der Universität Mainz - Alemanha (6)
- Archivo Digital para la Docencia y la Investigación - Repositorio Institucional de la Universidad del País Vasco (11)
- Aston University Research Archive (16)
- Avian Conservation and Ecology - Eletronic Cientific Hournal - Écologie et conservation des oiseaux: (1)
- Biblioteca de Teses e Dissertações da USP (2)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (19)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (BDPI/USP) (19)
- Biblioteca Digital de Teses e Dissertações Eletrônicas da UERJ (9)
- BORIS: Bern Open Repository and Information System - Berna - Suiça (42)
- Boston University Digital Common (2)
- Brock University, Canada (3)
- Bucknell University Digital Commons - Pensilvania - USA (1)
- Bulgarian Digital Mathematics Library at IMI-BAS (61)
- CaltechTHESIS (25)
- Cambridge University Engineering Department Publications Database (35)
- CentAUR: Central Archive University of Reading - UK (41)
- Chinese Academy of Sciences Institutional Repositories Grid Portal (32)
- Cochin University of Science & Technology (CUSAT), India (11)
- Coffee Science - Universidade Federal de Lavras (1)
- Collection Of Biostatistics Research Archive (2)
- CORA - Cork Open Research Archive - University College Cork - Ireland (2)
- Corvinus Research Archive - The institutional repository for the Corvinus University of Budapest (13)
- CUNY Academic Works (1)
- Dalarna University College Electronic Archive (2)
- Deakin Research Online - Australia (38)
- DI-fusion - The institutional repository of Université Libre de Bruxelles (1)
- DigitalCommons - The University of Maine Research (3)
- DigitalCommons@University of Nebraska - Lincoln (1)
- DRUM (Digital Repository at the University of Maryland) (1)
- Duke University (11)
- Helda - Digital Repository of University of Helsinki (7)
- Indian Institute of Science - Bangalore - Índia (101)
- Instituto Politécnico de Bragança (1)
- Instituto Politécnico do Porto, Portugal (3)
- Lume - Repositório Digital da Universidade Federal do Rio Grande do Sul (2)
- Martin Luther Universitat Halle Wittenberg, Germany (1)
- Massachusetts Institute of Technology (10)
- Memorial University Research Repository (1)
- National Center for Biotechnology Information - NCBI (4)
- Plymouth Marine Science Electronic Archive (PlyMSEA) (1)
- Publishing Network for Geoscientific & Environmental Data (16)
- QSpace: Queen's University - Canada (1)
- QUB Research Portal - Research Directory and Institutional Repository for Queen's University Belfast (47)
- Queensland University of Technology - ePrints Archive (43)
- RDBU - Repositório Digital da Biblioteca da Unisinos (1)
- Repositório Científico do Instituto Politécnico de Lisboa - Portugal (1)
- Repositório digital da Fundação Getúlio Vargas - FGV (13)
- Repositório Digital da UNIVERSIDADE DA MADEIRA - Portugal (1)
- Repositório Institucional da Universidade de Aveiro - Portugal (9)
- Repositório Institucional da Universidade Estadual de São Paulo - UNESP (1)
- Repositório Institucional UNESP - Universidade Estadual Paulista "Julio de Mesquita Filho" (154)
- SAPIENTIA - Universidade do Algarve - Portugal (3)
- Universidad de Alicante (17)
- Universidad del Rosario, Colombia (3)
- Universidad Politécnica de Madrid (30)
- Universidade Complutense de Madrid (2)
- Universidade Federal do Pará (3)
- Universidade Federal do Rio Grande do Norte (UFRN) (11)
- Universita di Parma (2)
- Universitat de Girona, Spain (11)
- Universitätsbibliothek Kassel, Universität Kassel, Germany (5)
- Université de Lausanne, Switzerland (1)
- Université de Montréal, Canada (18)
- University of Connecticut - USA (1)
- University of Michigan (7)
- University of Queensland eSpace - Australia (15)
- University of Washington (8)
- WestminsterResearch - UK (4)
Resumo:
We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (STOC 1992) showed that there exists a polynomial-time algorithm for the problem achieving this bound up to a constant factor. Their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it impractical. We develop efficient algorithms for sorting under partial information. Like Kahn and Kim, our approach relies on graph entropy. However, our algorithms differ in essential ways from theirs. Rather than resorting to convex programming for computing the entropy, we approximate the entropy, or make sure it is computed only once in a restricted class of graphs, permitting the use of a simpler algorithm. Specifically, we present: an O(n2) algorithm performing O(log n·log e(P)) comparisons; an O(n2.5) algorithm performing at most (1+ε) log e(P) + Oε(n) comparisons; an O(n2.5) algorithm performing O(log e(P)) comparisons. All our algorithms are simple to implement. © 2010 ACM.