Optimal selection and sorting via dynamic programming

DOI10.1145/2444016.2493373MaRDI QIDQ5178742zbMATH OpenOpenAlexFDO

Authors Micha Hofri

Publication date 16 March 2015

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2444016.2493373

zbMATH Keywords

Markov decision processgraph isomorphismoptimal selectionoptimal sortingsmall set

Mathematics Subject Classification ID

Applications of continuous-time Markov processes on discrete state spaces (60J28) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Combinatorial optimization (90C27) Dynamic programming (90C39) Searching and sorting (68P10)

Recommendations

• scientific article; zbMATH DE number 67282
• Sorting with expensive comparands
• Automata, Languages and Programming
• New algorithms for selection
• Optimal decision processes and algorithms

Cited in

(7)

• Further analysis of the remedian algorithm
• Efficient Sorting in a Dynamic Adverse-Selection Model
• On the best order of observation in optimal stopping problems
• An Aid For The Selection Of Efficient Storage Structures
• On computing an optimal permutation of ranks for multiselection
• Energy efficient sorting, selection and searching
• A selectable sloppy heap

This page was built for publication: Optimal selection and sorting via dynamic programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5178742)