Approximate parametric searching

DOI10.1016/0020-0190(93)90149-4zbMATH Open0776.68062OpenAlexW2067862282MaRDI QIDQ685496FDOQ685496

Authors: Sivan Toledo 

Publication date: 26 November 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(93)90149-4

Recommendations

• scientific article; zbMATH DE number 1256706
• The complexity of approximating a nonlinear program
• scientific article; zbMATH DE number 1182930
• On nonlinear parametric search
• An approximation algorithm for a general class of parametric optimization problems

zbMATH Keywords

polynomial-time approximation algorithmmaximizing a class of concave functionsNP completeparametric searching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Cites Work

• Parallelism in Comparison Problems
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Slowing down sorting networks to obtain faster sorting algorithms

Cited In (7)

• A generalized approximation framework for fractional network flow and packing problems
• Optimization of partial search
• Weakly adaptive comparison searching
• An efficient, strongly polynomial, \(\varepsilon\)-approximation parametric optimization scheme
• On the complexity and approximability of budget-constrained minimum cost flows
• \(\varepsilon\)-approximation minimization of convex functions in fixed dimension
• Optimal parametric search on graphs of bounded tree-width

This page was built for publication: Approximate parametric searching

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