1 resultado para Hydraulic Sorting
em DI-fusion - The institutional repository of Université Libre de Bruxelles
Filtro por publicador
- Abertay Research Collections - Abertay University’s repository (1)
- Aberystwyth University Repository - Reino Unido (1)
- Academic Research Repository at Institute of Developing Economies (3)
- Acceda, el repositorio institucional de la Universidad de Las Palmas de Gran Canaria. España (1)
- AMS Tesi di Dottorato - Alm@DL - Università di Bologna (2)
- AMS Tesi di Laurea - Alm@DL - Università di Bologna (2)
- Aquatic Commons (40)
- Archive of European Integration (3)
- Archivo Digital para la Docencia y la Investigación - Repositorio Institucional de la Universidad del País Vasco (8)
- Aston University Research Archive (11)
- B-Digital - Universidade Fernando Pessoa - Portugal (1)
- Biblioteca de Teses e Dissertações da USP (1)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (2)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (BDPI/USP) (1)
- Biblioteca Digital de Teses e Dissertações Eletrônicas da UERJ (18)
- Bioline International (1)
- BORIS: Bern Open Repository and Information System - Berna - Suiça (14)
- Brock University, Canada (4)
- Bucknell University Digital Commons - Pensilvania - USA (8)
- CaltechTHESIS (5)
- Cambridge University Engineering Department Publications Database (86)
- CentAUR: Central Archive University of Reading - UK (20)
- Center for Jewish History Digital Collections (1)
- Chinese Academy of Sciences Institutional Repositories Grid Portal (121)
- Comissão Econômica para a América Latina e o Caribe (CEPAL) (1)
- CORA - Cork Open Research Archive - University College Cork - Ireland (4)
- Corvinus Research Archive - The institutional repository for the Corvinus University of Budapest (1)
- CUNY Academic Works (5)
- Deakin Research Online - Australia (24)
- 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 - Michigan Tech (1)
- Digital Commons @ DU | University of Denver Research (1)
- Digital Commons at Florida International University (3)
- Digital Peer Publishing (2)
- Digital Repository at Iowa State University (2)
- DRUM (Digital Repository at the University of Maryland) (1)
- Duke University (19)
- Earth Simulator Research Results Repository (2)
- eResearch Archive - Queensland Department of Agriculture; Fisheries and Forestry (11)
- Greenwich Academic Literature Archive - UK (1)
- Helda - Digital Repository of University of Helsinki (15)
- Illinois Digital Environment for Access to Learning and Scholarship Repository (1)
- Indian Institute of Science - Bangalore - Índia (80)
- Infoteca EMBRAPA (1)
- Instituto Politécnico do Porto, Portugal (1)
- Laboratório Nacional de Energia e Geologia - Portugal (1)
- Massachusetts Institute of Technology (3)
- Memorial University Research Repository (1)
- Ministerio de Cultura, Spain (2)
- National Center for Biotechnology Information - NCBI (23)
- Open University Netherlands (1)
- Plymouth Marine Science Electronic Archive (PlyMSEA) (3)
- 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 (31)
- Queensland University of Technology - ePrints Archive (131)
- Repositório Alice (Acesso Livre à Informação Científica da Embrapa / Repository Open Access to Scientific Information from Embrapa) (2)
- Repositório Científico do Instituto Politécnico de Lisboa - Portugal (1)
- Repositório digital da Fundação Getúlio Vargas - FGV (1)
- Repositório Institucional UNESP - Universidade Estadual Paulista "Julio de Mesquita Filho" (14)
- RUN (Repositório da Universidade Nova de Lisboa) - FCT (Faculdade de Cienecias e Technologia), Universidade Nova de Lisboa (UNL), Portugal (1)
- SAPIENTIA - Universidade do Algarve - Portugal (1)
- The Scholarly Commons | School of Hotel Administration; Cornell University Research (1)
- Universidad de Alicante (1)
- Universidad Politécnica de Madrid (11)
- Universidade Complutense de Madrid (1)
- Universita di Parma (1)
- Université de Montréal, Canada (2)
- University of Connecticut - USA (2)
- University of Michigan (143)
- University of Queensland eSpace - Australia (30)
- University of Washington (4)
- WestminsterResearch - 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.