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

approximation algorithms and heuristics for task scheduling in data-intensive distributed systems

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2018年第5期25卷 1417-1441页

作者： Povoa, Marcelo G. Xavier, Eduardo C. Google Ave Andradas 3000 BR-30260070 Belo Hozitonte Brazil Univ Estadual Campinas Inst Comp Ave Albert Einstein 1251 BR-13083852 Campinas SP Brazil

In this work, we are interested in the problem of task scheduling on large-scale data-intensive computing systems. In order to achieve good performance, one must construct not only good task schedules but also good data allocation across nodes on the system, since before a task can be executed, it must have access to data distributed on the system. In this article, we present a general formulation of a static problem that combines both scheduling and replication problems in data-intensive distributed systems. We show that this problem does not admit an approximation algorithm. However, considering a restricted version of the problem that considers some practical constraints, an approximation algorithm can be designed. From a practical perspective, we introduce a novel heuristic for the problem that is based on nodes clustering. We compare the heuristic with two adapted approaches from other works in the literature by computational simulations using an extensive set of instances based on real computer grids. We show that our heuristic often obtains the best solutions and also runs faster than other approaches.

关键词： data grids task scheduling data replication approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for metric facility location problems

引用

SIAM JOURNAL ON COMPUTING 2006年第2期36卷 411-432页

作者： Mahdian, Mohammad Ye, Yinyu Zhang, Jiawei Microsoft Res Redmond WA 98052 USA Stanford Univ Sch Engn Dept Management Sci & Engn Stanford CA 94305 USA NYU Stern Sch Business IOMS Operat Management New York NY 10012 USA

In this paper we present a 1.52-approximation algorithm for the metric uncapacitated facility location problem, and a 2-approximation algorithm for the metric capacitated facility location problem with soft capacities. Both these algorithms improve the best previously known approximation factor for the corresponding problem, and our soft-capacitated facility location algorithm achieves the integrality gap of the standard linear programming relaxation of the problem. Furthermore, we will show, using a result of Thorup, that our algorithms can be implemented in quasi-linear time.

关键词： approximation algorithms facility location problem greedy method linear programming

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for the scaffolding problem and its generalizations

引用

THEORETICAL COMPUTER SCIENCE 2018年 734卷 131-141页

作者： Chen, Zhi-Zhong Harada, Youta Guo, Fei Wang, Lusheng Tokyo Denki Univ Div Informat Syst Design Hatoyama Saitama 3500394 Japan Tianjin Univ Sch Comp Sci & Technol Tianjin Peoples R China City Univ Hong Kong Dept Comp Sci 83 Tat Chee Ave Hong Kong Hong Kong Peoples R China Univ Hong Kong Shenzhen Res Inst Shenzhen Hitech Ind Pk Shenzhen Peoples R China

Scaffolding is one of the main stages in genome assembly. During this stage, we want to merge contigs assembled from the paired-end reads into bigger chains called scaffolds. For this purpose, the following graph-theoretical problem has been proposed: Given an edge-weighted complete graph G and a perfect matching D of G, we wish to find a Hamiltonian path P in G such that all edges of D appear in P and the total weight of edges in P but not in D is maximized. This problem is NP-hard and the previously best polynomial-time approximation algorithm for it achieves a ratio of 1/2. In this paper, we design a new polynomial-time approximation algorithm achieving a ratio of 5-5 is an element of/9-8 is an element of for any constant 0 < is an element of < 1. Several generalizations of the problem have also been introduced in the literature and we present polynomial-time approximation algorithms for them that achieve better approximation ratios than the previous bests. In particular, one of the algorithms answers an open question. (C) 2017 Elsevier B.V. All rights reserved.

关键词： approximation algorithms Randomized algorithms Scaffolding Matchings

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for solving the line-capacitated minimum Steiner tree problem

引用

JOURNAL OF GLOBAL OPTIMIZATION 2022年第3期84卷 687-714页

作者： Li, Jianping Wang, Wencheng Lichen, Junran Liu, Suding Pan, Pengxiang Yunnan Univ Dept Math East Outer Ring South Rd Kunming 650504 Yunnan Peoples R China Chinese Acad Sci Acad Math & Syst Sci Inst Appl Math 55 Zhongguancun East Rd Beijing 100190 Peoples R China Beijing Univ Chem Technol Sch Math & Phys 15 North Third Ring East Rd Beijing 100029 Peoples R China

In this paper, we address the line-capacitated minimum Steiner tree problem (the Lc-MStT problem, for short), which is a variant of the (Euclidean) capacitated minimum Steiner tree problem and defined as follows. Given a set X = (r(1), r(2),...,r(n)} of n terminals in R-2, a demand function d : X -> N and a positive integer C, we are asked to determine the location of a line l and a Steiner tree T-l to interconnect these n terminals in X and at least one point located on this line l such that the total demand of terminals in each maximal subtree (of TO connected to the line l, where the terminals in such maximal subtree are all located at the same side of this line l, does not exceed the bound C. The objective is to minimize total weight Sigma(e is an element of Tl) w(e) of such a Steiner tree T-l among all line-capacitated Steiner trees mentioned-above, where weight w(e) = 0 if two endpoints of that edge e is an element of T-l are located on the line l and otherwise weight w(e) is the Euclidean distance between two endpoints of that edge e is an element of T-l . In addition, when this line l is as an input in R-2 and Sigma(r is an element of X) d(r) <= C holds, we refer to this version as the 1-line-fixed minimum Steiner tree problem (the 1Lf-MStT problem, for short). We obtain three main results. (1) Given a rho(st )-approximation algorithm to solve the Euclidean minimum Steiner tree problem and a rho(1Lf)-approximation algorithm to solve the 1Lf-MStT problem, respectively, we design a (rho(st)rho(1Lf )+2)-approximation algorithm to solve the Lc-MStT problem. (2) Whenever demand of each terminal r is an element of X is less than c/2, we provide a (rho(1Lf) + 2)-approximation algorithm to resolve the Lc-MStT problem. (3) Whenever demand of each terminal r is an element of X is at least c/2, using the Edmonds' algorithm to solve the minimum weight perfect matching as a subroutine, we present an exact algorithm in polynomial time to resolve the Lc-MStT problem.

关键词： Combinatorial optimization Locations of lines Line-capacitated Steiner trees approximation algorithms Exact algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for the Vertex K-Center Problem: Survey and Experimental Evaluation

引用

IEEE ACCESS 2019年 7卷 109228-109245页

作者： Garcia-Diaz, Jesus Menchaca-Mendez, Rolando Menchaca-Mendez, Ricardo Hernandez, Saul Pomares Perez-Sansalvador, Julio Cesar Lakouari, Noureddine Consejo Nacl Ciencia & Technol Cdmx 03940 Mexico Inst Nacl Astrofis Opt & Electr Comp Sci Dept Puebla 72840 Mexico Ctr Invest Computac Mexico City 07738 DF Mexico CNRS LAAS F-31400 Toulouse France

The vertex k-center problem is a classical NP-Hard optimization problem with application to Facility Location and Clustering among others. This problem consists in finding a subset C subset of V of an input graph G = (V, E), such that the distance from the farthest vertex in V to its nearest center in C is minimized, where vertical bar C vertical bar <= k, with k is an element of Z(+) as part of the input. Many heuristics, metaheuristics, approximation algorithms, and exact algorithms have been developed for this problem. This paper presents an analytical study and experimental evaluation of the most representative approximation algorithms for the vertex k-center problem. For each of the algorithms under consideration and using a common notation, we present proofs of their corresponding approximation guarantees as well as examples of tight instances of such approximation bounds, including a novel tight example for a 3-approximation algorithm. Lastly, we present the results of extensive experiments performed over de facto benchmark data sets for the problem which includes instances of up to 71009 vertices.

关键词： approximation algorithms k-center problem polynomial time heuristics

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for the Two-Watchman Route in a Simple Polygon

引用

ALGORITHMICA 2024年第9期86卷 2845-2884页

作者： Nilsson, Bengt J. Packer, Eli Malmo Univ S-20506 Malmo Sweden Yoom Ramat Gan Israel

The two-watchman route problem is that of computing a pair of closed tours in an environment so that the two tours together see the whole environment and some length measure on the two tours is minimized. Two standard measures are: the minmax measure, where we want the tours where the longest of them has smallest length, and the minsum measure, where we want the tours for which the sum of their lengths is the smallest. It is known that computing a minmax two-watchman route is NP-hard for simple rectilinear polygons and thus also for simple polygons. Also, any c-approximation algorithm for the minmax two-watchman route is automatically a 2c-approximation algorithm for the minsum two-watchman route. We exhibit two constant factor approximation algorithms for computing minmax two-watchman routes in simple polygons with approximation factors 5.969 and 11.939, having running times O ( n 8 ) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n<^>8)$$\end{document} and O ( n 4 ) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n<^>4)$$\end{document} respectively, where n is the number of vertices of the polygon. We also use the same techniques to obtain a 6.922-approximation for the fixed two-watchman route problem running in O ( n 2 ) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n<^>2)$$\end{document} time, i.e., when two starting points of the two tours are given as input.

关键词： Art gallery problems Visibility Watchman routes approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms AND HARDNESS FOR DOMINATION WITH PROPAGATION

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2009年第3期23卷 1382-1399页

作者： Aazami, Ashkan Stilp, Kael Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA

The POWER DOMINATING SET (PDS) problem is the following extension of the well-known dominating set problem: find a smallest-size set of nodes S that power dominates all the nodes, where a node v is power dominated if (1) v is in S or v has a neighbor in S, or (2) v has a neighbor w such that w and all of its neighbors except v are power dominated. We show a hardness of approximation threshold of 2(log1-epsilon n) in contrast to the logarithmic hardness for the dominating set problem. We give an O(root n)-approximation algorithm for planar graphs and show that our methods cannot improve on this approximation guarantee. Finally, we initiate the study of PDS on directed graphs and show the same hardness threshold of 2(log1-epsilon n) for directed acyclic graphs. Also we show that the directed PDS problem can be solved optimally in linear time if the underlying undirected graph has bounded tree-width.

关键词： dominating set power dominating set PMU placement problem approximation algorithms hardness of approximation tree-width planar graphs greedy algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for solving the vertex-traversing-constrained mixed Chinese postman problem

引用

JOURNAL OF GLOBAL OPTIMIZATION 2024年第4期90卷 965-982页

作者： Pan, Pengxiang Lichen, Junran Li, Jianping Yunnan Univ Sch Math & Stat East Outer Ring South Rd Kunming 650504 Peoples R China Beijing Univ Chem Technol Sch Math & Phys North Third Ring East Rd Beijing 100029 Peoples R China

In this paper, we address the vertex-traversing-constrained mixed Chinese postman problem (the VtcMCP problem), which is a further generalization of the Chinese postman problem, and this new problem has many practical applications in real life. Specifically, given a connected mixed graph G=(V,E boolean OR A;w,b)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G=(V, E\cup A;w,b)$$\end{document} with length function w()\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$w(\cdot )$$\end{document} on edges and arcs and traversal function b()\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b(\cdot )$$\end{document} on vertices, we are asked to determine a tour traversing each link (i.e., either edge or arc) at least once and each vertex v at most b(v) times, the objective is to minimize the total length of such a tour, where n=|V|\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n=|V|$$\end{document} is the number of vertices and m=|E boolean OR A|\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m=|E\cup A|$$\end{document} is the number of links of G, respectively

关键词： Combinatorial optimization Mixed graphs Vertex traversal times Chinese postman routing approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for pricing with negative network externalities

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2017年第2期33卷 681-712页

作者： Cao, Zhigang Chen, Xujin Hu, Xiaodong Wang, Changjun Chinese Acad Sci Acad Math & Syst Sci Beijing 100190 Peoples R China Beijing Univ Technol Beijing Inst Sci & Engn Comp Beijing 100124 Peoples R China

We study the problems of pricing an indivisible product to consumers who are embedded in a given social network. The goal is to maximize the revenue of the seller by the so-called iterative pricing that offers consumers a sequence of prices over time. The consumers are assumed to be impatient in that they buy the product as soon as the seller posts a price not greater than their valuations of the product. The product's value for a consumer is determined by two factors: a fixed consumer-specified intrinsic value and a variable externality that is exerted from the consumer's neighbors in a linear way. We focus on the scenario of negative externalities, which captures many interesting situations, but is much less understood in comparison with its positive externality counterpart. Assuming complete information about the network, consumers' intrinsic values, and the negative externalities, we prove that it is NP-hard to find an optimal iterative pricing, even for unweighted tree networks with uniform intrinsic values. Complementary to the hardness result, we design a 2-approximation algorithm for general weighted networks with (possibly) nonuniform intrinsic values. We show that, as an approximation to optimal iterative pricing, single pricing works fairly well for many interesting cases, such as forests, ErdAs-R,nyi networks and Barabasi-Albert networks, although its worst-case performance can be arbitrarily bad in general networks.

关键词： Pricing approximation algorithms NP-hardness Social networks Random networks Negative externalities

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for constructing specific subgraphs with minimum number of length-bounded stock pieces

引用

INFORMATION PROCESSING LETTERS 2018年 137卷 11-16页

作者： Lichen, Junran Li, Jianping Lih, Ko-Wei Yunnan Univ Dept Math Kunming 650091 Yunnan Peoples R China Acad Sinica Inst Math Taipei 10617 Taiwan

Motivated by the Steiner tree problem with minimum number of Steiner points and bounded edge-length in [4], we consider the problem of constructing specific subgraph with minimum number of length-bounded stock pieces (CSS-MSP, for short), which is defined as follows. In some constructing specific subgraph problem Q (CSS, for short), the objective is to choose a minimum-length subset of edges, such that these edges form a specific subgraph (such as a spanning tree or a Steiner tree). In the CSS-MSP problem Q', these edges are further required to be cut from some stock pieces of length L, and the new objective, however, is to minimize the number of stock pieces of length L to construct all edges in such a specific subgraph. We obtain two main results. (1) Whenever the CSS problem Q can be approximated by an alpha-approximation algorithm (alpha >= 1) (for the case alpha = 1, the CSS problem Q is solved optimally by a polynomial-time exact algorithm), we design two approximation algorithms with performance ratios 2 alpha and 7 alpha/4 to solve the CSS-MSP problem Q';(2) In addition, when the problem Q is to find a minimum spanning tree, we present a 3/2-approximation algorithm and an APTAS to solve the problem Q' of constructing spanning tree with minimum number of length-bounded stock pieces. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Subgraphs Stock piece of length L Bin-packing approximation algorithms APTAS

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：