2 citations · 6 across the 5 of their papers we have counts for
5 papers
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,…
Submodular Maximization in Clean Linear Time
Wenxin Li, Moran Feldman, Ehsan Kazemi +1
In this paper, we provide the first deterministic algorithm that achieves the tight approximation guarantee for submodular maximization under a cardinality (size) constrain…
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…
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…
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…