检索结果-内蒙古大学图书馆

approximation algorithm for prize-collecting vertex cover with fairness constraints

JOURNAL OF COMBINATORIAL OPTIMIZATION 2024年第3期48卷 1-18页

作者： Zhou, Mingchao Zhang, Zhao Du, Ding-Zhu Zhejiang Normal Univ Sch Math Sci Jinhua 321004 Zhejiang Peoples R China Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

Considering fairness has become increasingly important in recent research. This paper proposes the prize-collecting vertex cover problem with fairness constraints (FPCVC). In a prize-collecting vertex cover problem, those edges that are not covered incur penalties. By adding fairness concerns into the problem, the vertex set is divided into l groups, the goal is to find a vertex set to minimize the cost-plus-penalty value under the constraints that the profit of edges collected by each group exceeds a coverage requirement. In this paper, we propose a hybrid algorithm (combining deterministic rounding and randomized rounding) for the FPCVC problem which, with probability at least 1-1/l alpha\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1-1/l<^>{\alpha }$$\end{document}, returns a feasible solution with an objective value at most 9(alpha+1)2lnl+3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left( \frac{9(\alpha +1)}{2}\ln l+3\right) $$\end{document} times that of an optimal solution, where alpha\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha $$\end{document} is a constant. We also show a lower bound of Omega(lnl)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega (\ln l)$$\end{document} for the approximability of FPCVC. Thus, our approxima

关键词： Prize collecting vertex cover Fairness constraints approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm for minimum weight connected-k-subgraph cover

引用

THEORETICAL COMPUTER SCIENCE 2020年 838卷 160-167页

作者： Liu, Pengcheng Zhang, Zhao Huang, Xiaohui Zhejiang Normal Univ Coll Math & Comp Sci Jinhua 321004 Zhejiang Peoples R China Zhejiang Normal Univ Lib & Informat Ctr Jinhua 321004 Zhejiang Peoples R China

For a given graph G, the minimum weight connected-k-subgraph cover problem (MinWCkSC) is to find a minimum weight vertex subset C of G such that each connected subgraph of G on k vertices contains at least one vertex of C. Previously, Zhang et al. [37] presented a (k - 1)-approximation algorithm for MinWCkSC under the assumption that the girth of G, which is the length of a shortest cycle of G, is at least k. In this paper, we improve this result by showing that (k - 1)-approximation can be achieved when the girth requirement is relaxed from k to 2k/3. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Connected-k-subgraph cover approximation algorithm Girth

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm for the multicovering problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2021年第2期41卷 433-450页

作者： Gorgi, Abbass El Ouali, Mourad Srivastav, Anand Hachimi, Mohamed Univ Ibn Zohr Agadir Morocco Univ Kiel Kiel Germany

Let H = (V, epsilon) be a hypergraph with maximum edge size l and maximum degree Delta. For a given positive integers b(v), v is an element of V, a set multicover in H is a set of edges C subset of epsilon such that every vertex v in V belongs to at least b(v) edges in C. Set multicover is the problem of finding a minimum-cardinality set multicover. Peleg, Schechtman and Wool conjectured that for any fixed Delta and b := min(v is an element of V) b(v), the problem of set multicover is not approximablewithin a ratio less than delta :=Delta-b+1, unlessP = NP. Hence it's a challenge to explore for which classes of hypergraph the conjecture doesn't hold. We present a polynomial time algorithm for the set multicover problem which combines a deterministic threshold algorithm with conditioned randomized rounding steps. Our algorithm yields an approximation ratio of max {148/149 delta, (1 - (b-1)e(delta/4)/94l)delta} for b >= 2 and delta >= 3. Our result not only improves over the approximation ratio presented by El Ouali et al. (algorithmica 74:574, 2016) but it's more general since we set no restriction on the parameter l. Moreover we present a further polynomial time algorithm with an approximation ratio of 5/6 delta for hypergraphs with l <= (1 + epsilon)(l) over bar for any fixed epsilon is an element of [0, 1/2], where (l) over bar is the average edge size. The analysis of this algorithm relies on matching/covering duality due to Ray-Chaudhuri (1960), which we convert into an approximative form. The second performance disprove the conjecture of Peleg et al. for a large subclass of hypergraphs.

关键词： Integer linear programs Hypergraphs approximation algorithm Randomized rounding Set cover and set multicover k-matching

来源：评论

学校读者我要写书评

暂无评论

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 Note This 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 receiver interference problem in dual power Wireless Sensor Networks

引用

JOURNAL OF APPLIED MATHEMATICS AND COMPUTING 2019年第1-2期61卷 87-99页

作者： Shetty, D. Pushparaj Lakshmi, M. Prasanna Natl Inst Technol Dept Math & Computat Sci Surathkal 575025 Karnataka India

The problem of assigning power levels to the nodes of a wireless sensor network from a given a set of two power levels is called Dual power management problem and the underlying network is called Dual power network. We consider the problem of minimizing the maximum receiver interference of such a network. The interference disrupts the communication and forces the data packets to be retransmitted. The motivation is to conserve the energy by minimizing the interference and maintaining the connectivity of the dual power network. Receiver interference problem is proved to be NP-hard. In this paper, an approximation algorithm is derived for minimizing the maximum receiver interference of a dual power network by utilizing the approximation algorithm for Dual Power Management Problem. The proposed algorithm is supported by the simulation results. We term this problem as Dual Power Receiver Interference Problem and show that it is NP-complete using a polynomial time reduction from Degree Constrained Minimum Spanning Tree problem. We also prove the NP-completeness of Dual Power Management Problem by a polynomial reduction from Vertex Cover Problem.

关键词： Wireless sensor network Receiver interference Range assignment Dual power assignment approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm WITH CONSTANT RATIO FOR STOCHASTIC PRIZE-COLLECTING STEINER TREE PROBLEM

引用

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION 2021年第5期18卷 3351-3363页

作者： Sun, Jian Sheng, Haiyun Sun, Yuefang DU, Donglei Zhang, Xiaoyan Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China Nanjing Normal Univ Sch Math Sci Nanjing 210023 Jiangsu Peoples R China Nanjing Normal Univ Inst Math Nanjing 210023 Jiangsu Peoples R China Ningbo Univ Sch Math & Stat Ningbo 315211 Zhejiang Peoples R China Univ New Brunswick Fac Management Fredericton NB E3B 5A3 Canada

Steiner tree problem is a typical NP-hard problem, which has vast application background and has been an active research topic in recent years. Stochastic optimization problem is an important branch in the field of optimiza-tion. Compared with deterministic optimization problem, it is an optimization problem with random factors, and requires the use of tools such as probability and statistics, stochastic process and stochastic analysis. In this paper, we study a two-stage finite-scenario stochastic prize-collecting Steiner tree prob-lem, where the goal is to minimize the sum of the first stage cost, the expected second stage cost and the expected penalty cost. Our main contribution is to present a primal-dual 3-approximation algorithm for this problem.

关键词： Prize-collecting Steiner tree combinatorial optimization stochastic optimization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm for minimizing total latency in machine scheduling with deliveries

引用

DISCRETE OPTIMIZATION 2008年第1期5卷 97-107页

作者： Levin, Asaf Penn, Michal Hebrew Univ Jerusalem Dept Stat IL-91905 Jerusalem Israel Technion Israel Inst Technol Fac Ind Engn & Management IL-32000 Haifa Israel

We study the problem Of MINIMIZING TOTAL LATENCY IN MACHINE SCHEDULING WITH DELIVERIES, which is defined as follows. There is a set of n jobs to be processed by a single machine at a plant, where job J(i) is associated with its processing time and a customer i located at location i to which the job is to be delivered. In addition, there is a single uncapacitated delivery vehicle available. All jobs (vehicle) are available for processing (delivery) at time 0. Our aim is to determine the sequence in which the jobs should be processed in the plant, the departure times of the vehicle from the plant, and the routing of the vehicle, so as to minimize the total latency (job delivery time). We present a 6e similar to 16.309691-approximation algorithm for the problem. (C) 2007 Elsevier B.V. All rights reserved.

关键词： minimum latency scheduling approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm FOR SPHERICAL k-MEANS PROBLEM WITH PENALTY

引用

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION 2022年第4期18卷 2277-2287页

作者： Wu, Chenchen Lv, Wei Wang, Yujie Xu, Dachuan Nankai Univ Sch Business Tianjin 300071 Peoples R China Tianjin Univ Technol Coll Sci Tianjin 300384 Peoples R China Tianjin Renai Coll Comp Sci & Technol Dept Tianjin 306136 Peoples R China Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China

The k-means problem is a classical combinatorial optimization problem which has lots of applications in many fields such as machine learn-ing, data mining, etc. We consider a variant of k-means problem in the spherical space, that is, spherical k-means problem with penalties. In the problem, it is allowable that some nodes in the spherical space can not be clustered by paying some penalty costs. Based on local search scheme, we propose a (4(11 + 4 root 7) + epsilon)-approximation algorithm using singe-swap oper-ation, where E is a positive constant.

关键词： k-means local search algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm for the energy-aware profit maximizing problem in heterogeneous computing systems

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2019年 124卷 70-77页

作者： Li, Weidong Liu, Xi Cai, Xiaobo Zhang, Xuejie Yunnan Univ Sch Math & Stat Kunming 650504 Yunnan Peoples R China Yunnan Univ Sch Informat Sci & Engn Kunming 650504 Yunnan Peoples R China

Trade-offs between energy and performance are important for energy-aware scheduling. Recently, a novel model, called energy-aware profit maximizing scheduling problem (EAPM), which combines energy and makespan into the objective of maximizing the profit per unit of time has been proposed. The user pay a given price to have a bag-of-tasks processed and the objective is to maximize the profit per unit time. In this study, we design a polynomial-time algorithm for the EAPM problem. The execution time of our algorithm is polynomial in the number of task types which is an improvement over the previous algorithm, whose execution time is polynomial in the number of tasks. Moreover, we demonstrate that the approximation ratio of our algorithm is close to 2 for a special case, which may be the best result we can obtain. Experimental results show that our algorithm can produce a feasible solution with better objective value than the previous algorithm. (C) 2018 Published by Elsevier Inc.

关键词： Task scheduling High performance computing Load balancing approximation algorithm Bag-of-tasks

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm for maximum edge coloring

引用

THEORETICAL COMPUTER SCIENCE 2009年第11期410卷 1022-1029页

作者： Feng, Wangsen Zhang, Li'ang Wang, Hanpin Peking Univ Ctr Comp Minist Educ Key Lab Network & Software Secur Assurance Beijing 100871 Peoples R China Peking Univ Sch Elect Engn & Comp Sci Minist Educ Key Lab High Confidence Software Technol Beijing 100871 Peoples R China

We propose a polynomial time approximation algorithm for a novel maximum edge coloring problem which arises from wireless mesh networks [Ashish Raniwala, Tzi-cker Chiueh, Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network, in: INFOCOM 2005, pp. 2223-2234;Ashish Raniwala, Kartik Gopalan, Tzi-cker Chiueh, Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks, Mobile Comput. Commun. Rev. 8 (2) (2004) 50-65]. The problem is to color all the edges in a graph with maximum number of colors under the following q-Constraint: for every vertex in the graph, all the edges incident to it are colored with no more than q (q is an element of Z, q >= 2) colors. We show that the algorithm is a 2-approximation for the case q = 2 and a (1 + 4q-2/3q(2)-5q+2)-approximation for the case q > 2 respectively. The case q = 2 is of great importance in practice. For complete graphs and trees, polynomial time accurate algorithms are found for them when q = 2. The approximation algorithm gives a feasible solution to channel assignment in multi-channel wireless mesh networks. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Maximum edge coloring approximation algorithm Wireless mesh networks

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：