4 papers
cs.LG2020
A Note on Optimizing the Ratio of Monotone Supermodular Functions
Wenxin Li
We show that for the problem of minimizing (or maximizing) the ratio of two supermodular functions, no bounded approximation ratio can be achieved via polynomial number of queries,…
cs.PF2019
On the Asymptotic Optimality of Work-Conserving Disciplines in Completion Time Minimization
Wenxin Li
In this paper, we prove that under mild stochastic assumptions, work-conserving disciplines are asymptotic optimal for minimizing total completion time. As a byproduct of our analy…
cs.DS2019
A Faster FPTAS for Knapsack Problem With Cardinality Constraint
Wenxin Li, Joohyun Lee
We study the -item knapsack problem (i.e., -dimensional KP), which is a generalization of the famous 0-1 knapsack problem (i.e., -dimensional KP) in which an upper bound…
cs.DS2018
Nearly Linear Time Deterministic Algorithms for Submodular Maximization Under Knapsack Constraint and Beyond
Wenxin Li
In this work, we study the classic submodular maximization problem under knapsack constraints and beyond. We first present an -approximate algorithm for single…