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

IEEE 16th International Conference on Cloud Computing (IEEE CLOUD)

作者： Bahreini, Tayebeh Tantawi, Asser Youssef, Alaa IBM TJ Watson Res Ctr Yorktown Hts NY 10598 USA

ISBN: (纸本)9798350304817

The amount of carbon emission associated with the computational energy consumption in data centers depends, in a significant way, on the schedule of the workloads. Due to the inconsistent availability of renewable energy over time, in addition to the existence of various sources of power in grid regions, the carbon intensity of data centers changes over time and location. Thus, the placement and scheduling of flexible workloads, based on the carbon intensity of power sources in data centers, can remarkably decrease the carbon emission. In this paper, we address the problem of placement and scheduling of workloads over geographically distributed data centers. We propose two algorithms that take the variability of carbon intensity of the power sources of the data centers, as well as their computational resource availability, into account when deciding about the placement and scheduling of the workloads. The first is a randomized rounding approximation algorithm that provides solutions that are guaranteed to be within a given distance from the optimal solution. The second is a sample-based algorithm that improves the solutions obtained by the randomized rounding approximation algorithm. The experimental results show that the proposed algorithms can solve the problem efficiently.

关键词： approximation algorithm cloud sustainability green computing placement randomized rounding scheduling

来源：评论

学校读者我要写书评

暂无评论

Scheduling with Speed Predictions 1

引用

21st International Workshop on approximation and Online algorithms (WAOA) part of ALGO Conference

作者： Balkanski, Eric Ou, Tingting Stein, Clifford Wei, Hao-Ting Columbia Univ Dept Ind Engn & Operat Res New York NY 10027 USA

ISBN: (数字)9783031498152

ISBN: (纸本)9783031498145;9783031498152

algorithms with predictions is a recent framework that has been used to overcome pessimistic worst-case bounds in incomplete information settings. In the context of scheduling, very recent work has leveraged machine-learned predictions to design algorithms that achieve improved approximation ratios in settings where the processing times of the jobs are initially unknown. In this paper, we study the speed-robust scheduling problem where the speeds of the machines, instead of the processing times of the jobs, are unknown and augment this problem with predictions. Our main result is an algorithm that achieves a min{eta(2) (1 + alpha), (2 + 2/alpha)} approximation, for any alpha is an element of (0, 1), where eta >= 1 is the prediction error. When the predictions are accurate, this approximation outperforms the best known approximation for speed-robust scheduling without predictions of 2- 1/m, where m is the number of machines, while simultaneously maintaining a worst-case approximation of 2+ 2/alpha even when the predictions are arbitrarily wrong. In addition, we obtain improved approximations for three special cases: equal job sizes, infinitesimal job sizes, and binary machine speeds. We also complement our algorithmic results with lower bounds. Finally, we empirically evaluate our algorithm against existing algorithms for speed-robust scheduling. The full version of the paper can be referred to the following link https://***/abs/2205.01247.

关键词： algorithms with prediction Scheduling approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Local search approximation algorithms for the k-means problem with penalties

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2019年第2期37卷 439-453页

作者： Zhang, Dongmei Hao, Chunlin Wu, Chenchen Xu, Dachuan Zhang, Zhenning Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Shandong Peoples R China Beijing Univ Technol Coll Appl Sci Dept Informat & Operat Res 100 Pingleyuan Beijing 100124 Peoples R China Tianjin Univ Technol Coll Sci Tianjin 300384 Peoples R China Beijing Univ Technol Beijing Inst Sci & Engn Comp 100 Pingleyuan Beijing 100124 Peoples R China

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 D subset of R-d, a penalty cost p (j) > 0 for each j. D, and an integer k <= n. The goal is to open a center subset F subset of R-d with vertical bar F vertical bar <= k and to choose a client subset P subset of D as the penalized client set such that the total cost (including the sum of squares of distance for each client in D\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 + epsilon)-approximation algorithm for the k-MPWP by using single-swap operation. We further improve the above approximation ratio to (25 + epsilon) by using multi-swap operation.

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

来源：评论

学校读者我要写书评

暂无评论

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第3期44卷 1724-1740页

作者： Zhang, Siyun Nip, Kameng Wang, Zhenbo Tsinghua Univ Dept Math Sci Beijing Peoples R China Sun Yat Sen Univ Sch Math Zhuhai Zhuhai Peoples R China

We propose a related machine scheduling problem in which the processing times of jobs are given and known, but the speeds of machines are variables and must satisfy a system of linear constraints. The objective is to decide the speeds of machines and minimize the makespan of the schedule among all the feasible choices. The problem is motivated by some practical application scenarios. This problem is strongly NP-hard in general, and we discuss various cases of it. In particular, we obtain polynomial time algorithms for two special cases. If the number of constraints is more than one and the number of machines is a fixed constant, then we give a (2+epsilon)-approximation algorithm. For the case where the number of machines is an input of the problem instance, we propose several approximation algorithms, and obtain a polynomial time approximation scheme when the number of distinct machine speeds is a fixed constant.

关键词： Related machine scheduling Linear programming approximation algorithm Scheduling under linear constaints

来源：评论

学校读者我要写书评

暂无评论

Approximating Dynamic Weighted Vertex Cover with Soft Capacities

引用

algorithmICA 2022年第1期84卷 124-149页

作者： Wei, Hao-Ting Hon, Wing-Kai Horn, Paul Liao, Chung-Shou Sadakane, Kunihiko Natl Tsing Hua Univ Dept Ind Engn & Engn Management Hsinchu 30013 Taiwan Natl Tsing Hua Univ Dept Comp Sci Hsinchu 30013 Taiwan Univ Denver Dept Math Denver CO USA Univ Tokyo Dept Math Informat Tokyo Japan

This study considers the soft capacitated vertex cover problem in a dynamic setting. This problem generalizes the dynamic model of the vertex cover problem, which has been intensively studied in recent years. Given a dynamically changing vertex-weighted graph G = (V, E), which allows edge insertions and edge deletions, the goal is to design a data structure that maintains an approximate minimum vertex cover while satisfying the capacity constraint of each vertex. That is, when picking a copy of a vertex v in the cover, the number of v's incident edges covered by the copy is up to a given capacity of v. We extend Bhattacharya et al.'s work [SODA'15 and ICALP'15] to obtain a deterministic primal-dual algorithm for maintaining a constant-factor approximate minimum capacitated vertex cover with O(log n/is an element of) amortized update time, where n is the number of vertices in the graph. The algorithm can be extended to (1) a more general model in which each edge is associated with a non-uniform and unsplittable demand, and (2) the more general capacitated set cover problem.

关键词： Dynamic algorithm Vertex cover approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

The bi-criteria seeding algorithms for two variants of k-means problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第3期44卷 1693-1704页

作者： Li, Min Shandong Normal Univ Sch Math & Stat Jinan 250014 Peoples R China

The k-means problem is very classic and important in computer science and machine learning, so there are many variants presented depending on different backgrounds, such as the k-means problem with penalties, the spherical k-means clustering, and so on. Since the k-means problem is NP-hard, the research of its approximation algorithm is very hot. In this paper, we apply a bi-criteria seeding algorithm to both k-means problem with penalties and spherical k-means problem, and improve (upon) the performance guarantees given by the k-means++ algorithm for these two problems.

关键词： approximation algorithm k-means problem with penalties Spherical k-means clustering Seeding algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for the combination problem of parallel machine scheduling and path

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2019年第3期38卷 689-697页

作者： Guan, Li Li, Jianping Li, Weidong Lichen, Junran Yunnan Univ Sch Math & Stat Kunming 650504 Yunnan Peoples R China

In this paper, we study a combination problem of parallel machine scheduling and the s-t path problem, which is to find a s-t path P-st of the given directed graph, and to schedule the jobs corresponding to the arcs of the path P-st on m parallel machines, such that the makespan is minimized. It has been proved that this problem is NP-hard and admits 2-approximation algorithm. We present a polynomial-time algorithm with approximation ratio 1.5. By modifying the dynamic programming method for the restricted shortest path problem, we also give a polynomial time approximation scheme.

关键词： Parallel machine scheduling Shortest path approximation algorithm Polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth 2023

Approximate Max-Flow Min-Multicut Theorem for Graphs of Boun...

引用

55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

作者： Friedrich, Tobias Issac, Davis Kumar, Nikhil Mallek, Nadym Zeif, Ziena Potsdam Univ Hasso Plattner Inst Potsdam Germany

ISBN: (纸本)9781450399135

We prove an approximate max-multiflow min-multicut theorem for bounded treewidth graphs. In particular, we show the following: Given a treewidth-r graph, there exists a (fractional) multi-commodity flow of value f, and a multicut of capacity c such that f <= c <= O(ln(r + 1))center dot f. It is well known that the multiflow-multicut gap on an r-vertex (constant degree) expander graph can be Omega(ln r), and hence our result is tight up to constant factors. Our proof is constructive, and we also obtain a polynomial time O(ln(r + 1))-approximation algorithm for the minimum multicut problem on treewidth-r graphs. Our algorithm proceeds by rounding the optimal fractional solution to the natural linear programming relaxation of the multicut problem. We introduce novel modifications to the well-known region growing algorithm to facilitate the rounding while guaranteeing at most a logarithmic factor loss in the treewidth.

关键词： Max-Flow Min-Multicut Theorem Small Diameter Decomposition approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Graph Covering Using Bounded Size Subgraphs 9th

Graph Covering Using Bounded Size Subgraphs

引用

9th International Conference on algorithms and Discrete Applied Mathematics (CALDAM)

作者： Gorain, Barun Patra, Shaswati Singh, Rishi Ranjan Indian Inst Technol Bhilai Raipur Madhya Pradesh India

ISBN: (纸本)9783031252105;9783031252112

A variant of graph covering problem demands to find a set of sub-graphs when the union of sub-graphs contain all the edges of G. Another variant of graph covering problem requires finding a collection of subgraphs such that the union of the vertices of subgraphs forms a vertex cover. We study the later version of the graph covering problem. The objective of these problems is to minimize the size/cost of the collection of subgraphs. Covering graphs with the help of a set of edges, set of vertices, tree or tour has been studied extensively in the past few decades. In this paper, we study a variant of the graph covering problem using two special subgraphs. The first problem is called bounded component forest cover problem. The objective is to find a collection of minimum number of edge-disjoint bounded weight trees such that the vertices of the forest, i.e., collection of edge-disjoint trees, cover the graph. The second problem is called bounded size walk cover problem. It asks to minimize the number of bounded size walks which can cover the graph. Walks allow repetition of vertices/edges. Both problems are a generalization of classical vertex cover problem, therefore, are NP-hard. We give 4. and 6. factor approximation algorithm for bounded component forest cover and bounded size walk cover problems respectively, where. is an approximation factor to find a solution to the tree cover problem.

关键词： Graph Covering Vertex Cover Problem Tree Cover Problem approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A unified greedy approximation for several dominating set problems

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期973卷

作者： Zhong, Hao Tang, Yong Zhang, Qi Lin, Ronghua Li, Weisheng South China Normal Univ Sch Comp Sci Guangzhou 510631 Peoples R China Guangzhou Coll Commerce Sch Informat Technol & Engn Guangzhou 511363 Peoples R China Pazhou Lab Guangzhou 510330 Peoples R China

Minimum Dominating Set and Minimum Connected Dominating Set are classic graph problems that have been studied extensively in the literature. These two problems and their various variants are NP-hard in a general graph, and for some of them greedy approximation algorithms have been proposed. In this paper, by designing two potential functions that enjoy submodularity or a weak submodularity, we propose a unified O(ln & delta;)-approximation algorithm for a generalized Minimum (Connected) Dominating Set that includes Minimum (Connected) Dominating Set, Minimum (Connected) Total Dominating Set, Minimum (Connected) *-Dominating Set and Minimum (Connected) Positive Influence Dominating Set, where & delta;is the maximum node degree of the input graph. For each specific version of the generalized Minimum (Connected) Dominating Set, the unified algorithm either matches the best one of existing approximation algorithms, or gives the first approximation solution.& COPY;2023 Elsevier B.V. All rights reserved.

关键词： Dominating set Connected dominating set Submodularity approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：