A linear time randomizing algorithm for searching ranked functions

DOI10.1007/BF01840350zbMath0642.68121OpenAlexW2044668258MaRDI QIDQ1101237

Eitan Zemel

Publication date: 1987

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01840350

zbMATH Keywords

searchingparametric knapsack problemcost effective resource allocationlinear time randomizing algorithmicranked function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Sensitivity, stability, parametric optimization (90C31) Algorithms in computer science (68W99)

Related Items

An approximate binary search algorithm for the multiple-choice knapsack problem, A Fast Approximation Algorithm For The Subset-Sum Problem, New scaling algorithms for the assignment and minimum mean cycle problems, Approximating the minimum cycle mean, A linear-time algorithm for solving continuous maximin knapsack problems, Mass change detection based on reduced measurements, An algorithm for fractional assignment problems, A new saling algorithm for the maximum mean cut problem, Approximate binary search algorithms for mean cuts and cycles

Cites Work

• Unnamed Item
• The Weighted Euclidean 1-Center Problem
• An O(nlogn) randomizing algorithm for the weighted euclidean 1-center problem
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms