NDLI: Twenty-Five Comparators Is Optimal When Sorting Nine Inputs (and Twenty-Nine for Ten)

Content Provider	IEEE Xplore Digital Library
Author	Codish, M. Cruz-Filipe, L. Frank, M. Schneider-Kamp, P.
Copyright Year	2014
Description	Author affiliation: Dept. of Math. & Comput. Sci., Univ. of Southern Denmark, Odense, Denmark (Cruz-Filipe, L.; Schneider-Kamp, P.) \|\| Dept. of Comput. Sci., Ben-Gurion Univ. of the Negev, Beer-Sheva, Israel (Codish, M.; Frank, M.)
Abstract	This paper describes a computer-assisted non-existence proof of 9-input sorting networks consisting of 24 comparators, hence showing that the 25-comparator sorting network found by Floyd in 1964 is optimal. As a corollary, we obtain that the 29-comparator network found by Waksman in 1969 is optimal when sorting 10 inputs. This closes the two smallest open instances of the optimal-size sorting network problem, which have been open since the results of Floyd and Knuth from 1966 proving optimality for sorting networks of up to 8 inputs. The proof involves a combination of two methodologies: one based on exploiting the abundance of symmetries in sorting networks, and the other based on an encoding of the problem to that of satisfiability of propositional logic. We illustrate that, while each of these can single-handedly solve smaller instances of the problem, it is their combination that leads to the more efficient solution that scales to handle 9 inputs.
Starting Page	186
Ending Page	193
File Size	802848
Page Count	8
File Format	PDF
ISBN	9781479965724
ISSN	10823409
DOI	10.1109/ICTAI.2014.36
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2014-11-10
Publisher Place	Cyprus
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Sorting Encoding Optimization Search problems Instruction sets Computer science Educational institutions
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Twenty-five comparators is optimal when sorting nine inputs (and twenty-nine for ten (2014)

Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten)

Non-dominated sorting cuckoo search for multiobjective optimization

A computer assisted optimal depth lower bound for sorting networks with nine inputs

A computer assisted optimal depth lower bound for sorting networks with nine inputs

ILGA: An Improved Local Greedy Algorithm for Optimal Parameters Searches

Differentially Encoded Search Trees

Morphic search strategies

Comparison of serial and parallel searching in multicore systems

Twenty-Five Comparators Is Optimal When Sorting Nine Inputs (and Twenty-Nine for Ten)

Similar Documents

Twenty-five comparators is optimal when sorting nine inputs (and twenty-nine for ten (2014)

Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten)

Non-dominated sorting cuckoo search for multiobjective optimization

A computer assisted optimal depth lower bound for sorting networks with nine inputs

A computer assisted optimal depth lower bound for sorting networks with nine inputs

ILGA: An Improved Local Greedy Algorithm for Optimal Parameters Searches

Differentially Encoded Search Trees

Morphic search strategies

Comparison of serial and parallel searching in multicore systems

Twenty-Five Comparators Is Optimal When Sorting Nine Inputs (and Twenty-Nine for Ten)