A characterization of odd-hole inequalities related to Latin squares

dc.contributor.author	Μάγος, Δημήτριος	el
dc.contributor.author	Μούρτος, Ιωάννης	el
dc.date.accessioned	2015-06-06T18:01:57Z
dc.date.available	2015-06-06T18:01:57Z
dc.date.issued	2015-06-06
dc.identifier.uri	http://hdl.handle.net/11400/15354
dc.rights	Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ηνωμένες Πολιτείες	*
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/3.0/us/	*
dc.source	http://www.tandfonline.com	en
dc.subject	Planar assignment
dc.subject	Polyhedral combinatorics
dc.subject	Επίπεδη ανάθεση
dc.subject	Πολυεδρική συνδυαστική
dc.title	A characterization of odd-hole inequalities related to Latin squares	en
heal.type	journalArticle
heal.classification	Technology
heal.classification	Computer programming
heal.classification	Τεχνολογία
heal.classification	Προγραμματισμός
heal.classificationURI	http://id.loc.gov/authorities/subjects/sh85133147
heal.classificationURI	http://skos.um.es/unescothes/C00749
heal.classificationURI	N/A-Τεχνολογία
heal.classificationURI	N/A-Προγραμματισμός
heal.identifier.secondary	DOI: 10.1080/02331934.2011.611510
heal.language	en
heal.access	campus
heal.publicationDate	2013
heal.bibliographicCitation	Magos, D. and Mourtos, I. (2013) A characterization of odd-hole inequalities related to Latin squares. "Optimization", 62 (9), p.1169-1201	el
heal.abstract	A Latin square is an n × n matrix where in each row and each column every number between 1 and n appears exactly once. A Latin square can be described by a binary vector with n 3 components, and the Latin square polytope (P n;I) is the convex hull of such binary vectors. We study the facial structure of P n;I by examining valid inequalities induced by the odd holes of the associated intersection graph. In particular, we define the concept of the lifting set of an odd hole, present an efficient algorithm for identifying it and derive tight bounds on the left-hand side coefficients of an induced odd-hole inequality. In this way, we are able to characterize the class of odd holes that yield maximal inequalities without lifting and show that, for sufficiently large n, they are facet-defining for P n;I. This outcome unifies and generalizes previous results, with respect to the classes of facets for P n;I, presented in the literature. Computational experience regarding the use of (lifted) odd-hole inequalities as cutting planes is reported.	en
heal.journalName	Optimization	en
heal.journalType	peer-reviewed
heal.fullTextAvailability	true