The effectiveness of finite improvement algorithms for finding global optima

Sheldon H. Jacobson, Daniel Solow

Research output: Contribution to journalArticlepeer-review


This paper investigates the effectiveness of using finite improvement algorithms for solving decision, search, and optimization problems. Finite improvement algorithms operate in a finite number of iterations, each taking a polynomial amount of work, where strict improvement is required from iteration to iteration. The hardware, software, and way of measuring complexity found in the polynomial setting are modified to identify the concept of repetition and define the new classes of decision problems, FI and NFI. A first NFI-complete problem is given using the idea of FI-transformations. Results relating these new classes to P, NP, and NP-complete are given. It is shown that if an optimization problem in a new class PGS is NP-hard, then NP=co-NP. Two PGS problems are given for which no polynomial algorithms are known to exist.

Original languageEnglish (US)
Pages (from-to)257-272
Number of pages16
JournalZOR Zeitschrift für Operations Research Methods and Models of Operations Research
Issue number3
StatePublished - Oct 1993
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Management Science and Operations Research


Dive into the research topics of 'The effectiveness of finite improvement algorithms for finding global optima'. Together they form a unique fingerprint.

Cite this