3 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…
cs.DS2025
Efficient Branch-and-Bound for Submodular Function Maximization under Knapsack Constraint
Yimin Hao, Yi Zhou, Chao Xu +1
The submodular knapsack problem (SKP), which seeks to maximize a submodular set function by selecting a subset of elements within a given budget, is an important discrete optimizat…