Matroid Intersections, Polymatroid Inequalities, and Related Problems
Matroid Intersections, Polymatroid Inequalities, and Related Problems
复制标题
拟阵交集、多拟阵不等式及相关问题
DOI：
10.1007/3-540-45687-2_11
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
L. Khachiyan
中科院分区：
文献类型：
--
作者：
E. Boros;Khaled M. Elbassioni;V. Gurvich;L. Khachiyan
给定mmatroidsM 1，.，在公共基集V上，证明了V的所有极大子集，在拟阵中是独立的，都可以在拟多项式时间内生成。更一般地，给定一个多拟阵不等式组f1（X）≥t1，.，fm（X）≥ tm且拟多项式有界右sidest 1，...，tm，系统的所有最小可行解X ∈ V都可以在增量拟多项式时间内生成.我们证明这些结果是基于一个组合不等式的多拟阵函数，这可能是独立的利益。精确地说，对于多拟阵函数f和整数阈值dt ≥ 1，设α = α（f，t）表示满足f（X）<t的极大集X <$V的个数，设β = β（ft）表示满足f（X）≥t的极小集X <$V的个数，设n =| V|.证明了α ≤ maxn，β（logt）/c，其中c =c（n，β）是方程2c（nc/logβ - 1）= 1的唯一正根.特别地，我们的界意味着α ≤（nβ）logt。给出了n，α，β为任意大且α = β（1-01））logt/c的多拟阵函数的例子.
GivenmmatroidsM1,...,Mmon the common ground setV, it is shown that all maximal subsets ofV, independent in themmatroids, can be generated in quasi-polynomial time. More generally, given a system of polymatroid inequalitiesf1(X) ≥t1,...,fm(X) ≥tmwith quasi-polynomially bounded right hand sidest1,...,tm, all minimal feasible solutionsX⊆Vto the system can be generated in incremental quasi-polynomial time. Our proof of these results is based on a combinatorial inequality for polymatroid functions which may be of independent interest. Precisely, for a polymatroid functionfand an integer thresholdt≥ 1, let α = α(f,t) denote the number of maximal setsX⊆Vsatisfyingf(X) <t, let β = β(ft) be the number of minimal setsX⊆Vfor whichf(X) ≥t, and letn= |V|. We show that α ≤ maxn,β(logt)/c, wherec=c(n,β) is the unique positive root of the equation 2c(nc/logβ - 1) = 1. In particular, our bound implies that α ≤ (nβ)logt. We also give examples of polymatroid functions with arbitrarily largetn,α and β for which α = β(1-01))logt/c.
单调对偶化及相关主题
DOI：
--
发表时间：
2020
期刊：
影响因子：
--
作者：
112.Yuta Halvorson;Naoki Hasimoto;Kazuhisa Makino
通讯作者：
Kazuhisa Makino