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

Multi-robot exploration on grids with a bounded time

SCIENTIA IRANICA 2021年第3期28卷 1515-1528页

作者： Davoodi, M. Delfaraz, E. Ghobadi, S. Masoori, M. Inst Adv Studies Basic Sci Dept Comp Sci & Informat Technol Gavazang Zanjan Iran

In this paper, the problem of exploring a grid environment in the offline setting is studied. The goal is to propose an algorithm to find the minimum number of robots for exploring a rectangular grid environment, with n rows and m columns, denoted by R(n, m) at a predefined time T. In case of no obstacles in the environment, an optimal solution is proposed for the problem. In another case when the environment may contain some obstacles, it is pointed out that the problem is NP-complete and it cannot be approximated within better than a factor 2. Finally, a 4-approximation algorithm is presented in order to explore R(n, m) in the presence of obstacles. (C) 2021 Sharif University of Technology. All rights reserved.

关键词： approximation algorithm Path planning Exploration Grid environments Lower bound

来源：评论

学校读者我要写书评

暂无评论

APPROXIMATING A BEHAVIOURAL PSEUDOMETRIC WITHOUT DISCOUNT FOR PROBABILISTIC SYSTEMS

引用

LOGICAL METHODS IN COMPUTER SCIENCE 2008年第2期4卷

作者： Van Breugel, Franck Sharma, Babita Worrell, James York Univ Toronto ON M3J 1P3 Canada IBM Corp Toronto Lab Markham ON L6G 1C7 Canada Univ Oxford Comp Lab Oxford OX1 3QD England

Desharnais, Gupta, Jagadeesan and Panangaden introduced a family of behavioural pseudometrics for probabilistic transition systems. These pseudometrics are a quantitative analogue of probabilistic bisimilarity. Distance zero captures probabilistic bisimilarity. Each pseudometric has a discount factor, a real number in the interval (0, 1]. The smaller the discount factor, the more the future is discounted. If the discount factor is one, then the future is not discounted at all. Desharnais et al. showed that the behavioural distances can be calculated up to any desired degree of accuracy if the discount factor is smaller than one. In this paper, we show that the distances can also be approximated if the future is not discounted. A key ingredient of our algorithm is Tarski's decision procedure for the first order theory over real closed fields. By exploiting the Kantorovich-Rubinstein duality theorem we can restrict to the existential fragment for which more efficient decision procedures exist.

关键词： probabilistic transition system behavioural pseudometric probabilistic bisimilarity approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2002年第4期15卷 450-469页

作者： Schulz, AS Skutella, M MIT Alfred P Sloan Sch Management Cambridge MA 02139 USA Tech Univ Berlin Fak 2 Inst Math D-10623 Berlin Germany

We present a new class of randomized approximation algorithms for unrelated parallel machine scheduling problems with the average weighted completion time objective. The key idea is to assign jobs randomly to machines with probabilities derived from an optimal solution to a linear programming (LP) relaxation in time-indexed variables. Our main results are a (2+epsilon)-approximation algorithm for the model with individual job release dates and a (3/2+epsilon)-approximation algorithm if all jobs are released simultaneously. We obtain corresponding bounds on the quality of the LP relaxation. It is an interesting implication for identical parallel machine scheduling that jobs are randomly assigned to machines;in which each machine is equally likely. In addition, in this case the algorithm has running time O(n log n) and performance guarantee 2. Moreover, the approximation result for identical parallel machine scheduling applies to the on-line setting in which jobs arrive over time as well, with no difference in performance guarantee.

关键词： approximation algorithm randomized rounding linear programming relaxation scheduling on-line algorithm

来源：评论

学校读者我要写书评

暂无评论

Off-site protection against service function forwarder failures in NFV

引用

COMPUTER NETWORKS 2023年第1期221卷

作者： Peng, Chengzong Zheng, Danyang Zhong, Yihan Cao, Xiaojun Chengdu Univ Informat Technol Sch Cybersecur Chengdu 610225 Peoples R China Soochow Univ Suzhou Key Lab Adv Opt Commun Network Technol Sch Elect & Informat Engn Suzhou 215006 Peoples R China Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA

Many internet applications in the emerging 5G/6G networks require ultra-reliable and low-latency communi-cations (URLLC) services. To deliver URLLC services flexibly and efficiently, network function virtualization (NFV) is employed to enable network slicing. NFV deploys service function chains (SFCs) consisting of service functions (SFs) and service function forwarders (SFFs) to deliver services. It is possible for SFFs in an SFC to fail when forwarding traffic to specified SF instances. Protecting SFF failures in NFV is challenging since multiple SF instances may fail simultaneously as a result of a single SFF failure. This work investigates how to protect the SF instances against the SFF failures while minimizing the cost of backup computing resources. We formulate a new problem called SFF-driven multi-instance failures and protection (SMFP), and prove its NP-hardness. We propose an efficient heuristic algorithm, namely, SFF-centralized resource optimization (FCRO), which is based on the proposed techniques of backup auxiliary transferring, backup cost-effectiveness selection, and adaptive fit backup. Our experimental results demonstrate that the proposed FCRO is effective and significantly outperforms the schemes directly extended from the existing work.

关键词： Network function virtualization Network reliability Service function forwarder approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Packet-in request redirection: A load-balancing mechanism for minimizing control plane response time in SDNs

引用

JOURNAL OF SYSTEMS ARCHITECTURE 2022年 129卷

作者： Xia, Rui Dai, Haipeng Zheng, Jiaqi Xu, Hong Li, Meng Chen, Guihai Nanjing Univ State Key Lab Novel Software Technol Nanjing 210023 Peoples R China Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China

A distributed control plane is more scalable and robust in software defined networking. This paper focuses on controller load balancing using packet-in request redirection, that is, given the instantaneous state of the system, determining whether to redirect packet-in requests for each switch, such that the overall control plane response time (CPRT) is minimized. To address the above problem, we propose a framework based on Lyapunov optimization. First, we use the drift-plus-penalty algorithm to combine CPRT minimization problem with controller capacity constraints, and further derive a non-linear program, whose optimal solution is obtained with brute force using standard linearization techniques. Second, we present a greedy strategy to efficiently obtain a solution with a bounded approximation ratio. Third, we reformulate the program as a problem of maximizing a non-monotone submodular function subject to matroid constraints. We implement a controller prototype for packet-in request redirection, and conduct trace-driven simulations to validate our theoretical results. The results show that our algorithms can reduce the average CPRT by 81.6% compared to static assignment, and achieve a 3x improvement in maximum controller capacity violation ratio.

关键词： Software defined networking (SDN) Distributed control plane Load balancing Lyapunov optimization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximate Distance Oracles for Geometric Spanners

引用

ACM TRANSACTIONS ON algorithmS 2008年第1期4卷 10-10页

作者： Gudmundsson, Joachim Levcopoulos, Christos Narasimhan, Giri Smid, Michiel Natl ICT Australia Ltd Eveleigh NSW 1430 Australia Lund Univ Dept Comp Sci S-22100 Lund Sweden Florida Int Univ Sch Comp & Informat Sci Miami FL 33199 USA Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada

Given an arbitrary real constant epsilon > 0, and a geometric graph G in d-dimensional Euclidean space with n points, O(n) edges, and constant dilation, our main result is a data structure that answers (1 + epsilon)-approximate shortest-path-length queries in constant time. The data structure can be constructed in O( n log n) time using O( n log n) space. This represents the first data structure that answers (1 + epsilon)-approximate shortest-path queries in constant time, and hence functions as an approximate distance oracle. The data structure is also applied to several other problems. In particular, we also show that approximate shortest-path queries between vertices in a planar polygonal domain with "rounded" obstacles can be answered in constant time. Other applications include query versions of closest-pair problems, and the efficient computation of the approximate dilations of geometric graphs. Finally, we show how to extend the main result to answer (1 + epsilon)-approximate shortest-path-length queries in constant time for geometric spanner graphs with m = omega(n) edges. The resulting data structure can be constructed in O(m + n log n) time using O(n log n) space.

关键词： Shortest paths geometric graphs approximation algorithm computational geometry spanners

来源：评论

学校读者我要写书评

暂无评论

New algorithms for fair k-center problem with outliers and capacity constraints

引用

THEORETICAL COMPUTER SCIENCE 2024年 999卷

作者： Wu, Xiaoliang Feng, Qilong Xu, Jinhui Wang, Jianxin Cent South Univ Sch Comp Sci & Engn Changsha Peoples R China Xiangjiang Lab Changsha Peoples R China SUNY Buffalo Dept Comp Sci & Engn New York NY USA Cent South Univ Hunan Prov Key Lab Bioinformat Changsha Peoples R China

The fair k-center problem has been paid lots of attention recently. In the fair k-center problem, we are given a set X of points in a metric space and a parameter k is an element of Z(+), where the points in X are divided into several groups, and each point is assigned a color to denote which group it is in. The goal is to partition X into k clusters such that the number of cluster centers with each color is equal to a given value, and the k-center problem objective is minimized. In this paper, we consider the fair k-center problem with outliers and capacity constraints, denoted as the fair k-center with outliers (FkCO) problem and the capacitated fair k-center (CFkC) problem, respectively. The outliers constraints allow up to z outliers to be discarded when computing the objective function, while the capacity constraints require that each cluster has size no more than L. In this paper, we design an Fixed-Parameter Tractability (FPT) approximation algorithm and a polynomial approximation algorithm for the above two problems. In particular, our algorithms give (1 + epsilon)-approximations with FPT time for the FkCO and CFkC problems in doubling metric space. Moreover, we also propose a 3-approximation algorithm in polynomial time for the FkCO problem with some reasonable assumptions.

关键词： k-center Fairness approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Race to Idle: New algorithms for Speed Scaling with a Sleep State

引用

ACM TRANSACTIONS ON algorithmS 2014年第2期10卷 9-9页

作者： Albers, Susanne Antoniadis, Antonios Humboldt Univ Dept Comp Sci D-10099 Berlin Germany

We study an energy conservation problem where a variable-speed processor is equipped with a sleep state. Executing jobs at high speeds and then setting the processor asleep is an approach that can lead to further energy savings compared to standard dynamic speed scaling. We consider classical deadline-based scheduling, that is, each job is specified by a release time, a deadline and a processing volume. For general convex power functions, Irani et al. [2007] devised an offline 2-approximation algorithm. Roughly speaking, the algorithm schedules jobs at a critical speed scrit that yields the smallest energy consumption while jobs are processed. For power functions P(s) = s(alpha) + gamma, where s is the processor speed, Han et al. [2010] gave an (alpha(alpha) + 2)-competitive online algorithm. We investigate the offline setting of speed scaling with a sleep state. First, we prove NP-hardness of the optimization problem. Additionally, we develop lower bounds, for general convex power functions: No algorithm that constructs s(crit)-schedules, which execute jobs at speeds of at least s(crit), can achieve an approximation factor smaller than 2. Furthermore, no algorithm that minimizes the energy expended for processing jobs can attain an approximation ratio smaller than 2. We then present an algorithmic framework for designing good approximation algorithms. For general convex power functions, we derive an approximation factor of 4/3. For power functions P(s) = beta s(alpha) + gamma, we obtain an approximation of 137/117 < 1.171. We finally show that our framework yields the best approximation guarantees for the class of scrit-schedules. For general convex power functions, we give another 2-approximation algorithm. For functions P(s) = beta s(alpha) + gamma, we present tight upper and lower bounds on the best possible approximation factor. The ratio is exactly eW(-1)(-e(-1-1/e))/(eW(-1)(-e(-1-1/e))+ 1) < 1.211, where W-1 is the lower branch of the Lambert W function.

关键词： Variable-speed processor power-down mechanism NP-hard approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

NEAR-OPTIMAL DISTRIBUTED MAXIMUM FLOW

引用

SIAM JOURNAL ON COMPUTING 2018年第6期47卷 2078-2117页

作者： Ghaffari, Mohsen Karrenbauer, Andreas Kuhn, Fabian Lenzen, Christoph Patt-Shamir, Boaz Swiss Fed Inst Technol Comp Sci Dept CH-8092 Zurich Switzerland MPI Informat Saarland Informat Campus D-66123 Saarbrucken Germany Univ Freiburg Dept Comp Sci D-79085 Freiburg Germany Tel Aviv Univ Sch Elect Engn IL-6997801 Tel Aviv Israel

We present a near-optimal distributed algorithm for (1 + o(1))-approximation of single-commodity maximum flow in undirected weighted networks that runs in (D + root n) . n(o(1)) communication rounds in the CONGEST model. Here, n and D denote the number of nodes and the network diameter, respectively. This is the first improvement over the trivial bound of O(n(2)), and it nearly matches the (Omega) over tilde (D + root n)-round complexity lower bound. The development of the algorithm entails two subresults of independent interest: (i) A (D + root n) . n(o(1))-round distributed construction of a spanning tree of average stretch n(o(1)). (ii) A (D + root n) . n(o(1))-round distributed construction of an n(o(1))-congestion approximator consisting of the cuts induced by O(logn) virtual trees. The distributed representation of the cut approximator allows for evaluation in (D + root n) n(o(1)) rounds. All our algorithms make use of randomization and succeed with high probability.

关键词： CONGEST model congestion approximator approximation algorithm gradient descent

来源：评论

学校读者我要写书评

暂无评论

Single Machine Scheduling with Outsourcing Under Different Fill Rates or Quantity Discount Rates

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2020年第1期37卷

作者： Lu, Lingfa Zhang, Liqi Zhang, Jie Zuo, Lili Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China Henan Agr Univ Coll Informat & Management Sci Zhengzhou 450003 Henan Peoples R China

In this paper, we consider two single machine scheduling problems with outsourcing under different fill rates or quantity discount rates. From the manufacturer point of view, to maintain a predefined high service level under limited production capacity, it is required that the number of outsourced jobs must belong to a given interval [a, b]. We call this model "scheduling with outsourcing under different fill rates". Meanwhile, from the outsourcers point of view, in order to encourage more outsourcing actions from the manufacturer, the outsourcers might provide an attractive discount scheme. Here, we assume that all discount rates depend only on the quantity (number) of the outsourced jobs. That is, the actual outsourcing cost equals to the original outsourcing cost multiplied by the corresponding discount rate. This model is called "scheduling with outsourcing under different quantity discount rates". The objective is to minimize the sum of the makespan of the processed jobs and the (actual) outsourcing costs of the outsourced jobs. For the above two problems, some optimal algorithms, approximation algorithms and approximation schemes are proposed.

关键词： Scheduling with outsourcing fill rates discount rates approximation algorithm FPTAS

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：