@inproceedings{2011294a884a4985b75befaeb0e0c57b,
title = "A full description of polytopes related to the index of the lowest nonzero row of an assignment matrix",
abstract = "Consider a \{0, 1\} assignment matrix where each column contains exactly one coefficient equal to 1 and let h be the index of the lowest row that is not identically equal to the zero row.We give a full description of the convex hull of all feasible assignments appended with the extra parameter h. This polytope and some of its variants naturally appear in the context of several combinatorial optimization problems including frequency assignment, job scheduling, graph orientation, maximum clique, etc. We also show that the underlying separation problems are solvable in polynomial time and thus optimization over those polytopes can be done in polynomial time.",
author = "Walid Ben-Ameur and Antoine Glorieux and Jos{\'e} Neto",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 4th International Symposium on Combinatorial Optimization, ISCO 2016 ; Conference date: 16-05-2016 Through 18-05-2016",
year = "2016",
month = jan,
day = "1",
doi = "10.1007/978-3-319-45587-7\_2",
language = "English",
isbn = "9783319455860",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "13--25",
editor = "Satoru Fujishige and Mahjoub, \{Ridha A.\} and Raffaele Cerulli",
booktitle = "Combinatorial Optimization - 4th International Symposium, ISCO 2016, Revised Selected Papers",
}