3 citations · 10 across the 6 of their papers we have counts for
8 papers
A 0.4584-approximation for DR-submodular maximization over down-closed convex sets
Donglei Du
We obtain a -approximation for nonnegative, non-monotone, -smooth DR-submodular maximization over compact convex down-closed subsets of the unit cube, improving the $4/9…
Concave Roofs and Downward Recovery for DR-Submodular Polynomial Maximization
Donglei Du
We give approximation algorithms for $\max\{F(x):x\in\K\}$, where $\K$ is a nonempty compact down-closed convex subset of the unit cube and is a nonnegative diminishing-returns…
Lyapunov function approach for approximation algorithm design and analysis: with applications in submodular maximization
Donglei Du
We propose a two-phase systematical framework for approximation algorithm design and analysis via Lyapunov function. The first phase consists of using Lyapunov function as an input…
An improved approximation algorithm for maximizing a DR-submodular function over a convex set
Donglei Du, Zhicheng Liu, Chenchen Wu +2
Maximizing a DR-submodular function subject to a general convex set is an NP-hard problem arising from many applications in combinatorial optimization and machine learning. While i…
On the Population Monotonicity of Independent Set Games
Libing Wang, Han Xiao, Donglei Du +1
An independent set game is a cooperative game defined on graphs and dealing with profit-sharing in maximum independent set problems. A population monotonic allocation scheme is a r…
Approximation algorithms for general cluster routing problem
Xiaoyan Zhang, Donglei Du, Gregory Gutin +2
Graph routing problems have been investigated extensively in operations research, computer science and engineering due to their ubiquity and vast applications. In this paper, we st…
An improved approximation algorithm for k-median problem using a new factor-revealing LP
Chenchen Wu, Dachuan Xu, Donglei Du +1
The k-median problem is a well-known strongly NP-hard combinatorial optimization problem of both theoretical and practical significance. The previous best approximation ratio for t…
Copula-based Randomized Mechanisms for Truthful Scheduling on Two Unrelated Machines
Xujin Chen, Donglei Du, Luis F. Zuluaga
We design a Copula-based generic randomized truthful mechanism for scheduling on two unrelated machines with approximation ratio within , offering an improved up…