Author

D. Du

3 papers indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Oct 2026

0.4633-Approximation for Online and Offline on-Monotone DR-Submodular Maximization

We obtain the approximation coefficient $\alpha_0=54440750000/117486474169>0.463378$ for maximizing nonnegative, non-monotone DR-submodular functions over compact convex down-closed subsets of the unit cube, with queries allowed throughout the cube. This improves the previous best coefficient, $4/9$. A coordinatewise m...

Vaneet Aggarwal, D. Du · 0 citations

Preprint Oct 2026

A 0.4584-approximation for DR-submodular maximization over down-closed convex sets

We obtain a $0.4584$-approximation for nonnegative, non-monotone, $L$-smooth DR-submodular maximization over compact convex down-closed subsets of the unit cube, improving the $4/9\approx0.4444$ ratio of Aggarwal's projection-based algorithm~\cite{aggarwal2026geometry}. A recovery map combining exponential and linear-f...

D. Du · 0 citations

Preprint Oct 2026

Concave Roofs and Downward Recovery for DR-Submodular Polynomial Maximization

Global monotonicity and concave-cardinality structure give stronger guarantees for multilinear local-function sums, with no recovery beyond the identity map, and standard matroid rounding transfers the multilinear guarantees without loss.

D. Du · 1 citation