2 papers
cs.DS2026
Large-Scale Trade-Off Curve Computation for Incentive Allocation with Cardinality and Matroid Constraints
Yu Cong, Chao Xu, Yi Zhou
We consider a large-scale incentive allocation problem where the entire trade-off curve between budget and profit has to be maintained approximately at all times. The application o…
cs.DS2026
Derandomizing Karger's Contraction Algorithm for Matroids
Yu Cong, Chao Xu, Yajie Zhao
Karger's randomized contraction algorithm finds a minimum-weight cocircuit of a matroid whenever the cogirth-density ratio is bounded. We prove that the same hypothesis yields a de…