Sorting sums of binary decision summands

2017/04/19 by Torsten Groß, Nils Blüthgen, Gross, Torsten +1
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #Digital Image Processing Techniques #FOS: Computer and information sciences #QR Code Applications and Technologies

paper · pdf · doi:10.48550/arxiv.1704.05795

openalex publication_date 2017/04/19 · openalex created_date 2017/05/05 · openalex updated_date 2026/07/28

Abstract

A sum where each of the N summands can be independently chosen from two choices yields 2^N possible summation outcomes. There is an O(K²)-algorithm that finds the K smallest/largest of these sums by evading the enumeration of all sums.

Citations

• A Threshold Selection Method from Gray-Level Histograms

Related

• An Explicit and Efficient O(n²)-Time Algorithm for Sorting Sumsets
• Selective algorithm processing of subset sum distributions
• The Decision Tree Complexity for k-SUM is at most Nearly Quadratic
• Near-optimal linear decision trees for k-SUM and related problems
• Solving k-SUM using few linear queries