1 resultado para Librarianship the Information Science
em DI-fusion - The institutional repository of Université Libre de Bruxelles
Filtro por publicador
- KUPS-Datenbank - Universität zu Köln - Kölner UniversitätsPublikationsServer (1)
- Repository Napier (3)
- Aberystwyth University Repository - Reino Unido (9)
- Adam Mickiewicz University Repository (3)
- Applied Math and Science Education Repository - Washington - USA (1)
- Aquatic Commons (16)
- Archive of European Integration (20)
- Archivo Digital para la Docencia y la Investigación - Repositorio Institucional de la Universidad del País Vasco (3)
- Aston University Research Archive (10)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (4)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (BDPI/USP) (12)
- Biodiversity Heritage Library, United States (4)
- BORIS: Bern Open Repository and Information System - Berna - Suiça (11)
- Boston University Digital Common (1)
- Brock University, Canada (7)
- Bucknell University Digital Commons - Pensilvania - USA (4)
- Bulgarian Digital Mathematics Library at IMI-BAS (8)
- CaltechTHESIS (1)
- Cambridge University Engineering Department Publications Database (16)
- CentAUR: Central Archive University of Reading - UK (45)
- Chinese Academy of Sciences Institutional Repositories Grid Portal (12)
- Cochin University of Science & Technology (CUSAT), India (17)
- Comissão Econômica para a América Latina e o Caribe (CEPAL) (37)
- CORA - Cork Open Research Archive - University College Cork - Ireland (4)
- Cornell: DigitalCommons@ILR (2)
- Corvinus Research Archive - The institutional repository for the Corvinus University of Budapest (1)
- CUNY Academic Works (13)
- Dalarna University College Electronic Archive (4)
- Deakin Research Online - Australia (49)
- Department of Computer Science E-Repository - King's College London, Strand, London (2)
- DI-fusion - The institutional repository of Université Libre de Bruxelles (1)
- Digital Commons @ DU | University of Denver Research (7)
- Digital Commons @ Winthrop University (6)
- Digital Commons at Florida International University (4)
- Digital Howard @ Howard University | Howard University Research (1)
- Digital Peer Publishing (1)
- DigitalCommons@The Texas Medical Center (4)
- DigitalCommons@University of Nebraska - Lincoln (6)
- Doria (National Library of Finland DSpace Services) - National Library of Finland, Finland (1)
- DRUM (Digital Repository at the University of Maryland) (2)
- Duke University (1)
- eResearch Archive - Queensland Department of Agriculture; Fisheries and Forestry (1)
- Greenwich Academic Literature Archive - UK (5)
- Helda - Digital Repository of University of Helsinki (14)
- Illinois Digital Environment for Access to Learning and Scholarship Repository (1)
- Indian Institute of Science - Bangalore - Índia (19)
- Instituto Politécnico do Porto, Portugal (3)
- Massachusetts Institute of Technology (2)
- Memoria Académica - FaHCE, UNLP - Argentina (12)
- Ministerio de Cultura, Spain (3)
- National Center for Biotechnology Information - NCBI (2)
- Nottingham eTheses (1)
- Plymouth Marine Science Electronic Archive (PlyMSEA) (5)
- Portal de Revistas Científicas Complutenses - Espanha (6)
- Publishing Network for Geoscientific & Environmental Data (2)
- QSpace: Queen's University - Canada (2)
- QUB Research Portal - Research Directory and Institutional Repository for Queen's University Belfast (57)
- Queensland University of Technology - ePrints Archive (271)
- Repositorio Académico de la Universidad Nacional de Costa Rica (6)
- Repositório Científico da Universidade de Évora - Portugal (1)
- Repositório Institucional da Universidade de Aveiro - Portugal (1)
- Repositório Institucional da Universidade de Brasília (2)
- Repositório Institucional da Universidade Estadual de São Paulo - UNESP (2)
- Repositório Institucional da Universidade Federal do Rio Grande - FURG (1)
- Repositório Institucional UNESP - Universidade Estadual Paulista "Julio de Mesquita Filho" (45)
- RUN (Repositório da Universidade Nova de Lisboa) - FCT (Faculdade de Cienecias e Technologia), Universidade Nova de Lisboa (UNL), Portugal (2)
- Universidad de Alicante (2)
- Universidad Politécnica de Madrid (6)
- Universidade de Lisboa - Repositório Aberto (1)
- Universidade Federal do Pará (1)
- Universitat de Girona, Spain (1)
- Université de Lausanne, Switzerland (1)
- Université de Montréal (1)
- Université de Montréal, Canada (11)
- University of Michigan (87)
- University of Queensland eSpace - Australia (13)
- University of Southampton, United Kingdom (3)
- University of Washington (3)
- WestminsterResearch - UK (3)
- Worcester Research and Publications - Worcester Research and Publications - UK (1)
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.