Slowing down sorting networks to obtain faster sorting algorithms
From MaRDI portal
Publication:4601942
DOI10.1145/7531.7537zbMath1378.68037OpenAlexW2013382394WikidataQ127516402 ScholiaQ127516402MaRDI QIDQ4601942
Publication date: 25 January 2018
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/7531.7537
Related Items (only showing first 100 items - show all)
Iterated nearest neighbors and finding minimal polytopes ⋮ Computing the similarity between moving curves ⋮ Computing the smallest \(k\)-enclosing circle and related problems ⋮ Extremal polygon containment problems ⋮ Improved algorithms for the bichromatic two-center problem for pairs of points ⋮ Selecting distances in the plane ⋮ Reverse shortest path problem for unit-disk graphs ⋮ An approximation algorithm for least median of squares regression ⋮ Finding a minimum-weight \(k\)-link path in graphs with the concave Monge property and applications ⋮ Computing a centerpoint of a finite planar set of points in linear time ⋮ Partitioning point sets in arbitrary dimension ⋮ Efficient algorithms for center problems in cactus networks ⋮ Matroid and knapsack center problems ⋮ Computing the Center of Uncertain Points on Tree Networks ⋮ Approximating points by a piecewise linear function ⋮ Using sparsification for parametric minimum spanning tree problems ⋮ Parametric problems on graphs of bounded tree-width ⋮ Optimal parametric search on graphs of bounded tree-width ⋮ The (1|1)-Centroid Problem in the Plane with Distance Constraints ⋮ Rearranging a sequence of points onto a line ⋮ On the planar piecewise quadratic 1-center problem ⋮ LOCATING AN OBNOXIOUS LINE AMONG PLANAR OBJECTS ⋮ Computing the smallest k-enclosing circle and related problems ⋮ Can we compute the similarity between surfaces? ⋮ Distance-constrained multifacility minimax location problems on tree networks ⋮ LABELING POINTS WITH RECTANGLES OF VARIOUS SHAPES ⋮ Efficient piecewise-linear function approximation using the uniform metric ⋮ L-infinity interdistance selection by parametric search ⋮ An efficient algorithm for the proximity connected two center problem ⋮ Parametric search made practical ⋮ Algorithms on minimizing the maximum sensor movement for barrier coverage of a linear domain ⋮ Selecting distances in arrangements of hyperplanes spanned by points. ⋮ Revisiting \(k\)-sum optimization ⋮ Computing the Fréchet distance between piecewise smooth curves ⋮ The multi-service center problem ⋮ Linear-time algorithms for parametric minimum spanning tree problems on planar graphs ⋮ Fréchet distance with speed limits ⋮ Constant work-space algorithms for facility location problems ⋮ Geometric p-Center Problems with Centers Constrained to Two Lines ⋮ New Upper Bounds on Continuous Tree Edge-Partition Problem ⋮ The two-center problem of uncertain points on a real line ⋮ Some variations on constrained minimum enclosing circle problem ⋮ Improved algorithms for several network location problems with equality measures. ⋮ Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\) ⋮ Link distance and shortest path problems in the plane ⋮ Backup 2-center on interval graphs ⋮ Parallel selection ⋮ Partitioning arrangements of lines. I: An efficient deterministic algorithm ⋮ Construction of \(\epsilon\)-nets ⋮ The complexity of hyperplane depth in the plane ⋮ A note on searching line arrangements and applications ⋮ Exact algorithms for the bottleneck Steiner tree problem ⋮ An inverse model for the most uniform problem ⋮ Shortest path problems on a polyhedral surface ⋮ Computing the Fréchet distance between simple polygons ⋮ A generalized model of equality measures in network location problems ⋮ Efficient planar two-center algorithms ⋮ One-dimensional \(k\)-center on uncertain data ⋮ Finding effective ``Force targets for two-dimensional, multifinger frictional grips ⋮ Efficient algorithms for the one-dimensional \(k\)-center problem ⋮ Geometric pattern matching under Euclidean motion ⋮ A generalized approximation framework for fractional network flow and packing problems ⋮ Diameter, width, closest line pair, and parametric searching ⋮ Approximate parametric searching ⋮ Optimal slope selection via expanders ⋮ Computing the center of uncertain points on tree networks ⋮ Intersection of unit-balls and diameter of a point set in \(\mathbb R^3\). ⋮ Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches ⋮ Strongly polynomial-time approximation for a class of bicriteria problems. ⋮ Parametric search: three new applications ⋮ Efficient algorithms for the sum selection problem and \(k\) maximum sums problem ⋮ The constrained minimum weighted sum of job completion times problem ⋮ Computing the center region and its variants ⋮ ON ENUMERATING AND SELECTING DISTANCES ⋮ Linear-Time Fitting of a k-Step Function ⋮ A note on computing the center of uncertain data on the real line ⋮ Center location problems on tree graphs with subtree-shaped customers ⋮ Unnamed Item ⋮ Efficient parallel algorithms for r-dominating set and p-center problems on trees ⋮ Computing and minimizing the relative regret in combinatorial optimization with interval data ⋮ Output-sensitive results on convex hulls, extreme points, and related problems ⋮ Dynamic ham-sandwich cuts in the plane ⋮ A selectable sloppy heap ⋮ Improved complexity results for several multifacility location problems on trees ⋮ Linear-time algorithms for parametric minimum spanning tree problems on planar graphs ⋮ Continuous bottleneck tree partitioning problems ⋮ Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time ⋮ New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems ⋮ Optimal movement of mobile sensors for barrier coverage of a planar region ⋮ A combinatorial algorithm for the ordered 1-median problem on cactus graphs ⋮ Computing a geodesic two-center of points in a simple polygon ⋮ One-way and round-trip center location problems ⋮ An O(n log n)-Time Algorithm for the k-Center Problem in Trees ⋮ Locating two obnoxious facilities using the weighted maximin criterion ⋮ OPTIMAL FACILITY LOCATION UNDER VARIOUS DISTANCE FUNCTIONS ⋮ On the planar two-center problem and circular hulls ⋮ Locating service centers with precedence constraints ⋮ The centdian subtree on tree networks ⋮ Algorithmic results for ordered median problems ⋮ Optimal point movement for covering circular regions
This page was built for publication: Slowing down sorting networks to obtain faster sorting algorithms
