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

Producción científica: Contribución a una revista › Artículo › revisión exhaustiva

1 Cita (Scopus)

Resumen

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.

Idioma original	Inglés
Páginas (desde-hasta)	252-254
Número de páginas	3
Publicación	Operations Research Letters
Volumen	39
N.º	4
DOI	https://doi.org/10.1016/j.orl.2011.04.006
Estado	Publicada - jul. 2011
Publicado de forma externa	Sí

Acceder al documento

10.1016/j.orl.2011.04.006

Citar esto

@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 - http://www.scopus.com/inward/record.url?scp=79960836824&partnerID=8YFLogxK

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

Resumen

Acceder al documento

Huella

Citar esto