Integrality gaps for colorful matchings |
| |
Institution: | 1. Department of Mathematics, Butler University, Indianapolis, IN 46208, United States;2. Department of Mathematics, University of Iowa, Iowa City, IA 52242, United States;3. Department of Mathematics, Iowa State University, 396 Carver Hall, Ames, IA 50011, United States |
| |
Abstract: | We study the integrality gap of the natural linear programming relaxation for the Bounded Color Matching (BCM) problem. We provide several families of instances and establish lower bounds on their integrality gaps and we study how the Sherali–Adams “lift-and-project” technique behaves on these instances. We complement these results by showing that if we exclude certain simple sub-structures from our input graphs, then the integrality gap of the natural linear formulation strictly improves. To prove this, we adapt for our purposes the results of Füredi (1981). We further leverage this to show upper bounds on the performance of the Sherali–Adams hierarchy when applied to the natural LP relaxation of the BCM problem. |
| |
Keywords: | Linear programming Lift and project Sherali-Adams Colorful matchings Integrality gap |
本文献已被 ScienceDirect 等数据库收录! |
|