首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号