Order preserving reductions and polynomial improving paths

Derek E. Armstrong, Sheldon H. Jacobson

Research output: Contribution to journalArticlepeer-review

Abstract

This paper shows that neighborhood transformations and data-independent order transformations preserve the length of improving paths and order of local optima of neighborhood functions. These results imply that finding effective neighborhood functions for Zero-One IP is at least as hard as finding effective neighborhood functions for any other NPO problem.

Original languageEnglish (US)
Pages (from-to)9-16
Number of pages8
JournalOperations Research Letters
Volume34
Issue number1
DOIs
StatePublished - Jan 2006

Keywords

  • Computational complexity
  • Discrete optimization
  • Neighborhood functions
  • Satisfiability

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Order preserving reductions and polynomial improving paths'. Together they form a unique fingerprint.

Cite this