9 citations · 22 across the 13 of their papers we have counts for
14 papers
Continuous Non-monotone DR-submodular Maximization with Down-closed Convex Constraint
Shengminjie Chen, Donglei Du, Wenguo Yang +2
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…
-approximate pure Nash equilibria algorithms for weighted congestion games and their runtimes
Ren Chunying, Wu Zijun, Xu Dachuan +1
This paper concerns computing approximate pure Nash equilibria in weighted congestion games, which has been shown to be PLS-complete. With the help of -game and approximate…
Parallel algorithms for maximizing one-sided -smooth function
Hongxiang Zhang, Yukun Cheng, Chenchen Wu +2
In this paper, we study the problem of maximizing a monotone normalized one-sided -smooth ( for short) function , subject to a convex polytope. This problem was first…
Maximizing Modular plus Non-monotone Submodular Functions
Xin Sun, Chenchen Wu, Dachuan Xu +1
The research problem in this work is the relaxation of maximizing non-negative submodular plus modular with the entire real number domain as its value range over a family of down-c…
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…
Approximate the individually fair k-center with outliers
Lu Han, Dachuan Xu, Yicheng Xu +1
In this paper, we propose and investigate the individually fair -center with outliers (IFCO). In the IFCO, we are given an -sized vertex set in a metric space, as well…
Outliers Detection Is Not So Hard: Approximation Algorithms for Robust Clustering Problems Using Local Search Techniques
Yishui Wang, Rolf H. Möhring, Chenchen Wu +2
In this paper, we consider two types of robust models of the -median/-means problems: the outlier-version (-MedO/-MeaO) and the penalty-version (-MedP/-MeaP), in…
Eigenvalue-corrected Natural Gradient Based on a New Approximation
Kai-Xin Gao, Xiao-Lei Liu, Zheng-Hai Huang +5
Using second-order optimization methods for training deep neural networks (DNNs) has attracted many researchers. A recently proposed method, Eigenvalue-corrected Kronecker Factoriz…
A Trace-restricted Kronecker-Factored Approximation to Natural Gradient
Kai-Xin Gao, Xiao-Lei Liu, Zheng-Hai Huang +4
Second-order optimization methods have the ability to accelerate convergence by modifying the gradient through the curvature matrix. There have been many attempts to use second-ord…
A convergence analysis of the price of anarchy in atomic congestion games
Zijun Wu, Rolf H. Moehring, Chunying Ren +1
This paper provides a comprehensive convergence analysis of the PoA of both pure and mixed Nash equilibria in atomic congestion games with unsplittable demands.
Selfishness need not be bad: a general proof
Zijun Wu, Rolf H. Möhring, Dachuan Xu
This article studies the user behavior in non-atomic congestion games. We consider non-atomic congestion games with continuous and non-decreasing functions and investigate the limi…
Selfishness need not be bad
Wu Zijun, Moehring Rolf H., Chen Yanyan +1
We investigate the price of anarchy (PoA) in non-atomic congestion games when the total demand gets very large. First results in this direction have recently been obtained by \…
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…