Sorting (Pairwise Sums)
Let , and let and be sets of numbers in a linearly ordered domain. The question is to sort their pairwise sums. In the usual algorithmic formulation, the items to be sorted are indexed by pairs, so repeated values are retained:
with output in nondecreasing order. The literal set
contains only distinct values; it can be obtained from the sorted list by deleting repetitions. The central complexity question is the worst-case running time, particularly in the comparison model, for sorting these sums. The standard comparison-based bounds treat the pair-indexed sums as the items. Open Problems Project, Problem 41
Background
This problem is a structured instance of sorting with partial information: the input sums are not arbitrary, because sorting and imposes a grid-shaped partial order on the pair-indexed sums. Fredman’s 1976 paper is the earliest known reference; it attributes the problem to Elwyn Berlekamp. The question also matters as a source of reductions: sorting is a hardness benchmark for several geometric problems, including computing Minkowski sums of orthogonal-convex polygons, sorting vertices of a line arrangement, and sorting interpoint distances. Fredman also noted an application to multiplying sparse polynomials. Open Problems Project, Problem 41 Fredman (1976) Hernández Barrera (1996) Barequet and Har-Peled (2001)
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.