File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Algorithms for the generalized sorting problem

TitleAlgorithms for the generalized sorting problem
Authors
KeywordsAlgorithm
Comparison-Sort
Sorting
Issue Date2011
Citation
Proceedings - Annual Ieee Symposium On Foundations Of Computer Science, Focs, 2011, p. 738-747 How to Cite?
AbstractWe study the generalized sorting problem where we are given a set of n elements to be sorted but only a subset of all possible pair wise element comparisons is allowed. The goal is to determine the sorted order using the smallest possible number of allowed comparisons. The generalized sorting problem may be equivalently viewed as follows. Given an undirected graph G(V, E) where V is the set of elements to be sorted and E defines the set of allowed comparisons, adaptively find the smallest subset E′ ⊆ E of edges to probe such that the directed graph induced by E′ contains a Hamiltonian path. When G is a complete graph, we get the standard sorting problem, and it is well-known that Θ(n log n) comparisons are necessary and sufficient. An extensively studied special case of the generalized sorting problem is the nuts and bolts problem where the allowed comparison graph is a complete bipartite graph between two equal-size sets. It is known that for this special case also, there is a deterministic algorithm that sorts using Θ(n log n) comparisons. However, when the allowed comparison graph is arbitrary, to our knowledge, no bound better than the trivial O(n 2) bound is known. Our main result is a randomized algorithm that sorts any allowed comparison graph using Õ(n 3/2) comparisons with high probability (provided the input is sortable). We also study the sorting problem in randomly generated allowed comparison graphs, and show that when the edge probability is p, Õ(min{n/p 2, n 3/2 √p}) comparisons suffice on average to sort. © 2011 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/188497
ISSN
2020 SCImago Journal Rankings: 2.949
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorHuang, Zen_US
dc.contributor.authorKannan, Sen_US
dc.contributor.authorKhanna, Sen_US
dc.date.accessioned2013-09-03T04:08:44Z-
dc.date.available2013-09-03T04:08:44Z-
dc.date.issued2011en_US
dc.identifier.citationProceedings - Annual Ieee Symposium On Foundations Of Computer Science, Focs, 2011, p. 738-747en_US
dc.identifier.issn0272-5428en_US
dc.identifier.urihttp://hdl.handle.net/10722/188497-
dc.description.abstractWe study the generalized sorting problem where we are given a set of n elements to be sorted but only a subset of all possible pair wise element comparisons is allowed. The goal is to determine the sorted order using the smallest possible number of allowed comparisons. The generalized sorting problem may be equivalently viewed as follows. Given an undirected graph G(V, E) where V is the set of elements to be sorted and E defines the set of allowed comparisons, adaptively find the smallest subset E′ ⊆ E of edges to probe such that the directed graph induced by E′ contains a Hamiltonian path. When G is a complete graph, we get the standard sorting problem, and it is well-known that Θ(n log n) comparisons are necessary and sufficient. An extensively studied special case of the generalized sorting problem is the nuts and bolts problem where the allowed comparison graph is a complete bipartite graph between two equal-size sets. It is known that for this special case also, there is a deterministic algorithm that sorts using Θ(n log n) comparisons. However, when the allowed comparison graph is arbitrary, to our knowledge, no bound better than the trivial O(n 2) bound is known. Our main result is a randomized algorithm that sorts any allowed comparison graph using Õ(n 3/2) comparisons with high probability (provided the input is sortable). We also study the sorting problem in randomly generated allowed comparison graphs, and show that when the edge probability is p, Õ(min{n/p 2, n 3/2 √p}) comparisons suffice on average to sort. © 2011 IEEE.en_US
dc.languageengen_US
dc.relation.ispartofProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCSen_US
dc.subjectAlgorithmen_US
dc.subjectComparison-Sorten_US
dc.subjectSortingen_US
dc.titleAlgorithms for the generalized sorting problemen_US
dc.typeConference_Paperen_US
dc.identifier.emailHuang, Z: hzhiyi@cis.upenn.eduen_US
dc.identifier.authorityHuang, Z=rp01804en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1109/FOCS.2011.54en_US
dc.identifier.scopuseid_2-s2.0-84863324249en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-84863324249&selection=ref&src=s&origin=recordpageen_US
dc.identifier.spage738en_US
dc.identifier.epage747en_US
dc.identifier.isiWOS:000298962700078-
dc.identifier.scopusauthoridHuang, Z=55494568500en_US
dc.identifier.scopusauthoridKannan, S=7102340548en_US
dc.identifier.scopusauthoridKhanna, S=7401552504en_US
dc.identifier.issnl0272-5428-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats