Home > Research > Publications & Outputs > On the membership problem for the {0, 1/2}-closure

Research

Electronic data

Links

Text available via DOI:

Keywords

View graph of relations

On the membership problem for the {0, 1/2}-closure

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

On the membership problem for the {0, 1/2}-closure. / Letchford, A N; Pokutta, Sebastian; Schulz, AS.
In: Operations Research Letters, Vol. 39, No. 5, 09.2011, p. 301-304.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Letchford, AN, Pokutta, S & Schulz, AS 2011, 'On the membership problem for the {0, 1/2}-closure', Operations Research Letters, vol. 39, no. 5, pp. 301-304. https://doi.org/10.1016/j.orl.2011.07.003

APA

Letchford, A. N., Pokutta, S., & Schulz, AS. (2011). On the membership problem for the {0, 1/2}-closure. Operations Research Letters, 39(5), 301-304. https://doi.org/10.1016/j.orl.2011.07.003

Vancouver

Letchford AN, Pokutta S, Schulz AS. On the membership problem for the {0, 1/2}-closure. Operations Research Letters. 2011 Sept;39(5):301-304. Epub 2011 Jul 29. doi: 10.1016/j.orl.2011.07.003

Author

Letchford, A N ; Pokutta, Sebastian ; Schulz, AS. / On the membership problem for the {0, 1/2}-closure. In: Operations Research Letters. 2011 ; Vol. 39, No. 5. pp. 301-304.

Bibtex

@article{35b50cd828664c83ba375da2e5ee49d2,
title = "On the membership problem for the {0, 1/2}-closure",
abstract = "In integer programming, {0,1/2}-cuts are Gomory–Chv{\'a}tal cuts that can be derived from the original linear system by using coefficients of value 0 or 1/2 only. The separation problem for {0,1/2}-cuts is strongly NP-hard. We show that separation remains strongly NP-hard, even when all integer variables are binary.",
keywords = "Integer programming, Gomory–Chv{\'a}tal cuts , {0,1/2}-cuts, Separation , Computational complexity",
author = "Letchford, {A N} and Sebastian Pokutta and AS Schulz",
year = "2011",
month = sep,
doi = "10.1016/j.orl.2011.07.003",
language = "English",
volume = "39",
pages = "301--304",
journal = "Operations Research Letters",
issn = "0167-6377",
publisher = "Elsevier",
number = "5",

}

RIS

TY - JOUR

T1 - On the membership problem for the {0, 1/2}-closure

AU - Letchford, A N

AU - Pokutta, Sebastian

AU - Schulz, AS

PY - 2011/9

Y1 - 2011/9

N2 - In integer programming, {0,1/2}-cuts are Gomory–Chvátal cuts that can be derived from the original linear system by using coefficients of value 0 or 1/2 only. The separation problem for {0,1/2}-cuts is strongly NP-hard. We show that separation remains strongly NP-hard, even when all integer variables are binary.

AB - In integer programming, {0,1/2}-cuts are Gomory–Chvátal cuts that can be derived from the original linear system by using coefficients of value 0 or 1/2 only. The separation problem for {0,1/2}-cuts is strongly NP-hard. We show that separation remains strongly NP-hard, even when all integer variables are binary.

KW - Integer programming

KW - Gomory–Chvátal cuts

KW - {0,1/2}-cuts

KW - Separation

KW - Computational complexity

U2 - 10.1016/j.orl.2011.07.003

DO - 10.1016/j.orl.2011.07.003

M3 - Journal article

VL - 39

SP - 301

EP - 304

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 5

ER -