Tightness of LP relaxations for almost balanced models

Adrian Weller, Mark Rowland, David Sontag

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We examine Boolean binary weighted constraint satisfaction problems and derive sufficient conditions for when certain linear programming (LP) relaxations are guaranteed to return an integer solution, in which case the solution is exact and we say that the relaxation is tight.

Original languageEnglish (US)
Title of host publicationPrinciples and Practice of Constraint Programming - 22nd International Conference, CP 2016, Proceedings
EditorsMichel Rueher
PublisherSpringer Verlag
Pages894-895
Number of pages2
ISBN (Print)9783319449524
StatePublished - 2016
Event22nd International Conference on Principles and Practice of Constraint Programming, CP 2016 - Toulouse, France
Duration: Sep 5 2016Sep 9 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9892 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other22nd International Conference on Principles and Practice of Constraint Programming, CP 2016
CountryFrance
CityToulouse
Period9/5/169/9/16

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Tightness of LP relaxations for almost balanced models'. Together they form a unique fingerprint.

Cite this