检索结果-南通市图书馆

An Improved Approximation Algorithm for the k-Level Facility Location Problem with Soft Capacities

在线全文

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 2017年第4期33卷 1015-1024页

作者： Chen-chen WU da-chuan xu College of Science Tianjin 300384 China Department of Information and Operations Research College of Applied Sciences Beijing University of Tech-nology Beijing 100124 China

We consider the k-level facility location problem with soft capacities （k-LFLPSC）. In the k- LFLPSC, each facility i has a soft capacity ui along with an initial opening cost fi ≥O, i.e., the capacity of facility i is an integer multiple of ui incurring a cost equals to the corresponding multiple of fi. We firstly propose a new bifactor （ln（1/β）/（1 -β）, 1 ＋ 2/（1 - β））-approximation algorithm for the k-level facility location problem （k-LFLP）, where β∈（0, 1） is a fixed constant. Then, we give a reduction from the k-LFLPSC to the k-LFLP. The reduction together with the above bifactor approximation algorithm for the k-LFLP imply a 5.5053-approximation algorithm for the k-LFLPSC which improves the previous 6-approximation.

关键词： facility location approximation algorithm soft capacity

Robust Solutions of Uncertain Complex-valued Quadratically Constrained Programs

在线全文

学校读者我要写书评

暂无评论

Acta Mathematica Sinica,English Series 2008年第8期24卷 1279-1290页

作者： da chuan xu Zheng Hai HUANG Department of Applied Mathematics College of Applied Sciences Beijing University of Technology 100 Pingleyuan Chaoyang District Beijing 100022 P. R. China Department of Mathematics School of Science Tianjin University Tianjin 300072 P. R. China

In this paper, we discuss complex convex quadratically constrained optimization with uncertain data. Using S-Lemma, we show that the robust counterpart of complex convex quadratically constrained optimization with ellipsoidal or intersection-of-two-ellipsoids uncertainty set leads to a complex semidefinite program. By exploring the approximate S-Lemma, we give a complex semidefinite program which approximates the NP-hard robust counterpart of complex convex quadratic optimization with intersection-of-ellipsoids uncertainty set.

关键词： robust optimization quadratically constrained program complex semidefinite program S-Lemma

Nonlinear Extrapolation Estimates of π

在线全文

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 2024年第1期40卷 91-108页

作者： Wen-qing xu Sha-sha Wang da-chuan xu Beijing Institute for Scientific and Engineering Computing Beijing University of TechnologyBeijing100124China Department of Mathematics and Statistics California State UniversityLong BeachCalifornia90840USA Department of Mathematics and Physics Shijiazhuang Tiedao UniversityShijiazhuang050043China

The classical Archimedean approximation of π uses the semiperimeter or area of regular polygons inscribed in or circumscribed about a unit circle in R~2 and it is well-known that by using linear combinations of these basic estimates,modern extrapolation techniques can greatly speed up the approximation ***,when n vertices are randomly selected on the circle,the semiperimeter and area of the corresponding random inscribed and circumscribing polygons are known to converge to π almost surely as n→∞,and by further applying extrapolation processes,faster convergence rates can also be achieved through similar linear combinations of the semiperimeter and area of these random *** this paper,we further develop nonlinear extrapolation methods for approximating π through certain nonlinear functions of the semiperimeter and area of such *** focus on two types of extrapolation estimates of the forms χ_n=S_n~αA_n~β and Y_n(p)=(αS_n~p+βA_n~p)~(1/p) where α+β=1,p≠0,and Sn and An respectively represents the semiperimeter and area of a random n-gon inscribed in the unit circle in R~2,and Xn may be viewed as the limit of Y_n(p) when p→*** deriving probabilistic asymptotic expansions with carefully controlled error estimates for Xn and Y_n(p),we show that the choice α=4/3,β=-1/3 minimizes the approximation error in both cases,and their distributions are also asymptotically normal.

关键词： Archimedean polygons random polygons approximations ofπ extrapolation processes asymptotic convergence

Fault-tolerant Concave Facility Location Problem with Uniform Requirements

在线全文

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 2012年第3期28卷 475-484页

作者： Xing WANG da-chuan xu Zheng-Hai HUANG Department of Mathematics School of ScienceTianjin UniversityTianjin 300072China Department of Applied Mathematics Beijing University of TechnologyBeijing 100124China

In this paper, we consider the fault-tolerant concave facility location problem （FTCFL） with uniform requirements. By investigating the structure of the FTCFL, we obtain a modified dual-fitting bifactor approximation algorithm. Combining the scaling and greedy argumentation technique, the approximation factor is proved to be 1.52.

关键词： approximation algorithm facility location problem dual-fitting

An Almost Tight Lower Bound for the Scheduling Problem to Meet Two Min-Sum Objectives

在线全文

学校读者我要写书评

暂无评论

Journal of the Operations Research Society of China 2013年第1期1卷 159-161页

作者： Dong-lei Du da-chuan xu Faculty of Business Administration University of New BrunswickNew BrunswickCanada E3B 9Y2 Department of Applied Mathematics Beijing University of Technology100 PingleyuanChaoyang DistrictBeijing 100124P.R.China

In this note,we provide an almost tight lower bound for the scheduling problem to meet two min-sum objectives considered by Angel et *** ***.35(1):69–73,2007.

关键词： Bi-criteria Scheduling Approximation algorithm

Local search yields a PTAS for fixed-dimensional k-means problem with penalties

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Journal of the Operations Research Society of China 2024年第2期12卷 351-362页

作者： Fan Yuan da-chuan xu Dong-Lei Du Dong-Mei Zhang Beijing Institute for Scientific and Engineering Computing Beijing University of TechnologyBeijing 100124China Faculty of Management University of New BrunswickFrederictonNB E3B 9Y2Canada School of Computer Science and Technology Shandong Jianzhu UniversityJinan 250101ShandongChina

We study a problem called the k-means problem with penalties(k-MPWP),which is a natural generalization of the typical k-means *** this problem,we have a set D of client points in R^(d),a set F of possible centers in R^(d),and a penalty cost Pj>O for each point j∈*** are also given an integer k which is the size of the center point *** want to find a center point set S■F with size k,choose a penalized subset of clients P■D,and assign every client in D\P to its open *** goal is to minimize the sum of the squared distances between every point in D\P to its assigned centre point and the sum of the penalty costs for all clients in *** using the multi-swap local search technique and under the fixed-dimensional Euclidean space setting,we present a polynomial-time approximation scheme(PTAS)for the k-MPWP.

关键词： Approximation algorithm k-means Local search Penalty

Simultaneous Approximation of Multi-criteria Submodular Function Maximization

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Journal of the Operations Research Society of China 2014年第3期2卷 271-290页

作者： Dong-Lei Du Yu Li Nai-Hua Xiu da-chuan xu Faculty of Business Administration University of New BrunswickFrederictonNB E3B 9Y2Canada Department of Mathematics School of ScienceBeijing Jiaotong University3 ShangyuancunHaidian DistrictBeijing 100044China Department of Applied Mathematics Beijing University of Technology100 PingleyuanChaoyang DistrictBeijing 100124China

Recently intensive interest has been raised on approximation of the NPhard submodular maximization problem due to their theoretical and practical *** this work,we extend this line of research by focusing on the simultaneous approximation of multiple submodular function *** address the existence and nonexistence results for both deterministic and randomized approximation when the submodular functions are symmetric and asymmetric,respectively,along with algorithmic *** offer complete characterization of the symmetric case and partial results on the asymmetric case.

关键词： Multi-criteria Submodular function maximization Approximation algorithm Existence

A Primal-Dual Algorithm for the Generalized Prize-Collecting Steiner Forest Problem

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Journal of the Operations Research Society of China 2017年第2期5卷 219-231页

作者： Lu Han da-chuan xu Dong-Lei Du Chen-Chen Wu Department of Information and Operations Research Beijing University of TechnologyBeijing 100124China Faculty of Business Administration University of New BrunswickFrederictonNB E3B 5A3Canada College of Science Tianjin University of TechnologyTianjin 300384China

In this paper,we consider the generalized prize-collecting Steiner forest problem,extending the prize-collecting Steiner forest *** this problem,we are given a connected graph G=(V,E)and a set of vertex sets V={V1,V2,…,Vl}.Every edge in E has a nonnegative cost,and every vertex set in V has a nonnegative penalty *** a given edge set F⊆E,vertex set Vi∈V is said to be connected by edge set F if Vi is in a connected component of the F-spanned *** objective is to find such an edge set F such that the total edge cost in F and the penalty cost of the vertex sets not connected by F is *** main contribution is to give a 3-approximation algorithm for this problem via the primal-dual method.

关键词： Prize-collecting Steiner forest Approximation algorithm Primal-dual

A Note on Submodularity Preserved Involving the Rank Functions

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Journal of the Operations Research Society of China 2019年第3期7卷 399-407页

作者： Min Li Dong-Lei Du da-chuan xu Zhen-Ning Zhang School of Mathematics and Statistics Shandong Normal UniversityJinan 250358China Faculty of Business Administration University of New BrunswickFrederictonCanada College of Applied Sciences Beijing University of TechnologyBeijing 100124China

In many kinds of games with economic significance,it is very important to study the submodularity of *** this paper,wemainly study the problem of maximizing a concave function over an intersection of two *** obtain that the submod-ularity may not be preserved,but it involves one maximal submodular problem(or minimal supermodular problem)with some ***,we also present examples showing that these conditions can be satisfied.

关键词： Matroid Submodular function Rank function Convexclosure Game