A note on the integrality gap of an ILP formulation for the periodic maintenance problem

Alexander Grigoriev, Joris Van De Klundert

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We address the integrality gap of the integer linear program introduced by Grigoriev et al. (2006) [3] for the periodic maintenance problem. We prove that the integrality gap of this program is bounded by a constant.

Original languageEnglish
Pages (from-to)252-254
Number of pages3
JournalOperations Research Letters
Volume39
Issue number4
DOIs
StatePublished - Jul 2011
Externally publishedYes

Keywords

  • Approximation algorithm
  • Integer programming
  • Integrality gap
  • Preventive maintenance
  • Scheduling

Fingerprint

Dive into the research topics of 'A note on the integrality gap of an ILP formulation for the periodic maintenance problem'. Together they form a unique fingerprint.

Cite this