Relaxation of 3-partition instances

S.J.C. Joosten, H. Zantema

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

35 Downloads (Pure)

Abstract

The 3-partition problem admits a straightforward formulation as a 0-1 Integer Linear Program (ILP). We investigate problem instances for which the half-integer relaxation of the ILP is feasible, while the ILP is not. We prove that this only occurs on a set of at least 18 elements, and in case of 18 elements such an instance always contains an element of weight = 10. These bounds are sharp: we give all 14 instances consisting of 18 elements all having weight = 10. Our approach is based on analyzing an underlying graph structure.
Original languageEnglish
Title of host publication12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (Enschede, Netherlands, May 21-23, 2013)
EditorsK. Cornelissen, R. Hoeksma, J. Hurink, B. Manthey
Pages133-136
Publication statusPublished - 2013

Publication series

NameCTIT Workshop Proceedings Series
VolumeWP 13-01
ISSN (Print)1574-0846

Fingerprint

Dive into the research topics of 'Relaxation of 3-partition instances'. Together they form a unique fingerprint.

Cite this