Author name cluster

Dachuan Xu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

23 papers

2 author rows

TCS Journal 2026 Journal Article

On competitive ratio for online uniform facility location problem in random-order model

Mengzhen Li
Runjie Miao
Chenchen Wu
Dachuan Xu

We study the online facility location problem, where clients arrive sequentially in a random order and must be assigned to an open facility immediately and irrevocably upon arrival. At the initial stage, the set of facilities is fully known. We present a 8-competitive online algorithm for the uniform facility cost case, providing the first competitive ratio result for this setting. Our algorithm reduces the competitive ratio by 75% compared to the previously known 33-competitive ratio for the nonuniform case. The analysis offers new theoretical insights into online algorithms for the nonuniform case and establishes a foundation for practical applications in decision-making contexts.

AAAI Conference 2024 Conference Paper

Parameterized Approximation Algorithms for Sum of Radii Clustering and Variants

Xianrun Chen
Dachuan Xu
Yicheng Xu
Yong Zhang

Clustering is one of the most fundamental tools in artificial intelligence, machine learning, and data mining. In this paper, we follow one of the recent mainstream topics of clustering, Sum of Radii (SoR), which naturally arises as a balance between the folklore k-center and k-median. SoR aims to determine a set of k balls, each centered at a point in a given dataset, such that their union covers the entire dataset while minimizing the sum of radii of the k balls. We propose a general technical framework to overcome the challenge posed by varying radii in SoR, which yields fixed-parameter tractable (fpt) algorithms with respect to k (i.e., whose running time is f(k) ploy(n) for some f). Our framework is versatile and obtains fpt approximation algorithms with constant approximation ratios for SoR as well as its variants in general metrics, such as Fair SoR and Matroid SoR, which significantly improve the previous results.

PDF Details DOI

ICML Conference 2024 Conference Paper

SPABA: A Single-Loop and Probabilistic Stochastic Bilevel Algorithm Achieving Optimal Sample Complexity

Tianshu Chu
Dachuan Xu
Wei Yao
Jin Zhang

While stochastic bilevel optimization methods have been extensively studied for addressing large-scale nested optimization problems in machine learning, it remains an open question whether the optimal complexity bounds for solving bilevel optimization are the same as those in single-level optimization. Our main result resolves this question: SPABA, an adaptation of the PAGE method for nonconvex optimization in (Li et al. , 2021) to the bilevel setting, can achieve optimal sample complexity in both the finite-sum and expectation settings. We show the optimality of SPABA by proving that there is no gap in complexity analysis between stochastic bilevel and single-level optimization when implementing PAGE. Notably, as indicated by the results of (Dagréou et al. , 2022), there might exist a gap in complexity analysis when implementing other stochastic gradient estimators, like SGD and SAGA. In addition to SPABA, we propose several other single-loop stochastic bilevel algorithms, that either match or improve the state-of-the-art sample complexity results, leveraging our convergence rate and complexity analysis. Numerical experiments demonstrate the superior practical performance of the proposed methods.

JMLR Journal 2024 Journal Article

Zeroth-order Stochastic Approximation Algorithms for DR-submodular Optimization

Yuefang Lian
Xiao Wang
Dachuan Xu
Zhongrui Zhao

In this paper, we study approximation algorithms for several classes of DR-submodular optimization problems, where DR is short for diminishing return. Following a newly introduced algorithm framework for zeroth-order stochastic approximation methods, we first propose algorithms {\bf CG-ZOSA} and {\bf RG-ZOSA} for smooth DR-submodular optimization based on the coordinate-wise gradient estimator and the randomized gradient estimator, respectively. Our theoretical analysis proves that \rm{\bf{CG-ZOSA}} can reach a solution whose expected objective value exceeds $(1-e^{-1}-\epsilon^{2})$OPT$-\epsilon$ after $\mathcal{O}(\epsilon^{-2})$ iterations and $\mathcal{O}(N^{2/3}d\epsilon^{-2})$ oracle calls, where $d$ represents the problem dimension. On the other hand, \rm{\bf{RG-ZOSA}} improves the approximation ratio to $(1-e^{-1}-\epsilon^{2}/d)$ while maintaining the same overall oracle complexity. For non-smooth up-concave maximization problems, we propose a novel auxiliary function based on a smoothed objective function and introduce the \rm{\bf{NZOSA}} algorithm. This algorithm achieves an approximation ratio of $(1-e^{-1}-\epsilon \ln \epsilon^{-1}- \epsilon^{2}\ln \epsilon^{-1})$ with $\mathcal{O}(d\epsilon^{-2})$ iterations and $\mathcal{O}(N^{2/3}d^{3/2} \epsilon^{-3})$ oracle calls. We also extend \rm{\bf{NZOSA}} to handle a class of robust DR-submodular maximization problems. To validate the effectiveness of our proposed algorithms, we conduct experiments on both synthetic and real-world problems. The results demonstrate the superior performance and efficiency of our methods in solving DR-submodular optimization problems. [abs] [ pdf ][ bib ] &copy JMLR 2024. ( edit, beta )

TCS Journal 2023 Journal Article

A game-theoretic perspective of deep neural networks

Chunying Ren
Zijun Wu
Dachuan Xu
Wenqing Xu

We devote this paper to a theoretic analysis of deep neural networks from a game-theoretical perspective. We consider a general deep neural network D with linear activation functions f ( x ) = x + b. We show that the deep neural network can be transformed into a non-atomic congestion game, regardless whether it is fully connected or locally connected. Moreover, we show that learning the weight and bias vectors of D for a training set H is equivalent to computing an optimal solution of the corresponding non-atomic congestion game. In particular, when D is a deep neural network for a classification task, then the learning is equivalent to computing a Wardrop equilibrium of the corresponding non-atomic congestion game.

TCS Journal 2021 Journal Article

A constrained two-stage submodular maximization

Ruiqi Yang
Shuyang Gu
Chuangen Gao
Weili Wu
Hua Wang
Dachuan Xu

In this paper, we investigate the two-stage submodular maximization problem, where there is a collection F = { f 1, .. ., f m } of m submodular functions which are defined on the same element ground set Ω. The goal is to select a subset S ⊆ Ω of size at most ℓ such that 1 m ∑ f ∈ F max T ⊆ S, T ∈ I ⁡ f ( T ) is maximized, where I denotes a specifically-defined independence system. We consider the two-stage submodular maximization with a P-matroid constraint and present a ( 1 / ( P + 1 ) ) ( 1 − 1 / e ( P + 1 ) ) -approximation algorithm. Furthermore, we extend the algorithm to the two-stage submodular maximization with a more generalized P-exchange system constraint and show the approximation ratio can be maintained with slightly modifications of the algorithm.

AAAI Conference 2021 Conference Paper

A Trace-restricted Kronecker-Factored Approximation to Natural Gradient

Kaixin Gao
Xiaolei Liu
Zhenghai Huang
Min Wang
Zidong Wang
Dachuan Xu
Fan Yu

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 secondorder optimization methods for training deep neural networks. In this work, inspired by diagonal approximations and factored approximations such as Kronecker-factored Approximate Curvature (KFAC), we propose a new approximation to the Fisher information matrix (FIM) called Trace-restricted Kronecker-factored Approximate Curvature (TKFAC), which can hold the certain trace relationship between the exact and the approximate FIM. In TKFAC, we decompose each block of the approximate FIM as a Kronecker product of two smaller matrices and scaled by a coefficient related to trace. We theoretically analyze TKFAC’s approximation error and give an upper bound of it. We also propose a new damping technique for TKFAC on convolutional neural networks to maintain the superiority of second-order optimization methods during training. Experiments show that our method has better performance compared with several state-of-the-art algorithms on some deep network architectures.

TCS Journal 2021 Journal Article

Approximation algorithms for spherical k-means problem using local search scheme

Dongmei Zhang
Yukun Cheng
Min Li
Yishui Wang
Dachuan Xu

In the spherical k-means problem (SKMP), which is a well-studied clustering problem in text mining, we are given an n-point set D in d-dimensional unit sphere S d, and an integer k ≤ n. The goal is to find a center subset S ⊂ S d with | S | ≤ k that minimizes the sum of cosine dissimilarity measure for each point in D to the nearest center. We prove that any γ-approximation algorithm for the k-means problem (KMP) can be adapted to the SKMP with 2γ-approximation ratio. It follows that there is a local search ( 18 + ϵ ) -approximation algorithm for the SKMP, by leveraging the classical local search ( 9 + ϵ ) -approximation algorithm for the KMP. Therefore, an interesting problem arises, that is whether there exists an approximation algorithm using local search scheme directly for the SKMP. In this paper, we present a local search approximation algorithm for the SKMP and prove its performance guarantee is ( 2 ( 4 + 7 ) + ϵ ). We also conduct numerical computation to show the efficiency of the local search approximation algorithm by single-swap operation in the end.

TCS Journal 2021 Journal Article

Approximation algorithms for the dynamic k-level facility location problems

Limin Wang
Zhao Zhang
Chenchen Wu
Dachuan Xu
Xiaoyan Zhang

In this paper, we first consider a dynamic k-level facility location problem, which is a generalization of the k-level facility location problem when considering time factor. We present a combinatorial primal-dual approximation algorithm for this problem which finds a constant factor approximate solution. Then, we investigative the dynamic k-level facility location problem with submodular penalties and outliers, which extend the existing problem on two fronts, namely from static to dynamic and from without penalties (outliers) to penalties (outliers) allowed. Based on primal-dual technique and the triangle inequality property, we also give two constant factor approximation algorithms for the dynamic problem with submodular penalties and outliers, respectively.

TCS Journal 2021 Journal Article

Bicriteria algorithms to balance coverage and cost in team formation under online model

Yijing Wang
Dachuan Xu
Donglei Du
Ran Ma

In this work, we investigate online bicriteria algorithms that consider both coverage and cost in the team formation problem, which selects a set of experts with the objective of maximizing the difference of two set functions f − ℓ, where function f is non-negative normalized monotone approximately submodular, and function ℓ is non-negative linear. By exploiting the problem's combinatorial structure, we present three bicriteria algorithms along with their corresponding competitive analysis. The first two algorithms handle the cases where function f is γ-weakly submodular, and strictly γ-weakly submodular, respectively. The last algorithm is more general by integrating the first two with extra parameters introduced.

TCS Journal 2021 Journal Article

Deterministic approximation algorithm for submodular maximization subject to a matroid constraint

Xin Sun
Dachuan Xu
Longkun Guo
Min Li

In this paper, we study the generalized submodular maximization problem with a non-negative monotone submodular set function as the objective function and subject to a matroid constraint. The problem is generalized through the curvature parameter α ∈ [ 0, 1 ] which measures how far a set function deviates from linearity to submodularity. We propose a deterministic approximation algorithm which uses the approximation algorithm proposed by Buchbinder et al. [2] as a building block and inherits the approximation guarantee for α = 1. For general value of the curvature parameter α ∈ [ 0, 1 ], we present an approximation algorithm with a factor of 1 + h α ( y ) + Δ ⋅ [ 3 + α − ( 2 + α ) y − ( 1 + α ) h α ( y ) ] 2 + α + ( 1 + α ) ( 1 − y ), where y ∈ [ 0, 1 ] is a predefined parameter for tuning the ratio. In particular, when α = 1 we obtain a ratio 0. 5008 when setting y = 0. 9, coinciding with the renowned state-of-art approximate ratio; when α = 0 that the object is a linear function, the approximation factor equals one and our algorithm is indeed an exact algorithm that always produces optimum solutions.

TCS Journal 2021 Journal Article

Parallelized maximization of nonsubmodular function subject to a cardinality constraint

Hongxiang Zhang
Dachuan Xu
Longkun Guo
Jingjing Tan

In the paper, we consider the problem of maximizing the multilinear extension of a nonsubmodular set function subject to a k-cardinality constraint with adaptive rounds of evaluation queries. We devise an algorithm which achieves a ratio of ( 1 − e − γ 2 − ϵ ) and requires O ( log ⁡ n / ϵ 2 ) adaptive rounds and O ( n log ⁡ n / ϵ 2 ) queries, where γ is the continuous generic submodularity ratio that compares favorably in flexibility to the traditional submodularity ratio proposed by Das and Kempe. The key idea of our algorithm is originated from the parallel-greedy algorithm proposed by Chekuri et al. , but incorporating with two major changes to retain the performance guarantee: First, identify all good coordinates with the continuous generic submodularity ratio and gradient values approximately as large as the best coordinate, and increase along all these coordinates uniformly; Second, increase x along these coordinates by a dynamical increment whose value depends on γ. The key difficulty of our algorithm is that when the function is nonsubmodular, the set of the best coordinate does not decrease during iterations; while provided submodularity, the decreasing can be ensured by the parallel-greedy algorithm. Our algorithms slightly compromise performance guarantee for the sake of extending to constrained nonsubmodular maximization with parallelism, provided that the state-of-art algorithm for the corresponding submodular version attains an approximation ratio of ( 1 − 1 / e − ϵ ) and requires O ( log ⁡ n / ϵ 2 ) adaptive rounds.

AAAI Conference 2021 Conference Paper

THOR, Trace-based Hardware-driven Layer-Oriented Natural Gradient Descent Computation

Mengyun Chen
Kaixin Gao
Xiaolei Liu
Zidong Wang
Ningxi Ni
Qian Zhang
Lei Chen
Chao Ding

It is well-known that second-order optimizer can accelerate the training of deep neural networks, however, the huge computation cost of second-order optimization makes it impractical to apply in real practice. In order to reduce the cost, many methods have been proposed to approximate a second-order matrix. Inspired by KFAC, we propose a novel Trace-based Hardware-driven layer-ORiented Natural Gradient Descent Computation method, called THOR, to make the second-order optimization applicable in the real application models. Specifically, we gradually increase the update interval and use the matrix trace to determine which blocks of Fisher Information Matrix (FIM) need to be updated. Moreover, by resorting the power of hardware, we have designed a hardware-driven approximation method for computing FIM to achieve better performance. To demonstrate the effectiveness of THOR, we have conducted extensive experiments. The results show that training ResNet-50 on ImageNet with THOR only takes 66. 7 minutes to achieve a top-1 accuracy of 75. 9 % under an 8 Ascend 910 environment with MindSpore, a new deep learning computing framework. Moreover, with more computational resources, THOR can only takes 2. 7 minutes to 75. 9 % with 256 Ascend 910.

TCS Journal 2020 Journal Article

Interaction-aware influence maximization and iterated sandwich method

Chuangen Gao
Shuyang Gu
Ruiqi Yang
Jiguo Yu
Weili Wu
Dachuan Xu

Influence maximization problem has been studied extensively with the development of online social networks. Most of the existing works focus on the maximization of influence spread under the assumption that the number of influenced users determines the success of a product promotion. However, the profit of some products such as online game depends on the interactions among users besides the number of users. In this paper, we take both the number of active users and the user-to-user interactions into account and propose the interaction-aware influence maximization problem. To address this practical issue, we analyze its complexity and modularity, propose the sandwich theory which is based on decomposing the non-submodular objective function into the difference of two submodular functions and design two iterated sandwich algorithms which are guaranteed to get data dependent approximation solution. Through real data sets, we verify the effectiveness of our proposed algorithms.

TCS Journal 2020 Journal Article

M UFLP: Universal facility location problem in the p-th power of metric space

Yicheng Xu
Dachuan Xu
Yong Zhang
Juan Zou

We propose and study the M p UFLP (universal facility location problem in the p-th power of metric space) in this paper, where the universal facility location problem (UFLP) extends several classical facility location problems like the uncapacitated facility location, hard-capacitated facility location, soft-capacitated facility location, incremental-cost facility location, concave-cost facility location, etc. In UFLP, a set of facilities, a set of clients, as well as the distances between them are given. Each facility has its specific cost function w. r. t. the amount of clients assigned to that facility. The goal is to assign the clients to facilities such that the sum of facility cost and service cost is minimized. In traditional facility location problems, the unit service cost is proportional to the distance between the client and its assigned facility and thus metric. However, in our work, this assumption is removed and a generalized version of universal facility location problem is proposed, which is the so-called M n UFLP. When p = 2, it is also known as l 2 2 measure considered by Jain and Vazirani [J. ACM'01] and Fernandes et al. [Math. Program. '15]. Particularly in this case, we extend their work to include the aforementioned variants of facility location and a local search based ( 11. 18 + ε ) -approximation algorithm is proposed. Furthermore, the reanalysis of the proposed algorithm gives a p-related performance guarantee for general p.

TCS Journal 2020 Journal Article

Offline and online algorithms for single-minded selling problem

Yong Zhang
Francis Y.L. Chin
Sheung-Hung Poon
Hing-Fung Ting
Dachuan Xu
Dongxiao Yu

Given a seller with k types of items and n single-minded buyers, i. e. , each buyer is only interested in a particular bundle of items, to maximize the revenue, the seller must assign some amount of bundles to each buyer with respect to the buyer's accepted price. Each buyer b i is associated with a value function v i ( ⋅ ) such that v i ( x ) is the accepted unit bundle price b i is willing to pay for x bundles. In this paper, we assume that bundles can be sold fractionally. The single-minded item selling problem is proved to be NP-hard. Moreover, we give an O ( k ) -approximation algorithm. For the online version, i. e. , buyers come one by one and the decision must be made immediately on the arrival of each buyer, an O ( k ⋅ ( log ⁡ h + log ⁡ k ) ) -competitive algorithm is given, where h is the highest unit item price among all buyers.

TCS Journal 2019 Journal Article

Efficient approximation algorithms for maximum coverage with group budget constraints

Longkun Guo
Min Li
Dachuan Xu

Given a ground set U with a non-negative weight w i for each i ∈ U, a positive integer k and a collection of sets S, which is partitioned into a family of disjoint groups G, the goal of the Maximum Coverage problem with Group budget constraints (MCG) is to select k sets from S, such that the total weight of the union of the k sets is maximized and at most one set is selected from each group G ∈ G. We first present an approximation algorithm with a factor 1 − 1 e and an exponential time via randomized linear programming rounding technique. Then we improve the time complexity of the algorithm to O ( ( m + n ) 3. 5 L + k 3. 5 q 7 L ) for | S | = m, | U | = n, and L being the length of the input, by the key idea of modeling the selection of groups as computing a constrained flow in a corresponding auxiliary graph. The algorithm is later shown can be extended to solve two generalizations of MCG. Last but not the least, we present another algorithm with a time complexity O ( ( m + n ) 3. 5 L + k δ 10. 5 L ) and a slightly increased approximation ratio 1 − e 1 δ − 1 mainly based on the idea of partition, where δ ≥ 2 is a parameter tuning which can balance the time complexity and the ratio.

TCS Journal 2019 Journal Article

Improved approximation algorithm for universal facility location problem with linear penalties

Yicheng Xu
Dachuan Xu
Donglei Du
Chenchen Wu

The input of the universal facility location problem includes a set of clients and a set of facilities. Our goal is to find an assignment such that each client is assigned while the total connection and facility cost is minimized. Here the connection cost is proportional to the distance between each client and its assigned facility, thus metric. The facility cost is a nondecreasing function with respect to the total number of clients assigned to the facility. The universal facility location problem is NP-hard since it generalizes several classical facility location problems. Our work considers the universal facility location problem with linear penalties, a generalized version of the universal facility location problem. Here each client can be rejected for service with certain penalty cost. Thus we have to consider penalty cost other than total connection and facility cost in our objective function. Based on local search method, we present a ( 5. 83 + ϵ ) -approximation algorithm for this problem.

TCS Journal 2018 Journal Article

An approximation algorithm for the k-median problem with uniform penalties via pseudo-solution

Chenchen Wu
Donglei Du
Dachuan Xu

We present a ( 1 + 3 + ϵ ) -approximation algorithm for the k-median problem with uniform penalties, extending the recent result by Li and Svensson for the classical k-median problem without penalties. One important difference of this work from that of Li and Svensson is a new definition of sparse instance to exploit the combinatorial structure of our problem.

TCS Journal 2018 Journal Article

Approximation and hardness results for the Max k-Uncut problem

Peng Zhang
Chenchen Wu
Dachuan Xu

In the study of the homophily law of large scale complex networks, we get a combinatorial optimization problem which we call the Max k -Uncut problem. Given an n-vertex undirected graph G = ( V, E ) with nonnegative weights { w e | e ∈ E } defined on edges, and a positive integer k, the Max k -Uncut problem asks to find a partition { V 1, V 2, ⋯, V k } of V such that the total weight of edges that are not cut is maximized. Intuitively, an edge that is not cut connects two vertices with the same or similar attributes since they are in the same part of the partition. Interestingly, the Max k -Uncut problem is just the complement of the classic Min k -Cut problem. For Max k -Uncut, we present a randomized ( 1 − k n ) 2 -approximation algorithm, a greedy ( 1 − 2 ( k − 1 ) n ) -approximation algorithm, and an Ω ( 1 2 α ) -approximation algorithm by reducing it to Densest k -Subgraph, where α is the approximation ratio of the Densest k -Subgraph problem. More importantly, we show that Max k -Uncut and Densest k -Subgraph are in fact equivalent in approximability up to a factor of 2. We also prove an approximation hardness result for Max k -Uncut under the assumption P ≠ NP.

TCS Journal 2016 Journal Article

Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique

Dachuan Xu
Fengmin Wang
Donglei Du
Chenchen Wu

The notion of penalty has been introduced into many combinatorial optimization models. In this paper, we consider the submodular vertex cover problems with linear and submodular penalties, which are two variants of the submodular vertex cover problem where not all the edges are required to be covered by a vertex cover, and the uncovered edges are penalized. The problem is to determine a vertex subset to cover some edges and penalize the uncovered edges such that the total cost including covering and penalty is minimized. To overcome the difficulty of implementing the primal-dual framework directly, we relax the two dual programs to slightly weaker versions. We then present two primal-dual approximation algorithms with approximation ratios of 2 and 4, respectively.

TCS Journal 2015 Journal Article

Primal–dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach

Chenchen Wu
Donglei Du
Dachuan Xu

The main contribution of this work is to propose a primal–dual combinatorial 3 ( 1 + ε ) -approximation algorithm for the two-level facility location problem (2-LFLP) by exploring the approximation oracle concept. This result improves the previous primal–dual 6-approximation algorithm for the multilevel facility location problem, and also matches the previous primal–dual approximation ratio for the single-level facility location problem. One of the major merits of primal–dual type algorithms is their easy adaption to other variants of the facility location problems. As a demonstration, our primal–dual approximation algorithm can be easily adapted to several variants of the 2-LFLP, including models with stochastic scenario, dynamically arrived demands, and linear facility cost.

TCS Journal 2013 Journal Article

A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties

Yu Li
Donglei Du
Naihua Xiu
Dachuan Xu

We offer the currently best approximation ratio 2. 375 for the facility location problem with submodular penalties (FLPSP), improving not only the previous best combinatorial ratio 3, but also the previous best non-combinatorial ratio 2. 488. We achieve this improved ratio by combining the primal–dual scheme with the greedy augmentation technique.