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


Integral decomposition in polyhedra
Authors:Colin McDiarmid
Institution:(1) Wolfson College, Oxford, England
Abstract:We say that a polyhedronP satisfies weak integral decomposition if whenever an integral vector is the sum ofk vectors inP it is also the sum ofk integral vectors inP. This property is related to rounding results for packing and covering problems. We study the property and two related properties, and give results concerning integral polymatroids, totally unimodular matrices and network flows, pairs of strongly-base-orderable matroids, and branchings in directed graphs.
Keywords:Convex Polyhedra  Integral Decomposition  Packing and Covering  Polymatroids  Totally Unimodular Matrices  Network Flows  Strongly-base-orderable Matroids  Branchings
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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