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

27th European Conference on Advances in Databases and Information Systems (ADBIS)

作者： Forresi, Chiara Francia, Matteo Gallinucci, Enrico Golfarelli, Matteo Univ Bologna Cesena Italy

ISBN: (纸本)9783031429408;9783031429415

Schema profiling consists in producing key insights about the schema of data in a high-variety context. In this paper, we present a streaming approach to schema profiling, where heterogeneous data is continuously ingested from multiple sources, as is typical in many IoT applications (e.g., with multiple devices or applications dynamically logging messages). The produced profile is a clustering of the schemas extracted from the data and it is computed and evolved in real-time under the overlapping sliding window paradigm. The approach is based on two-phase k-means clustering, which entails pre-aggregating the data into a coreset and incrementally updating the previous clustering results without recomputing it in every iteration. Differently from previous proposals, the approach works in a domain where dimensionality is variable and unknown apriori, it automatically selects the optimal number of clusters, and detects cluster evolution by minimizing the need to recompute the profile. The experimental evaluation demonstrated the effectiveness and efficiency of the approach against the naive baseline and the stateof-the-art algorithms on stream clustering.

关键词： Schema profiling Stream clustering K-means approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Critical Relaxed Stable Matchings with Two-Sided Ties 49th

Critical Relaxed Stable Matchings with Two-Sided Ties

引用

49th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Nasre, Meghana Nimbhorkar, Prajakta Ranjan, Keshav IIT Madras Chennai India Chennai Math Inst Chennai India UMI ReLaX Chennai India

ISBN: (纸本)9783031433795;9783031433801

We consider the stable marriage problem in the presence of ties in preferences and critical vertices. The input to our problem is a bipartite graph G = (A. B, E) where A and B denote sets of vertices which need to be matched. Each vertex has a preference ordering over its neighbours possibly containing ties. In addition, a subset of vertices in A. B are marked as critical and the goal is to output a matching that matches as many critical vertices as possible. Such matchings are called critical matchings in the literature and in our setting, we seek to compute a matching that is critical as well as optimal with respect to the preferences of the vertices. Stability, which is a well-accepted notion of optimality in the presence of two-sided preferences, is generalized to weak-stability in the presence of ties. It is well known that in the presence of critical vertices, a matching that is critical as well as weakly stable may not exist. Popularity is another well-investigated notion of optimality for the two-sided preference list setting, however, in the presence of ties (even with no critical vertices), a popular matching need not exist. We, therefore, consider the notion of relaxed stability which was introduced and studied by Krishnaa et. al. (SAGT 2020). We show that in our setting a critical matching which is relaxed stable always exists although computing a maximum-sized relaxed stable matching turns out to be NP-hard. Our main contribution is a 3 2 -approximation to the maximum-sized critical relaxed stable matching for the stable marriage problem where ties as well as critical vertices are present on both the sides of the bipartition.

关键词： Stable Matching Ties in Preferences Critical Relaxed Stable approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Local search approximation algorithms for the sum of squares facility location problems

引用

JOURNAL OF GLOBAL OPTIMIZATION 2019年第4期74卷 909-932页

作者： Zhang, Dongmei Xu, Dachuan Wang, Yishui Zhang, Peng Zhang, Zhenning Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Shandong Peoples R China Beijing Univ Technol Beijing Inst Sci & Engn Comp Beijing 100124 Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen 518055 Peoples R China Shandong Univ Sch Comp Sci & Technol Jinan 250101 Shandong Peoples R China Beijing Univ Technol Coll Appl Sci Beijing 100124 Peoples R China

In this paper, we study the sum of squares facility location problem (SOS-FLP) which is an important variant of k-means clustering. In the SOS-FLP, we are given a client set C subset of R-p and a uniform center opening cost f > 0. The goal is to open a finite center subset F subset of R-p and to connect each client to the closest open center such that the total cost including center opening cost and the sum of squares of distances is minimized. The SOS-FLP is introduced firstly by Bandyapadhyay and Varadarajan (in: Proceedings of SoCG 2016, Article No. 14, pp 14: 1-14: 15, 2016) which present a PTAS for the fixed dimension case. Using local search and scaling techniques, we offer the first constant approximation algorithm for the SOS-FLP with general dimension. We further consider the discrete version of SOS-FLP, in which we are given a finite candidate center set with nonuniform opening cost comparing with the aforementioned (continue) SOS-FLP. By exploring the structures of local and optimal solutions, we claim that the approximation ratios are 7.7721 + is an element of and 9 + is an element of for the continue and discrete SOS-FLP respectively.

关键词： approximation algorithm K-means Facility location Local search

来源：评论

学校读者我要写书评

暂无评论

New approximation algorithms for the minimum cycle cover problem

引用

THEORETICAL COMPUTER SCIENCE 2019年 793卷 44-58页

作者： Yu, Wei Liu, Zhaohui Bao, Xiaoguang East China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China Shanghai Ocean Univ Coll Informat Technol Shanghai 201306 Peoples R China

Given an undirected weighted graph G = (V, E) with nonnegative weight function obeying the triangle inequality, a set {C1, C2, ..., C-k} of cycles is called a cycle cover if V subset of boolean OR(k)(i=1) V(C-i) and its cost is given by the maximum weight of the cycles. The Minimum Cycle Cover Problem aims to find a cycle cover of cost at most lambda with the minimum number of cycles. An O(n(2)) 24/5-approximation algorithm and an O(n(5)) 14/3-approximation algorithm are given by Yu and Liu (Improved approximation algorithms for some min-max cycle cover problems. Theoretical Computer Science 654 (2016) 45-58). However, the original proofs for approximation ratios are incomplete. In this paper we first present a corrected simplified analysis on the 24/5-approximation algorithm. Based on the simplified approach of analysis and some new observations, we present a new 14/3-approximation algorithm that runs in O(n(3)) and give an improved 32/7-approximation algorithm that runs in O (n(5)). (C) 2019 Elsevier B.V. All rights reserved.

关键词： Vehicle routing Cycle cover Traveling Salesman Problem approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Scheduling multiple two-stage flowshops with a deadline

引用

THEORETICAL COMPUTER SCIENCE 2022年 921卷 100-111页

作者： Chen, Jianer Huang, Minjie Guo, Yin Guangzhou Univ Sch Comp Sci Guangzhou 510006 Peoples R China Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA

Recently, motivated by applications in cloud computing, scheduling multiple two-stage flowshops with the objective of minimizing the makespan has drawn increasing attention. Motivated by the same applications, the current paper studies the problem of scheduling multiple two-stage flowshops with a deadline, with the objective of maximizing the profit of the jobs that can be completed by the deadline. algorithms and complexity of the problem are investigated. For the case where the number of two-stage flowshops is part of the input, we present an efficient approximation algorithm with a constant ratio. The approximation ratio is improved via a study of the relationship between the problem and the multiple knapsack problem, combined with the recent progresses in the research in approximation algorithms for the multiple knapsack problem. By integrating techniques in the study of the classical KNAPSACK problem and the classical MAKESPAN problem on multiple processors, plus additional new techniques, a polynomial-time approximation algorithm with a further improved approximation ratio is developed for the case where the number of flowshops is a fixed constant. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Scheduling Two-stage flowshop approximation algorithm Cloud computing

来源：评论

学校读者我要写书评

暂无评论

Online EV Scheduling algorithms for Adaptive Charging Networks with Global Peak Constraints

IEEE TRANSACTIONS ON SUSTAINABLE COMPUTING

引用

IEEE TRANSACTIONS ON SUSTAINABLE COMPUTING 2022年第3期7卷 537-548页

作者： Alinia, Bahram Hajiesmaili, Mohammad H. Lee, Zachary J. Crespi, Noel Mallada, Enrique Telecom SudParis Inst Mines Telecom Dept Networks & Mobile Multimedia Serv RS2M F-91000 Evry France Univ Massachusetts Coll Informat & Comp Sci Amherst MA 01003 USA CALTECH Dept Elect Engn Pasadena CA 91125 USA Johns Hopkins Univ Dept Elect & Comp Engn Baltimore MD 21218 USA

This paper tackles online scheduling of electric vehicles (EVs) in an adaptive charging network (ACN) with local and global peak constraints. Given the aggregate charging demand of the EVs and the peak constraints of the ACN, it might be infeasible to fully charge all the EVs according to their charging demand. Two alternatives in such resource-limited scenarios are to maximize the social welfare by partially charging the EVs (fractional model) or selecting a subset of EVs and fully charge them (integral model). The technical challenge is the need for online solution design since in practical scenarios the scheduler has no or limited information of future arrivals in a time-coupled underlying problem. For the fractional model, we devise both offline and online algorithms. We prove that the offline algorithm is optimal. Using competitive ratio as the performance measure, we prove the online algorithm achieves a competitive ratio of 2. The integral model, however, is more challenging since the underlying problem is strongly NP-hard due to 0/1 selection criteria of EVs. Hence, efficient solution design is challenging even in offline setting. For offline setting, we devise a low-complexity primal-dual scheduling algorithm that achieves a bounded approximation ratio. Built upon the offline approximate algorithm, we propose an online algorithm and analyze its competitive ratio in special cases. Extensive trace-driven experimental results show that the performance of the proposed online algorithms is close to the offline optimum, and outperform the existing solutions.

关键词： approximation algorithms Scheduling Electric vehicle charging Scheduling algorithms Adaptive systems Electronic mail Charging stations Electric vehicle online scheduling approximation algorithm competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Off-site Service Function Protection for Type-oriented Forwarder Failures

Off-site Service Function Protection for Type-oriented Forwa...

引用

IEEE International Conference on Communications (IEEE ICC)

作者： Peng, Chengzong Zheng, Danyang Wang, Ben Cao, Xiaojun Chengdu Univ Informat Technol Sch Cybersecur Chengdu Peoples R China Southwest Jiaotong Univ Chengdu Peoples R China Soochow Univ Sch Elect & Informat Engn Suzhou Jiangsu Peoples R China Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA

ISBN: (纸本)9781538674628

In network function virtualization (NFV), service providers can accommodate services from clients by deploying software-based functions, called service functions (SFs), on commodity servers. The deployed SFs are connected to SF forwarders for efficient management in these commodity servers. Many efforts have been put into protecting SFs from failures. However, little attention has been paid to protecting SF forwarders from failures. In this paper, we investigate how to efficiently allocate backup computing resources when facing SF and SF forwarder failures. To protect the deployed SFs with the minimum backup computing resources, we define a new SF forwarder off-site shared protection problem and approve its NP-hardness. An efficient heuristic algorithm is proposed and proved to be logarithmic approximate. Extensive simulation results show that the proposed algorithm significantly outperforms the approaches directly extended from the existing work.

关键词： Network function virtualization Backup resource allocation Service function approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved and Generalized algorithms for Burning a Planar Point Set 17th

Improved and Generalized Algorithms for Burning a Planar Poi...

引用

17th International Conference and Workshops on algorithms and Computation

作者： Gokhale, Prashant Keil, J. Mark Mondal, Debajyoti Indian Inst Sci Bangalore Karnataka India Univ Saskatchewan Saskatoon SK Canada

ISBN: (纸本)9783031270505;9783031270512

Given a set P of points in R-2, a point burning process is a discrete time process to burn all the points of P where fires must be initiated at the points of P. Specifically, the point burning process starts with a single burnt point from P, and at each subsequent step, burns all the points in R-2 that are within one unit distance from the currently burnt points, as well as one other unburnt point of P (if exists). The point burning number of P is the smallest number of steps required to burn all the points of P. If we allow the fire to be initiated anywhere in R-2, then the burning process is called an anywhere burning process. One can think of the anywhere burning problem as finding the minimum integer r such that P can be covered with disks of radii 0, 1, 2,..., r. A burning process provides a simple model for distributing commodities to the locations in P by sending a daily bulk shipment to a distribution center, i.e., the place where we initiate a fire. The burning number corresponds to the minimum number of days to reach all locations. In this paper we show that both point and anywhere burning problems admit PTAS in one dimension. We then show that in two dimensions, point burning and anywhere burning are (1.96+epsilon) and (1.92+epsilon) approximable, respectively, for every epsilon > 0, which improves the previously known (2 + epsilon) approximation for these problems. We then generalize the results by allowing the points to have different fire spreading rates, and prove that even if the burning sources are given as input, finding a point burning sequence itself is NP-hard. Finally, we obtain a 2-approximation for burning the maximum number of points in a given number of steps.

关键词： Computational geometry Burning number approximation algorithm NP-hard

来源：评论

学校读者我要写书评

暂无评论

A Carbon-aware Workload Dispatcher in Cloud Computing Systems 16

A Carbon-aware Workload Dispatcher in Cloud Computing System...

引用

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：