Optimal fractional matchings and covers in infinite hypergraphs: Existence and duality |
| |
Authors: | Ron Aharoni Ron Holzman |
| |
Institution: | (1) Department of Mathematics, Technion-Israel Institute of Technology, 32000 Haifa, Israel;(2) Department of Applied Mathematics and Computer Science, The Weizmann Institute of Science, 76100 Rehovot, Israel |
| |
Abstract: | We study fractional matchings and covers in infinite hypergraphs, paying particular attention to the following questions: Do fractional matchings (resp. covers) of maximal (resp. minimal) size exist? Is there equality between the supremum of the sizes of fractional matchings and the infimum of the sizes of fractional covers? (This is called weak duality.) Are there a fractional matching and a fractional cover that satisfy the complementary slackness conditions of linear programming? (This is called strong duality.) In general, the answers to all these questions are negative, but for certain classes of infinite hypergraphs (classified according to edge cardinalities and vertex degrees) we obtain positive results. We also consider the question of the existence of optimal fractional matchings and covers that assume rational values. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|