On the complexity of the surrogate dual of 0-1 programming

Research output: Contribution to journalArticle


It is shown that the surrogate dual of a 0-1 programming problem can be solved by 0(m3) knapsack calls, if m denotes the number of constraints.

Original languageEnglish (US)
Pages (from-to)A145-A153
JournalZeitschrift für Operations Research
Issue number3
StatePublished - May 1986

All Science Journal Classification (ASJC) codes

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


  • 0-1 programming
  • complexity
  • ellipsoid algorithm
  • surrogate constraints
  • surrogate dual

Fingerprint Dive into the research topics of 'On the complexity of the surrogate dual of 0-1 programming'. Together they form a unique fingerprint.

  • Cite this