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

Alexander Grigoriev; Joris Van De Klundert

doi:10.1016/j.orl.2011.04.006

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 journal › Article › peer-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 language	English
Pages (from-to)	252-254
Number of pages	3
Journal	Operations Research Letters
Volume	39
Issue number	4
DOIs	https://doi.org/10.1016/j.orl.2011.04.006
State	Published - Jul 2011
Externally published	Yes

Keywords

Approximation algorithm
Integer programming
Integrality gap
Preventive maintenance
Scheduling

Access to Document

10.1016/j.orl.2011.04.006

Cite this

@article{521256bf17964ec79c3dca5bafb7ff24,

title = "A note on the integrality gap of an ILP formulation for the periodic maintenance problem",

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.",

keywords = "Approximation algorithm, Integer programming, Integrality gap, Preventive maintenance, Scheduling",

author = "Alexander Grigoriev and \{Van De Klundert\}, Joris",

year = "2011",

month = jul,

doi = "10.1016/j.orl.2011.04.006",

language = "English",

volume = "39",

pages = "252--254",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "4",

}

TY - JOUR

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

AU - Grigoriev, Alexander

AU - Van De Klundert, Joris

PY - 2011/7

Y1 - 2011/7

N2 - 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.

AB - 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.

KW - Approximation algorithm

KW - Integer programming

KW - Integrality gap

KW - Preventive maintenance

KW - Scheduling

UR - https://www.scopus.com/pages/publications/79960836824

U2 - 10.1016/j.orl.2011.04.006

DO - 10.1016/j.orl.2011.04.006

M3 - Article

AN - SCOPUS:79960836824

SN - 0167-6377

VL - 39

SP - 252

EP - 254

JO - Operations Research Letters

JF - Operations Research Letters

IS - 4

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this