26 results on '"Dachuan Xu"'
Search Results
2. Bicriteria streaming algorithms to balance gain and cost with cardinality constraint
- Author
-
Yijing Wang, Donglei Du, Yanjun Jiang, and Dachuan Xu
- Subjects
Mathematical optimization ,Control and Optimization ,Computer science ,Applied Mathematics ,Function (mathematics) ,Linear function ,Computer Science Applications ,Submodular set function ,Constraint (information theory) ,Cardinality ,Monotone polygon ,Computational Theory and Mathematics ,Theory of computation ,Discrete Mathematics and Combinatorics ,Computer Science::Data Structures and Algorithms ,Streaming algorithm - Abstract
Team formation plays an essential role in the labor market. In this paper, we propose two bicriteria algorithms to construct a balance between gain and cost in a team formation problem under the streaming model, subject to a cardinality constraint. We formulate the problem as maximizing the difference of a non-negative normalized monotone submodular function and a non-negative linear function. As an extension, we also consider the case where the first function is $$\gamma $$ -weakly submodular. Combining the greedy technique with the threshold method, we present bicriteria streaming algorithms and give detailed analysis for both of these models. Our analysis is competitive with that in Ene’s work.
- Published
- 2021
3. Approximation algorithms for the lower bounded correlation clustering problem
- Author
-
Sai Ji, Yinhong Dong, Donglei Du, Dongzhao Wang, and Dachuan Xu
- Subjects
Control and Optimization ,Computational Theory and Mathematics ,Applied Mathematics ,Discrete Mathematics and Combinatorics ,Computer Science Applications - Published
- 2022
4. Improved local search algorithms for Bregman k-means and its variants
- Author
-
Dan Wu, Longkun Guo, Xiaoyun Tian, and Dachuan Xu
- Subjects
021103 operations research ,Control and Optimization ,business.industry ,Applied Mathematics ,0211 other engineering and technologies ,Center (category theory) ,k-means clustering ,Piecewise constant approximation ,0102 computer and information sciences ,02 engineering and technology ,Bregman divergence ,01 natural sciences ,Computer Science Applications ,Computational Theory and Mathematics ,Computer Science::Computational Engineering, Finance, and Science ,010201 computation theory & mathematics ,Discrete Mathematics and Combinatorics ,Local search (optimization) ,business ,Algorithm ,Mathematics - Abstract
In this paper, we consider the Bregman k-means problem (BKM) which is a variant of the classical k-means problem. For an n-point set $${\mathcal {S}}$$ and $$k \le n$$ with respect to $$\mu $$ -similar Bregman divergence, the BKM problem aims first to find a center subset $$C \subseteq {\mathcal {S}}$$ with $$ \mid C \mid = k$$ and then separate $${\mathcal {S}}$$ into k clusters according to C, such that the sum of $$\mu $$ -similar Bregman divergence from each point in $${\mathcal {S}}$$ to its nearest center is minimized. We propose a $$\mu $$ -similar BregMeans++ algorithm by employing the local search scheme, and prove that the algorithm deserves a constant approximation guarantee. Moreover, we extend our algorithm to solve a variant of BKM called noisy $$\mu $$ -similar Bregman k-means++ (noisy $$\mu $$ -BKM++) which is BKM in the noisy scenario. For the same instance and purpose as BKM, we consider the case of sampling a point with an imprecise probability by a factor between $$1-\varepsilon _1$$ and $$1+ \varepsilon _2$$ for $$\varepsilon _1 \in [0,1)$$ and $$\varepsilon _2 \ge 0$$ , and obtain an approximation ratio of $$O(\log ^2 k)$$ in expectation.
- Published
- 2021
5. The spherical k-means++ algorithm via local search scheme
- Author
-
Xiaoyun Tian, Ling Gai, Donglei Du, and Dachuan Xu
- Subjects
021103 operations research ,Control and Optimization ,business.industry ,Applied Mathematics ,0211 other engineering and technologies ,k-means clustering ,Center (category theory) ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Measure (mathematics) ,Computer Science Applications ,Combinatorics ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Theory of computation ,Discrete Mathematics and Combinatorics ,Trigonometric functions ,Local search (optimization) ,Point (geometry) ,business ,Cluster analysis ,Mathematics - Abstract
The spherical k-means problem (SKMP) is an important variant of the k-means clustering problem (KMP). In this paper, we consider the SKMP, which aims to divide the n points in a given data point set $${\mathcal {S}}$$ into k clusters so as to minimize the total sum of the cosine dissimilarity measure from each data point to their respective closest cluster center. Our main contribution is to design an expected constant approximation algorithm for the SKMP by integrating the seeding algorithm for the KMP and the local search technique. By utilizing the structure of the clusters, we further obtain an improved LocalSearch++ algorithm involving $$\varepsilon k$$ local search steps.
- Published
- 2021
6. Sequence submodular maximization meets streaming
- Author
-
Ruiqi Yang, Dachuan Xu, Longkun Guo, and Dongmei Zhang
- Subjects
Control and Optimization ,Computational Theory and Mathematics ,Applied Mathematics ,Discrete Mathematics and Combinatorics ,Computer Science Applications - Published
- 2020
7. Approximating the $$\tau $$-relaxed soft capacitated facility location problem
- Author
-
Yicheng Xu, Lu Han, Dongmei Zhang, and Dachuan Xu
- Subjects
021103 operations research ,Control and Optimization ,Triangle inequality ,Applied Mathematics ,0211 other engineering and technologies ,Approximation algorithm ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Facility location problem ,Computer Science Applications ,Metric k-center ,Combinatorics ,Set (abstract data type) ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Theory of computation ,Metric (mathematics) ,Physics::Accelerator Physics ,Discrete Mathematics and Combinatorics ,Connection (algebraic framework) ,Mathematics - Abstract
In this paper, we consider the $$\tau $$ -relaxed soft capacitated facility location problem ( $$\tau $$ -relaxed SCFLP), which extends several well-known facility location problems like the squared metric soft capacitated facility location problem (SMSCFLP), soft capacitated facility location problem (SCFLP), squared metric facility location problem and uncapacitated facility location problem. In the $$\tau $$ -relaxed SCFLP, we are given a facility set $$\mathcal {F}$$ , a client set and a parameter $$\tau \ge 1$$ . Every facility $$i \in \mathcal {F}$$ has a capacity $$u_i$$ and an opening cost $$f_i$$ , and can be opened multiple times. If facility i is opened l times, this facility can be connected by at most $$l u_i$$ clients and incurs an opening cost of $$l f_i$$ . Every facility-client pair has a connection cost. Under the assumption that the connection costs are non-negative, symmetric and satisfy the $$\tau $$ -relaxed triangle inequality, we wish to open some facilities (once or multiple times) and connect every client to an opened facility without violating the capacity constraint so as to minimize the total opening costs as well as connection costs. As our main contribution, we propose a primal-dual based $$(3 \tau + 1)$$ -approximation algorithm for the $$\tau $$ -relaxed SCFLP. Furthermore, our algorithm not only extends the applicability of the primal-dual technique but also improves the previous approximation guarantee for the SMSCFLP from $$11.18+ \varepsilon $$ to 10.
- Published
- 2020
8. Maximizing a monotone non-submodular function under a knapsack constraint
- Author
-
Yishui Wang, Zhenning Zhang, Dachuan Xu, Bin Liu, and Dongmei Zhang
- Subjects
021103 operations research ,Control and Optimization ,Optimization problem ,Applied Mathematics ,0211 other engineering and technologies ,TheoryofComputation_GENERAL ,0102 computer and information sciences ,02 engineering and technology ,Maximization ,Function (mathematics) ,01 natural sciences ,Computer Science Applications ,Submodular set function ,Combinatorics ,Monotone polygon ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Theory of computation ,Discrete Mathematics and Combinatorics ,Combinatorial optimization ,Computer Science::Data Structures and Algorithms ,Greedy algorithm ,Mathematics - Abstract
Submodular optimization has been well studied in combinatorial optimization. However, there are few works considering about non-submodular optimization problems which also have many applications, such as experimental design, some optimization problems in social networks, etc. In this paper, we consider the maximization of non-submodular function under a knapsack constraint, and explore the performance of the greedy algorithm, which is characterized by the submodularity ratio $$\beta $$ and curvature $$\alpha $$ . In particular, we prove that the greedy algorithm enjoys a tight approximation guarantee of $$ (1-e^{-\alpha \beta })/{\alpha }$$ for the above problem. To our knowledge, it is the first tight constant factor for this problem. We further utilize illustrative examples to demonstrate the performance of our algorithm.
- Published
- 2020
9. Approximation algorithms for two variants of correlation clustering problem
- Author
-
Dachuan Xu, Min Li, Sai Ji, and Yishui Wang
- Subjects
021103 operations research ,Control and Optimization ,Theoretical computer science ,Computer science ,Applied Mathematics ,Correlation clustering ,0211 other engineering and technologies ,Piecewise constant approximation ,Approximation algorithm ,0102 computer and information sciences ,02 engineering and technology ,Link (geometry) ,01 natural sciences ,Telecommunications network ,Computer Science Applications ,ComputingMethodologies_PATTERNRECOGNITION ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Theory of computation ,Cluster (physics) ,Discrete Mathematics and Combinatorics ,Cluster analysis - Abstract
Correlation clustering problem is a clustering problem which has many applications such as protein interaction networks, cross-lingual link detection, communication networks, and social computing. In this paper, we introduce two variants of correlation clustering problem: correlation clustering problem on uncertain graphs and correlation clustering problem with non-uniform hard constrained cluster sizes. Both problems overcome part of the limitations of the existing variants of correlation clustering problem and have practical applications in the real world. We provide a constant approximation algorithm and two approximation algorithms for the former and the latter problem, respectively.
- Published
- 2020
10. The seeding algorithm for spherical k-means clustering with penalties
- Author
-
Min Li, Dongmei Zhang, Longkun Guo, Dachuan Xu, and Sai Ji
- Subjects
Surface (mathematics) ,021103 operations research ,Control and Optimization ,Applied Mathematics ,0211 other engineering and technologies ,k-means clustering ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Computer Science Applications ,Separable space ,Data set ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Theory of computation ,Discrete Mathematics and Combinatorics ,Trigonometric functions ,Partition (number theory) ,Cluster analysis ,Algorithm ,Mathematics - Abstract
Spherical k-means clustering as a known NP-hard variant of the k-means problem has broad applications in data mining. In contrast to k-means, it aims to partition a collection of given data distributed on a spherical surface into k sets so as to minimize the within-cluster sum of cosine dissimilarity. In the paper, we introduce spherical k-means clustering with penalties and give a $$2\max \{2,M\}(1+M)(\ln k+2)$$-approximation algorithm. Moreover, we prove that when against spherical k-means clustering with penalties but on separable instances, our algorithm is with an approximation ratio $$2\max \{3,M+1\}$$ with high probability, where M is the ratio of the maximal and the minimal penalty cost of the given data set.
- Published
- 2020
11. An approximation algorithm for the uniform capacitated k-means problem
- Author
-
Donglei Du, Lu Han, Dachuan Xu, and Dongmei Zhang
- Subjects
021103 operations research ,Control and Optimization ,Applied Mathematics ,0211 other engineering and technologies ,Center (category theory) ,Approximation algorithm ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Upper and lower bounds ,Square (algebra) ,Computer Science Applications ,Combinatorics ,Cardinality ,Computational Theory and Mathematics ,Integer ,010201 computation theory & mathematics ,Discrete Mathematics and Combinatorics ,Point (geometry) ,Local search (constraint satisfaction) ,Mathematics - Abstract
In this paper, we consider the uniform capacitated k-means problem (UC-k-means), an extension of the classical k-means problem (k-means) in machine learning. In the UC-k-means, we are given a set $$\mathcal {D}$$ of n points in d-dimensional space and an integer k. Every point in the d-dimensional space has an uniform capacity which is an upper bound on the number of points in $$\mathcal {D}$$ that can be connected to this point. Every two-point pair in the space has an associated connecting cost, which is equal to the square of the distance between these two points. We want to find at most k points in the space as centers and connect every point in $$\mathcal {D}$$ to some center without violating the capacity constraint, such that the total connecting costs is minimized. Based on the technique of local search, we present a bi-criteria approximation algorithm, which has a constant approximation guarantee and violates the cardinality constraint within a constant factor, for the UC-k-means.
- Published
- 2020
12. Approximation algorithm for squared metric two-stage stochastic facility location problem
- Author
-
Yishui Wang, Dachuan Xu, Jin Zhang, Min Li, and Chenchen Wu
- Subjects
Mathematical optimization ,021103 operations research ,Control and Optimization ,Computer science ,Applied Mathematics ,0211 other engineering and technologies ,Approximation algorithm ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Facility location problem ,Computer Science Applications ,Connection (mathematics) ,Set (abstract data type) ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Metric (mathematics) ,Theory of computation ,Discrete Mathematics and Combinatorics ,Stage (hydrology) ,Integer programming - Abstract
In this paper, we consider a variant of the classical uncapacitated facility location problem, so-called squared metric two-stage stochastic facility location problem (SM-2-SFLP) which can treat the uncertainty of the set of clients and facility costs. We assume that the connection cost is squared metric, a variant of the metric case which is widely researched. We give a new 0–1 integer linear programming for SM-2-SFLP. Based on the new formulation, we apply two known algorithms to SM-2-SFLP, and analyze the approximation ratio and per-scenario bound respectively.
- Published
- 2019
13. A spectral partitioning algorithm for maximum directed cut problem
- Author
-
Dongmei Zhang, Donglei Du, Zhenning Zhang, Chenchen Wu, and Dachuan Xu
- Subjects
021103 operations research ,Control and Optimization ,Applied Mathematics ,Rounding ,0211 other engineering and technologies ,0102 computer and information sciences ,02 engineering and technology ,Directed graph ,01 natural sciences ,Computer Science Applications ,Arc (geometry) ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Theory of computation ,Discrete Mathematics and Combinatorics ,Quadratic programming ,Algorithm ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
We investigate the maximum directed cut (MaxDC) problem by designing a spectral partitioning algorithm. Given a directed graph with nonnegative arc weights, we wish to obtain a bipartition of the vertices such that the total weight of the directed cut arcs is maximized. Relaxing the MaxDC problem as a quadratic program allows us to explore combinatorial properties of the optimal solution, leading to a 0.272-approximation algorithm via the technique of spectral partitioning rounding.
- Published
- 2019
14. Local search approximation algorithms for the k-means problem with penalties
- Author
-
Zhenning Zhang, Chenchen Wu, Chunlin Hao, Dachuan Xu, and Dongmei Zhang
- Subjects
021103 operations research ,Control and Optimization ,Generalization ,Applied Mathematics ,0211 other engineering and technologies ,Center (category theory) ,Explained sum of squares ,Approximation algorithm ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Computer Science Applications ,Combinatorics ,Computational Theory and Mathematics ,Integer ,010201 computation theory & mathematics ,Theory of computation ,Discrete Mathematics and Combinatorics ,Backslash ,Local search (constraint satisfaction) ,Mathematics - Abstract
In this paper, we study the k-means problem with (nonuniform) penalties (k-MPWP) which is a natural generalization of the classic k-means problem. In the k-MPWP, we are given an n-client set $$ {\mathcal {D}} \subset {\mathbb {R}}^d$$ , a penalty cost $$p_j>0$$ for each $$j \in {\mathcal {D}}$$ , and an integer $$k \le n$$ . The goal is to open a center subset $$F \subset {\mathbb {R}}^d$$ with $$ |F| \le k$$ and to choose a client subset $$P \subseteq {\mathcal {D}} $$ as the penalized client set such that the total cost (including the sum of squares of distance for each client in $$ {\mathcal {D}} \backslash P $$ to the nearest open center and the sum of penalty cost for each client in P) is minimized. We offer a local search $$( 81+ \varepsilon )$$ -approximation algorithm for the k-MPWP by using single-swap operation. We further improve the above approximation ratio to $$( 25+ \varepsilon )$$ by using multi-swap operation.
- Published
- 2018
15. A local search approximation algorithm for a squared metric k-facility location problem
- Author
-
Zhenning Zhang, Dongmei Zhang, Peng Zhang, Yishui Wang, and Dachuan Xu
- Subjects
Discrete mathematics ,021103 operations research ,Control and Optimization ,business.industry ,Applied Mathematics ,0211 other engineering and technologies ,Explained sum of squares ,Approximation algorithm ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Facility location problem ,Computer Science Applications ,Metric k-center ,Metric space ,Computational Theory and Mathematics ,Integer ,010201 computation theory & mathematics ,Metric (mathematics) ,Physics::Accelerator Physics ,Discrete Mathematics and Combinatorics ,Local search (optimization) ,business ,Mathematics - Abstract
In this paper, we introduce a squared metric k-facility location problem (SM-k-FLP) which is a generalization of the squared metric facility location problem and k-facility location problem (k-FLP). In the SM-k-FLP, we are given a client set $$\mathcal {C}$$ and a facility set $$\mathcal {F} $$ from a metric space, a facility opening cost $$f_i \ge 0$$ for each $$ i \in \mathcal {F}$$ , and an integer k. The goal is to open a facility subset $$F \subseteq \mathcal {F}$$ with $$ |F| \le k$$ and to connect each client to the nearest open facility such that the total cost (including facility opening cost and the sum of squares of distances) is minimized. Using local search and scaling techniques, we offer a constant approximation algorithm for the SM-k-FLP.
- Published
- 2018
16. An approximation algorithm for soft capacitated k-facility location problem
- Author
-
Chenchen Wu, Dachuan Xu, Yanjun Jiang, Dongmei Zhang, and Donglei Du
- Subjects
Control and Optimization ,Applied Mathematics ,Structure (category theory) ,Approximation algorithm ,0102 computer and information sciences ,02 engineering and technology ,Condensed Matter::Mesoscopic Systems and Quantum Hall Effect ,01 natural sciences ,Facility location problem ,Computer Science Applications ,Combinatorics ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Theory of computation ,Hardware_INTEGRATEDCIRCUITS ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,020201 artificial intelligence & image processing ,Mathematics - Abstract
We present a $$(20+{5}/{n})$$(20+5/n)-approximation algorithm for the non-uniform soft capacitated k-facility location problem, violating the capacitated constrains by no more than a factor of 25. The main technique is based on the primal---dual algorithm for the soft capacitated facility location problem, and the exploitation of the combinatorial structure of the fractional solution for the soft capacitated k-facility location problem.
- Published
- 2017
17. Preface
- Author
-
Bo Chen, Dachuan Xu, and Guochuan Zhang
- Subjects
Mathematical optimization ,Control and Optimization ,Computational Theory and Mathematics ,Computer science ,Applied Mathematics ,Discrete Mathematics and Combinatorics ,Combinatorial optimization ,Computer Science Applications - Published
- 2021
18. A local search approximation algorithm for the uniform capacitated k-facility location problem
- Author
-
Donglei Du, Dongmei Zhang, Dachuan Xu, and Lu Han
- Subjects
Mathematical optimization ,021103 operations research ,Control and Optimization ,Computer science ,Applied Mathematics ,0211 other engineering and technologies ,Approximation algorithm ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Facility location problem ,Computer Science Applications ,Set (abstract data type) ,Constraint (information theory) ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,1-center problem ,Theory of computation ,Discrete Mathematics and Combinatorics ,Cardinality (SQL statements) ,Local search (constraint satisfaction) - Abstract
In the uniform capacitated k-facility location problem (UC-k-FLP), we are given a set of facilities and a set of clients. Every client has a demand. Every facility have an opening cost and an uniform capacity. For each client–facility pair, there is an unit service cost to serve the client with unit demand by the facility. The total demands served by a facility cannot exceed the uniform capacity. We want to open at most k facilities to serve all the demands of the clients without violating the capacity constraint such that the total opening and serving cost is minimized. The main contribution of this work is to present the first combinatorial bi-criteria approximation algorithm for the UC-k-FLP by violating the cardinality constraint.
- Published
- 2017
19. An approximation algorithm for k-facility location problem with linear penalties using local search scheme
- Author
-
Yishui Wang, Dachuan Xu, Chenchen Wu, and Donglei Du
- Subjects
Control and Optimization ,business.industry ,Applied Mathematics ,Contrast (statistics) ,Approximation algorithm ,0102 computer and information sciences ,02 engineering and technology ,Extension (predicate logic) ,01 natural sciences ,Facility location problem ,Computer Science Applications ,Combinatorics ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Scheme (mathematics) ,Theory of computation ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,020201 artificial intelligence & image processing ,Local search (optimization) ,business ,Mathematics - Abstract
In this paper, we consider an extension of the classical facility location problem, namely k-facility location problem with linear penalties. In contrast to the classical facility location problem, this problem opens no more than k facilities and pays a penalty cost for any non-served client. We present a local search algorithm for this problem with a similar but more technical analysis due to the extra penalty cost, compared to that in Zhang (Theoretical Computer Science 384:126–135, 2007). We show that the approximation ratio of the local search algorithm is $$2 + 1/p + \sqrt{3+ 2/p+ 1/p^2} + \epsilon $$ , where $$p \in {\mathbb {Z}}_+$$ is a parameter of the algorithm and $$\epsilon >0$$ is a positive number.
- Published
- 2016
20. Approximation algorithms for precedence-constrained identical machine scheduling with rejection
- Author
-
Xianzhao Zhang, Dachuan Xu, Donglei Du, and Chenchen Wu
- Subjects
Mathematical optimization ,Machine scheduling ,021103 operations research ,Control and Optimization ,Job shop scheduling ,Linear programming ,Computer science ,Applied Mathematics ,Rounding ,0211 other engineering and technologies ,Approximation algorithm ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Computer Science Applications ,Scheduling (computing) ,Submodular set function ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Theory of computation ,Discrete Mathematics and Combinatorics - Abstract
We study a precedence-constrained identical parallel machine scheduling problem with rejection. There is a communication delay between any two jobs connected in the precedence network where jobs may be rejected with penalty. The goal is to minimize the sum of the makespan and the rejection cost. We propose two 3-approximation algorithms for this problem under linear and submodular rejection costs respectively. These two algorithms are both based on linear programming rounding technique.
- Published
- 2016
21. An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding
- Author
-
Dachuan Xu, Donglei Du, Wenqing Xu, and Chenchen Wu
- Subjects
Semidefinite embedding ,Semidefinite programming ,Mathematical optimization ,021103 operations research ,Control and Optimization ,Linear programming ,Applied Mathematics ,Rounding ,0211 other engineering and technologies ,Graph partition ,Approximation algorithm ,0102 computer and information sciences ,02 engineering and technology ,Function (mathematics) ,01 natural sciences ,Computer Science Applications ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Discrete Mathematics and Combinatorics ,Combinatorial optimization ,Mathematics - Abstract
Graph partition problems have been investigated extensively in combinatorial optimization. In this work, we consider an important graph partition problem which has applications in the design of VLSI circuits, namely, the balanced Max-3-Uncut problem. We formulate the problem as a discrete linear program with complex variables and propose an approximation algorithm with an approximation ratio of 0.3456 using a semidefinite programming rounding technique along with a greedy swapping step afterwards to guarantee the balanced constraint. Our analysis utilizes a bivariate function, rather than the univariate function in previous work.
- Published
- 2015
22. An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems
- Author
-
Chenchen Wu, Dachuan Xu, and Donglei Du
- Subjects
Semidefinite programming ,Discrete mathematics ,Class (set theory) ,Control and Optimization ,Applied Mathematics ,Rounding ,Approximation algorithm ,Computer Science Applications ,Combinatorics ,Computational Theory and Mathematics ,Theory of computation ,Discrete Mathematics and Combinatorics ,Graph bisection ,Mathematics - Abstract
We present a unified semidefinite programming hierarchies rounding approximation algorithm for a class of maximum graph bisection problems with improved approximation ratios. Under the above algorithmic framework, we show that the approximation ratios of Max- $$\frac{n}{2}$$ n 2 -cut, Max- $$\frac{n}{2}$$ n 2 -dense-subgraph, and Max- $$\frac{n}{2}$$ n 2 -vertex-cover are equal to those of Max- $$\frac{n}{2}$$ n 2 -uncut, Max- $$\frac{n}{2}$$ n 2 -directed-cut, and Max- $$\frac{n}{2}$$ n 2 -directed-uncut, respectively.
- Published
- 2013
23. A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties
- Author
-
Naihua Xiu, Donglei Du, Dachuan Xu, and Yu Li
- Subjects
Mathematical optimization ,Control and Optimization ,Linear programming ,Applied Mathematics ,Approximation algorithm ,Facility location problem ,Computer Science Applications ,Submodular set function ,Dual (category theory) ,Computational Theory and Mathematics ,1-center problem ,Theory of computation ,Discrete Mathematics and Combinatorics ,Mathematics - Abstract
In this paper, we study two variants of the classical facility location problem, namely, the facility location problem with linear penalties (FLPLP) and the facility location problem with submodular penalties (FLPSP), respectively. We give a unified dual-fitting based approximation algorithm for these two problems, yielding approximation ratios 2 and 3 respectively.
- Published
- 2012
24. Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems
- Author
-
Donglei Du, Zi Xu, and Dachuan Xu
- Subjects
Semidefinite programming ,Discrete mathematics ,Control and Optimization ,Applied Mathematics ,Approximation algorithm ,Disjoint sets ,Function (mathematics) ,Convexity ,Computer Science Applications ,Combinatorics ,Range (mathematics) ,Computational Theory and Mathematics ,Theory of computation ,Discrete Mathematics and Combinatorics ,Relaxation (approximation) ,Mathematics - Abstract
We consider the max-bisection problem and the disjoint 2-catalog segmentation problem, two well-known NP-hard combinatorial optimization problems. For the first problem, we apply the semidefinite programming (SDP) relaxation and the RPR2 technique of Feige and Langberg (J. Algorithms 60:1---23, 2006) to obtain a performance curve as a function of the ratio of the optimal SDP value over the total weight through finer analysis under the assumption of convexity of the RPR2 function. This ratio is shown to be in the range of [0.5,1]. The performance curve implies better approximation performance when this ratio is away from 0.92, corresponding to the lowest point on this curve with the currently best approximation ratio of 0.7031 due to Feige and Langberg (J. Algorithms 60:1---23, 2006). For the second problem, similar technique results in an approximation ratio of 0.7469, improving the previously best known result 0.7317 due to Wu et al. (J. Ind. Manag. Optim. 8:117---126, 2012).
- Published
- 2012
25. An approximation algorithm for the k-level capacitated facility location problem
- Author
-
Donglei Du, Dachuan Xu, and Xing Wang
- Subjects
Mathematical optimization ,Control and Optimization ,Supply chain management ,business.industry ,Applied Mathematics ,Approximation algorithm ,Facility location problem ,Performance factor ,Computer Science Applications ,Computational Theory and Mathematics ,1-center problem ,Theory of computation ,Discrete Mathematics and Combinatorics ,Combinatorial optimization ,Local search (optimization) ,business ,Mathematics - Abstract
We consider the k-level capacitated facility location problem (k-CFLP), which is a natural variant of the classical facility location problem and has applications in supply chain management. We obtain the first (combinatorial) approximation algorithm with a performance factor of $k+2+\sqrt{k^{2}+2k+5}+\varepsilon$ (?>0) for this problem.
- Published
- 2009
26. A local search approximation algorithm for a squared metric k-facility location problem.
- Author
-
Dongmei Zhang, Dachuan Xu, Yishui Wang, Peng Zhang, and Zhenning Zhang
- Abstract
In this paper, we introduce a squared metric k-facility location problem (SM-k-FLP) which is a generalization of the squared metric facility location problem and k-facility location problem (k-FLP). In the SM-k-FLP, we are given a client set C and a facility set F from a metric space, a facility opening cost fi ≥ 0 for each i ∈ F, and an integer k. The goal is to open a facility subset F ⊆ F with |F| ≤ k and to connect each client to the nearest open facility such that the total cost (including facility opening cost and the sum of squares of distances) is minimized. Using local search and scaling techniques, we offer a constant approximation algorithm for the SM-k-FLP. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.