Search

Your search keyword '"Du, Donglei"' showing total 545 results
Start Over Author "Du, Donglei"

Refine your results

more »

more »

more »

more »
545 results on '"Du, Donglei"'

2. Streaming Algorithms for the $k$-Submodular Cover Problem

Author

Wang, Wenqi, Gutin, Gregory, Mao, Yaping, Du, Donglei, and Zhang, Xiaoyan

Subjects
Computer Science - Data Structures and Algorithms
Abstract

Given a natural number $k\ge 2$, we consider the $k$-submodular cover problem ($k$-SC). The objective is to find a minimum cost subset of a ground set $\mathcal{X}$ subject to the value of a $k$-submodular utility function being at least a certain predetermined value $\tau$. For this problem, we design a bicriteria algorithm with a cost at most $O(1/\epsilon)$ times the optimal value, while the utility is at least $(1-\epsilon)\tau/r$, where $r$ depends on the monotonicity of $g$.

Published
2023

3. Continuous Non-monotone DR-submodular Maximization with Down-closed Convex Constraint

Author

Chen, Shengminjie, Du, Donglei, Yang, Wenguo, Xu, Dachuan, and Gao, Suixiang

Subjects
Computer Science - Data Structures and Algorithms, Mathematics - Optimization and Control
Abstract

We investigate the continuous non-monotone DR-submodular maximization problem subject to a down-closed convex solvable constraint. Our first contribution is to construct an example to demonstrate that (first-order) stationary points can have arbitrarily bad approximation ratios, and they are usually on the boundary of the feasible domain. These findings are in contrast with the monotone case where any stationary point yields a $1/2$-approximation (Hassani et al. (2017)). Moreover, this example offers insights on how to design improved algorithms by avoiding bad stationary points, such as the restricted continuous local search algorithm (Chekuri et al. (2014)) and the aided measured continuous greedy (Buchbinder and Feldman (2019)). However, the analyses in the last two algorithms only work for the discrete domain because both need to invoke the inequality that the multilinear extension of any submodular set function is bounded from below by its Lovasz extension. Our second contribution, therefore, is to remove this restriction and show that both algorithms can be extended to the continuous domain while retaining the same approximation ratios, and hence offering improved approximation ratios over those in Bian et al. (2017a). for the same problem. At last, we also include numerical experiments to demonstrate our algorithms on problems arising from machine learning and artificial intelligence.

Published
2023

7. A Distributed Approximation Algorithm for the Total Dominating Set Problem

Author

Wang, Limin, Zhang, Zhao, Du, Donglei, Mao, Yaping, Zhang, Xiaoyan, Goos, Gerhard, Series Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Ghosh, Smita, editor, and Zhang, Zhao, editor

Published
2024
Full Text
View/download PDF

9. Lyapunov function approach for approximation algorithm design and analysis: with applications in submodular maximization

Author

Du, Donglei

Subjects
Mathematics - Optimization and Control, Computer Science - Artificial Intelligence, Computer Science - Data Structures and Algorithms, Computer Science - Machine Learning
Abstract

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 and outputs a continuous-time approximation algorithm with a provable approximation ratio. The second phase then converts this continuous-time algorithm to a discrete-time algorithm with almost the same approximation ratio along with provable time complexity. One distinctive feature of our framework is that we only need to know the parametric form of the Lyapunov function whose complete specification will not be decided until the end of the first phase by maximizing the approximation ratio of the continuous-time algorithm. Some immediate benefits of the Lyapunov function approach include: (i) unifying many existing algorithms; (ii) providing a guideline to design and analyze new algorithms; and (iii) offering new perspectives to potentially improve existing algorithms. We use various submodular maximization problems as running examples to illustrate our framework.

Published
2022

10. On the Population Monotonicity of Independent Set Games

Author

Wang, Libing, Xiao, Han, Du, Donglei, and Xu, Dachuan

Subjects
Computer Science - Computer Science and Game Theory, Computer Science - Discrete Mathematics, 05C57, 91A12, 91A43, 91A46
Abstract

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 rule specifying how to share the profit of each coalition among its participants such that every participant is better off when the coalition expands. In this paper, we provide a necessary and sufficient characterization for population monotonic allocation schemes in independent set games. Moreover, our characterization can be verified efficiently.

Published
2022
Full Text
View/download PDF

11. An improved approximation algorithm for maximizing a DR-submodular function over a convex set

Author

Du, Donglei, Liu, Zhicheng, Wu, Chenchen, Xu, Dachuan, and Zhou, Yang

Subjects
Computer Science - Data Structures and Algorithms, 68W25, E.5.3
Abstract

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 it is highly desirable to design efficient approximation algorithms under this general setting where neither the objective function is monotonic nor the feasible set is down-closed, our main contribution is to present a 0.25-approximation Frank-Wolfe type of algorithm with a sub-exponential time-complexity under the value oracle model., Comment: 8 Pages

Published
2022

17. Approximation algorithms for general cluster routing problem

Author

Zhang, Xiaoyan, Du, Donglei, Gutin, Gregory, Ming, Qiaoxia, and Sun, Jian

Subjects
Computer Science - Data Structures and Algorithms
Abstract

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 study constant approximation algorithms for some variations of the general cluster routing problem. In this problem, we are given an edge-weighted complete undirected graph $G=(V,E,c),$ whose vertex set is partitioned into clusters $C_{1},\dots ,C_{k}.$ We are also given a subset $V'$ of $V$ and a subset $E'$ of $E.$ The weight function $c$ satisfies the triangle inequality. The goal is to find a minimum cost walk $T$ that visits each vertex in $V'$ only once, traverses every edge in $E'$ at least once and for every $i\in [k]$ all vertices of $C_i$ are traversed consecutively., Comment: In COCOON 2020

Published
2020

18. Two-Stage Submodular Maximization Under Knapsack and Matroid Constraints

Author

Liu, Zhicheng, Jin, Jing, Du, Donglei, Zhang, Xiaoyan, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Du, Ding-Zhu, editor, Du, Donglei, editor, Wu, Chenchen, editor, and Xu, Dachuan, editor

Published
2022
Full Text
View/download PDF

26. Two-Stage BP Maximization Under p-matroid Constraint

Author

Chang, Hong, Liu, Zhicheng, Du, Donglei, Zhang, Xiaoyan, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Zhang, Yong, editor, Miao, Dongjing, editor, and Möhring, Rolf, editor

Published
2022
Full Text
View/download PDF

27. A Stochastic Non-monotone DR-Submodular Maximization Problem over a Convex Set

Author

Lian, Yuefang, Xu, Dachuan, Du, Donglei, Zhou, Yang, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Zhang, Yong, editor, Miao, Dongjing, editor, and Möhring, Rolf, editor

Published
2022
Full Text
View/download PDF

28. Distributed Fair k-Center Clustering Problems with Outliers

Author

Yuan, Fan, Diao, Luhong, Du, Donglei, Liu, Lei, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Shen, Hong, editor, Sang, Yingpeng, editor, Zhang, Yong, editor, Xiao, Nong, editor, Arabnia, Hamid R., editor, Fox, Geoffrey, editor, Gupta, Ajay, editor, and Malek, Manu, editor

Published
2022
Full Text
View/download PDF

29. A Linear-Time Streaming Algorithm for Cardinality-Constrained Maximizing Monotone Non-submodular Set Functions

Author

Cui, Min, Du, Donglei, Gai, Ling, Yang, Ruiqi, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Du, Ding-Zhu, editor, Du, Donglei, editor, Wu, Chenchen, editor, and Xu, Dachuan, editor

Published
2021
Full Text
View/download PDF

33. Improved Linear-Time Streaming Algorithms for Maximizing Monotone Cardinality-Constrained Set Functions.

Author

Cui, Min, Du, Donglei, Gai, Ling, and Yang, Ruiqi

Subjects
*DETERMINISTIC algorithms, *SET functions, *APPROXIMATION algorithms, *SOCIAL networks, *ALGORITHMS
Abstract

Many real-world applications arising from social networks, personalized recommendations, and others, require extracting a relatively small but broadly representative portion of massive data sets. Such problems can often be formulated as maximizing a monotone set function with cardinality constraints. In this paper, we consider a streaming model where elements arrive quickly over time, and create an effective, and low-memory algorithm. First, we provide the first single-pass linear-time algorithm, which is a a deterministic algorithm, achieves an approximation ratio of [ γ 4 a (1 + γ + γ 2 + γ 3) − ] for any ≥ 0 with a query complexity of ⌈ n / a ⌉ + a and a memory complexity of O (a k log (k) log (1 /)) , where a is a positive integer and γ is the submodularity ratio. However, the algorithm may produce less-than-ideal results. Our next result is to describe a multi-streaming algorithm, which is the first deterministic algorithm to attain an approximation ratio of 1 − e − γ − with linear query complexity. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

34. Improved Algorithms for Non-submodular Function Maximization Problem

Author

Liu, Zhicheng, Chang, Hong, Du, Donglei, Zhang, Xiaoyan, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Wu, Weili, editor, and Du, Hongwei, editor

Published
2021
Full Text
View/download PDF

35. Approximation Algorithm for Maximizing Nonnegative Weakly Monotonic Set Functions

Author

Cui, Min, Du, Donglei, Xu, Dachuan, Yang, Ruiqi, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Mohaisen, David, editor, and Jin, Ruoming, editor

Published
2021
Full Text
View/download PDF

36. Approximation Algorithms for the Lower Bounded Correlation Clustering Problem

Author

Ji, Sai, Dong, Yinhong, Du, Donglei, Xu, Dachuan, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Mohaisen, David, editor, and Jin, Ruoming, editor

Published
2021
Full Text
View/download PDF

37. Differentially Private Submodular Maximization over Integer Lattice

Author

Hu, Jiaming, Xu, Dachuan, Du, Donglei, Miao, Cuixia, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Mohaisen, David, editor, and Jin, Ruoming, editor

Published
2021
Full Text
View/download PDF

39. A Primal-Dual Algorithm for Euclidean k-Means Problem with Penalties

Author

Ren, Chunying, Xu, Dachuan, Du, Donglei, Li, Min, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Chen, Jianer, editor, Feng, Qilong, editor, and Xu, Jinhui, editor

Published
2020
Full Text
View/download PDF

40. Two-Stage Submodular Maximization Problem Beyond Non-negative and Monotone

Author

Liu, Zhicheng, Chang, Hong, Ma, Ran, Du, Donglei, Zhang, Xiaoyan, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Chen, Jianer, editor, Feng, Qilong, editor, and Xu, Jinhui, editor

Published
2020
Full Text
View/download PDF

41. Approximation Algorithm for the Balanced 2-correlation Clustering Problem on Well-Proportional Graphs

Author

Ji, Sai, Xu, Dachuan, Du, Donglei, Gai, Ling, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Zhang, Zhao, editor, Li, Wei, editor, and Du, Ding-Zhu, editor

Published
2020
Full Text
View/download PDF

42. Approximation Algorithm for Stochastic Set Cover Problem

Author

Sheng, Haiyun, Du, Donglei, Sun, Yuefang, Sun, Jian, Zhang, Xiaoyan, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Zhang, Zhao, editor, Li, Wei, editor, and Du, Ding-Zhu, editor

Published
2020
Full Text
View/download PDF

43. Online Bicriteria Algorithms to Balance Coverage and Cost in Team Formation

Author

Wang, Yijing, Xu, Dachuan, Du, Donglei, Ma, Ran, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Zhang, Zhao, editor, Li, Wei, editor, and Du, Ding-Zhu, editor

Published
2020
Full Text
View/download PDF

44. Online BP Functions Maximization

Author

Chen, Ling, Liu, Zhicheng, Chang, Hong, Du, Donglei, Zhang, Xiaoyan, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Zhang, Zhao, editor, Li, Wei, editor, and Du, Ding-Zhu, editor

Published
2020
Full Text
View/download PDF

45. The Spherical k-means++ Algorithm via Local Search

Author

Tian, Xiaoyun, Xu, Dachuan, Du, Donglei, Gai, Ling, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Zhang, Zhao, editor, Li, Wei, editor, and Du, Ding-Zhu, editor

Published
2020
Full Text
View/download PDF

50. An Overview of Submodular Optimization: Single- and Multi-Objectives

Author

Du, Donglei, Han, Qiaoming, Wu, Chenchen, Pardalos, Panos M., Managing Editor, Du, Ding-Zhu, Honorary Editor, Birge, John, Advisory Editor, Butenko, Sergiy, Advisory Editor, Giannessi, Franco, Advisory Editor, Rebennack, Steffen, Advisory Editor, Terlaky, Tamás, Advisory Editor, Ye, Yinyu, Advisory Editor, and Zhang, Zhao, editor

Published
2019
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results