APPROXIMATE PARAMETRIC SEARCHING

Authors
TOLEDO S
Citation
S. Toledo, APPROXIMATE PARAMETRIC SEARCHING, Information processing letters, 47(1), 1993, pp. 1-4
Citations number
4
Categorie Soggetti
Information Science & Library Science","Computer Applications & Cybernetics
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
47
Issue
1
Year of publication
1993
Pages
1 - 4
Database
ISI
SICI code
0020-0190(1993)47:1<1:APS>2.0.ZU;2-G
Abstract
We present a technique for approximately maximizing a class of concave functions whose evaluation is NP complete. We assume that there is a polynomial-time approximation algorithm for evaluating a function and use it to design a polynomial-time algorithm for approximating the max imum of the function. Finding the exact maximum is NP complete. Our te chnique is based on Megiddo's parametric searching technique.