The constraint of difference and total dual integrality

dc.contributor.author	Μάγος, Δημήτριος	el
dc.date.accessioned	2015-06-05T19:11:30Z
dc.date.available	2015-06-05T19:11:30Z
dc.date.issued	2015-06-05
dc.identifier.uri	http://hdl.handle.net/11400/15194
dc.rights	Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ηνωμένες Πολιτείες	*
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/3.0/us/	*
dc.source	http://dl.acm.org	en
dc.subject	Discrete variables
dc.subject	Linear functions
dc.subject	Polytopes
dc.subject	Διακριτές μεταβλητές
dc.subject	Πολύτοπα
dc.subject	Γραμμικές λειτουργίες
dc.title	The constraint of difference and total dual integrality	en
heal.type	journalArticle
heal.classification	Computer science
heal.classification	Computer programming ( URL: http://skos.um.es/unescothes/C00749)
heal.classification	Πληροφορική
heal.classification	Προγραμματισμός
heal.classificationURI	http://skos.um.es/unescothes/C00750
heal.classificationURI	http://skos.um.es/unescothes/C00749
heal.classificationURI	N/A-Πληροφορική
heal.classificationURI	N/A-Προγραμματισμός
heal.identifier.secondary	DOI: 10.1145/2491845.2491847
heal.language	en
heal.access	campus
heal.publicationDate	2013
heal.bibliographicCitation	Magos, D. (2013) The constraint of difference and total dual integrality. "International Conference Proceeding Series", p.188-194	en
heal.abstract	One of the most important logic constraints is the constraint of difference. It is imposed on a set of discrete variables requiring that they receive pairwise distinct values. This construct, initially studied in the field of Artificial Intelligence (in particular, Constraint Programming), has numerous applications and important theoretical properties. In the current work, we show that the polytope associated with this constraint is a generalized polymatroid and thus totally dual integral. As a consequence the problem of optimizing a linear function when variables are restricted to take pairwise distinct values belongs to P. Furthermore, we prove that the above problem can be solved by the greedy algorithm in O(\|J\| · log\|J\|) steps where J denotes the set indexing the variables (to receive pairwise distinct values). We establish that the dual of the above problem can also be solved in the same number of steps.	en
heal.journalName	International Conference Proceeding Series	en
heal.journalType	peer-reviewed
heal.fullTextAvailability	true