检索结果-南通市图书馆

维普期刊数据库

An approximation algorithm for lower-bounded k-median with constant factor

在线全文

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2022年第4期65卷 93-101页

作者： Xiaoliang WU Feng SHI Yutian GUO Zhen ZHANG Junyu HUANG Jianxin WANG School of Computer Science and Engineering Central South University Hunan Provincial Key Lab on Bioinformatics Central South University School of Frontier Crossover Studies Hunan University of Technology and Business

The lower-bounded k-median problem plays a key role in many applications related to privacy protection, which requires that the amount of assigned client to each facility should not be less than the requirement. Unfortunately, the lower-bounded clustering problem remains elusive under the widely studied k-median objective. Within this paper, we convert this problem to the capacitated facility location problem and successfully give a(516+ε)-approximation for this problem.

关键词： approximation algorithm approximation algorithm $k$-median lower-bounded $k$-median

A Tight approximation algorithm for Multi-Vehicle CVRP with Unsplittable Demands on a Line

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Journal of Systems Science & Complexity 2022年第5期35卷 1902-1909页

作者： WU Yuanxiao LU Xiwen School of Science East China University of Science and TechnologyShanghai 200237China

In this paper,the authors study the multi-vehicle capacitated vehicle routing problem on a line-shaped network with unsplittable demand.The objective is to find a transportation scheme to minimize the longest distance traveled by a single vehicle such that all the customers are served without violating the capacity constraint.The authors show that this problem has no polynomialtime algorithm with performance ratio less than 2 on condition that P≠NP,and then provide a 2-approximation algorithm.

关键词： approximation algorithm network unsplittable demand vehicle routing worst-case analysis

维普期刊数据库

A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties

在线全文

学校读者我要写书评

暂无评论

Frontiers of Computer Science 2023年第3期17卷 125-132页

作者： Xiaofei LIU Weidong LI Jinhua YANG School of Information Science and Engineering Yunnan UniversityKunming 650500China School of Mathematics and Statistics Yunnan UniversityKunming 650500China Dianchi College of Yunnan University Kunming 650228China

In this paper,we consider the-prize-collecting minimum vertex cover problem with submodular penalties,which generalizes the well-known minimum vertex cover problem,minimum partial vertex cover problem and minimum vertex cover problem with submodular penalties.We are given a cost graph and an integer.This problem determines a vertex set such that covers at least edges.The objective is to minimize the total cost of the vertices in plus the penalty of the uncovered edge set,where the penalty is determined by a submodular function.We design a two-phase combinatorial algorithm based on the guessing technique and the primal-dual framework to address the problem.When the submodular penalty cost function is normalized and nondecreasing,the proposed algorithm has an approximation factor of.When the submodular penalty cost function is linear,the approximation factor of the proposed algorithm is reduced to,which is the best factor if the unique game conjecture holds.

关键词： vertex cover k-prize-collecting primal-dual approximation algorithm

An approximation algorithm for P-prize-collecting Set Cover Problem

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Journal of the Operations Research Society of China 2023年第1期11卷 207-217页

作者： Jin-Shuang Guo Wen Liu Bo Hou School of Mathematical Sciences Hebei Key Laboratory of Computational Mathematics and ApplicationsHebei Normal UniversityShijiazhuang050024HebeiChina

In this paper,we consider the P-prize-collecting set cover(P-PCSC)problem,which is a generalization of the set cover problem.In this problem,we are given a set system(U,S),where U is a ground set and S⊆2U is a collection of subsets satisfying∪S∈SS=U.Every subset in S has a nonnegative cost,and every element in U has a nonnegative penalty cost and a nonnegative profit.Our goal is to find a subcollection C⊆S such that the total cost,consisting of the cost of subsets in C and the penalty cost of the elements not covered by C,is minimized and at the same time the combined profit of the elements covered by C is at least P,a specified profit bound.Our main work is to obtain a 2f+ε-approximation algorithm for the P-PCSC problem by using the primal-dual and Lagrangian relaxation methods,where f is the maximum frequency of an element in the given set system(U,S)andεis a fixed positive number.

关键词： P-prize-collecting set cover problem approximation algorithm Primal-dual Lagrangian relaxation

approximation algorithm for Weighted Weak Vertex Cover

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Journal of Computer Science & Technology 2004年第6期19卷 782-786页

作者： YongZhang HongZhu DepartmentofComputerScienceandEngineering FudanUniversityShanghai200433P.R.China LaboratoryforIntelligentInformationProcessing FudanUniversityShanghai200433P.R.China

The problem of efficiently monitoring the network flow is regarded as the problem to find out the minimum weighted weak vertex cover set for a given graphG=(V,E). In this paper, we give an approximation algorithm to solve it, which has the approximation ratio lnd+1, whered is the maximum degree of the vertex in graphG, and improve the previous work. Keywords weak vertex cover - NP-hard - approximation algorithm NoteThis work is supported by the Ministry of Science and Technology of China (Grant No.2001CCA03000), the National Natural Science Foundation of China (Grant No.60273045), and the Shanghai Science and Technology Development Foundation (Grant No.025115032).

关键词： weak vertex cover NP-hard approximation algorithm

approximation algorithm for Bottleneck Steiner Tree Problem in the Euclidean Plane

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Journal of Computer Science & Technology 2004年第6期19卷 791-794页

作者： Zi-MaoLi Da-MingZhu Shao-HanMa SchoolofComputerScienceandTechnology ShandongUniversityJinan250061P.R.China

A special case of the bottleneck Steiner tree problem in the Euclidean plane was considered in this paper. The problem has applications in the design of wireless communication networks, multifacility location, VLSI routing and network routing. For the special case which requires that there should be no edge connecting any two Steiner points in the optimal solution, a 3-restricted Steiner tree can be found indicating the existence of the performance ratio root2. In this paper, the special case of the problem is proved to be NP-hard and cannot be approximated within ratio root2. First a simple polynomial time approximation algorithm with performance ratio root3 is presented. Then based on this algorithm and the existence of the 3-restricted Steiner tree, a polynomial time approximation algorithm with performance ratio-root2 + epsilon is proposed, for any epsilon > 0.

关键词： bottleneck Steiner tree approximation algorithm performance ratio algorithm design and analysis

Robust Correlation Clustering Problem with Locally Bounded Disagreements

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Tsinghua Science and Technology 2024年第1期29卷 66-75页

作者： Sai Ji Min Li Mei Liang Zhenning Zhang Institute of Mathematics Hebei University of TechnologyTianjin 300401China School of Mathematics and Statistics Shandong Normal UniversityJinan 250358China College of Statistics and Data Science Beijing University of TechnologyBeijing 100124China Department of Operations Research and Information Engineering Beijing University of TechnologyBeijing 100124China

Min-max disagreements are an important generalization of the correlation clustering problem(CorCP).It can be defined as follows.Given a marked complete graph G=(V,E),each edge in the graph is marked by a positive label"+"or a negative label"_"based on the similarity of the connected vertices.The goal is to find a clustering C of vertices V,so as to minimize the number of disagreements at the vertex with the most disagreements.Here,the disagreements are the positive cut edges and the negative non-cut edges produced by clustering C.This paper considers two robust min-max disagreements:min-max disagreements with outliers and min-max disagreements with penalties.Given parameter δ∈(0,1/14),we first provide a threshold-based iterative clustering algorithm based on LP-rounding technique,which is a(1/δ,7/(1-14δ))-bi-criteria approximation algorithm for both the min-max disagreements with outliers and the min-max disagreements with outliers on one-sided complete bipartite graphs.Next,we verify that the above algorithm can achieve an approximation ratio of 21 for min-max disagreements with penalties when we set parameter δ=1/21.

关键词： min-max disagreements outliers penalties approximation algorithm LP-rounding

approximation algorithm FOR MAX-BISECTION PROBLEM WITH THE POSITIVE SEMIDEFINITE RELAXATION

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Journal of Computational Mathematics 2003年第3期21卷 357-366页

作者： Da-chuan Xu Ji-ye Han(Institute of Applied Mathematics, Academy of Mathematics and System Sciences, Chinese Academyof Sciences, Beijing 100080, China) Institute of Applied Mathematics Academy of Mathematics and System Sciences Chinese Academy of Sciences 北京 100080

Using outward rotations, we obtain an approximation algorithm for Max-Bisection problem, i.e., partitioning the vertices of an undirected graph into two blocks of equal cardinality so as to maximize the weights of crossing edges. In many interesting cases, the algorithm performs better than the algorithms of Ye and of Halperin and Zwick. The main tool used to obtain this result is semidefinite programming.

关键词： approximation algorithm Max-Bisection problem Semidefinite programming approximation ratio.

维普期刊数据库

approximation algorithm for minimizing relay node placement in wireless sensor networks

在线全文

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2010年第11期53卷 2332-2342页

作者： LU KeZhong1,2, CHEN GuoLiang1,2, FENG YuHong1,2, LIU Gang1,2 & MAO Rui1,2 1College of Computer Science and Software Engineering, Shenzhen University, Shenzhen 518060, China 2National High Performance Computing Center at Shenzhen, Shenzhen 518060, China College of Computer Science and Software Engineering Shenzhen University Shenzhen China National High Performance Computing Center at Shenzhen Shenzhen China

To eliminate the routing load unbalance among sensor nodes, one approach is to deploy a small number of powerful relay nodes acting as routing nodes in wireless sensor networks, the major optimization objective of which is to minimize the number of relay nodes required. In this paper, we prove that the relay node placement problem in a bounded plane is a P problem, but its computational complexity in general case is quite great. From the geometric cover feature of the relay node placement problem, an O(n2 log n) time greedy approximation algorithm is proposed, where n is the number of sensor nodes. Particularly, at each stage of this algorithm’s iterative process, we first select a critical node from uncovered sensor nodes, and then determine the location of relay node based on the principle of preferring to cover the sensor node closer to the critical node, so as to prevent the emergence of isolated node. Experiment results indicate that our proposed algorithm can generate a near optimum feasible relay node deployment in a very short time, and it outperforms existing algorithms in terms of both the size of relay node deployment and the execution time.

关键词： wireless sensor network relay node placement geometrical cover approximation algorithm greedy algorithm