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

16th Latin American Symposium on Theoretical Informatics (LATIN)

作者： Dey, Palash Kolay, Sudeshna Singh, Sipra Indian Inst Technol Kharagpur Kharagpur W Bengal India

ISBN: (纸本)9783031556005;9783031556012

We study the KNAPSACK problem with graph-theoretic constraints. That is, there exists a graph structure on the input set of items of KNAPSACK and the solution also needs to satisfy certain graph theoretic properties on top of the KNAPSACK constraints. In particular, we study CONNECTED KNAPSACK where the solution must be a connected subset of items which has maximum value and satisfies the size constraint of the knapsack. We show that this problem is strongly NP-complete even for graphs of maximum degree four and NP-complete even for star graphs. On the other hand, we develop an algorithm running in time O (2(O(tw log tw)) . poly(n) min{s(2), d(2)}) where tw, s, d, n are respectively treewidth of the graph, the size of the knapsack, the target value of the knapsack, and the number of items. We also exhibit a (1- epsilon) factor approximation algorithm running in time O (2(O(tw log tw)) . poly( n, 1/epsilon)) for every epsilon > 0. We show similar results for PATH KNAPSACK and Shortest PATH KNAPSACK, where the solution must also induce a path and shortest path, respectively. Our results suggest that CONNECTED KNAPSACK is computationally the hardest, followed by PATH KNAPSACK and then SHORTEST PATH KNAPSACK.

关键词： Knapsack Graph algorithms Parameterised Complexity approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

HARNESS: High Availability Supportive Self Reliant Network Slicing in 5G Networks

引用

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT 2022年第3期19卷 1951-1964页

作者： Vittal, Shwetha Franklin, A. Antony Indian Inst Technol Hyderabad Dept Comp Sci & Engn Hyderabad 502205 India

Mobile Network Operator (MNO)s avail the benefit of providing an isolated service with the network slice in a variety of forms like enhanced Mobile Broadband (eMBB), ultra Reliable Low Latency Communications (uRLLC), and massive Machine Type Communications (mMTC). However, they face challenges in handling situations of overload, congestion, and scaling with the arrival of unexpected control plane User Service Requests (USRs) leading to the dropping of USRs, and hence disturbing the slice's High Availability (HA). This paper presents a novel High Availability supportive self Reliant NEtwork Slicing System (HARNESS) for 5G Core, powered by intelligent and autonomous Self Organizing Network (SON) paradigm. In HARNESS, we propose algorithms to intelligently schedule and serve the significant portion of control plane USRs for both delay tolerant and delay sensitive slices, to ensure their uninterrupted HA service provision. Along with efficient resource utilization, the HARNESS shows improvements over the traditional HA provisioning methods, in preventing the occluding of crucial control plane USRs by 60% and reducing the average response time for these USRs by 50%. We developed the HARNESS framework in a 5G test-bed system using eXpress Data Path (XDP) and extended Berkeley Packet Filter (eBPF) mechanism for coherent and optimized end-to-end working of it. With this additional gear, HARNESS productively contributes to achieving 3.2% better slice service HA in the minimal two nodes active/active cluster configuration.

关键词： 5G mobile communication Delays Noise measurement Ultra reliable low latency communication Scheduling Quality of service Network slicing 5G 5G core approximation algorithm network slicing high availability reliability NP-completeness Pareto distribution self organizing network

来源：评论

学校读者我要写书评

暂无评论

To Store or Not to Store: a graph theoretical approach for Dataset Versioning 38

To Store or Not to Store: a graph theoretical approach for D...

引用

International Parallel and Distributed Processing Symposium (IPDPS)

作者： Guo, Anxin Li, Jingwei Sukprasert, Pattara Khuller, Samir Deshpande, Amol Mukherjee, Koyel Northwestern Univ Comp Sci Dept Evanston IL 60208 USA Columbia Univ Ind Engn & Operat Res New York NY USA Databricks San Francisco CA USA Univ Maryland Dept Comp Sci College Pk MD USA Adobe Res Bangalore Karnataka India

ISBN: (纸本)9798350387117;9798350387124

Dataset Versioning is extremely important for ensuring the reproducibility of results, tracking data changes over time, maintaining quality measures, enabling collaboration, and ensuring legal compliance. In this work, we study the cost efficient data versioning problem, where the goal is to optimize the storage and reconstruction (retrieval) costs of data versions, given a graph of datasets as nodes and edges capturing edit/delta information. One central variant we study is MINSUM RETRIEVAL (MSR) where the goal is to minimize the total retrieval costs, while keeping the storage costs bounded. This problem (along with its variants) was introduced by Bhattacherjee et al. [VLDB'15]. While such problems are frequently encountered in collaborative tools (e.g., version control systems and data analysis pipelines), to the best of our knowledge, no existing research studies the theoretical aspects of these problems. We established, in the full version of this work(1), that the previous best heuristic, LMG (introduced in [VLDB'15]) can perform arbitrarily badly in a simple worst case. Moreover, we show that it is hard to get o(n)-approximation for MSR on general graphs even if we relax the storage constraints by an O(log n) factor. Similar hardness results are shown for other variants. Meanwhile, we propose poly-time approximation schemes for tree-like graphs, motivated by the fact that the graphs arising in practice from typical edit operations are often not arbitrary. As version graphs typically have low treewidth, we further develop new algorithms for bounded treewidth graphs. Furthermore, we propose two new heuristics and evaluate them empirically. First, we extend LMG by considering more potential "moves", to propose a new heuristic LMG-All. LMG-All consistently outperforms LMG while having comparable run time on a wide variety of datasets, i.e., version graphs. Secondly, we apply our tree algorithms on the minimum-storage arborescence of an instance, yielding algorith

关键词： Version Control Systems Data Management approximation algorithm Combinatorial Optimization

来源：评论

学校读者我要写书评

暂无评论

A Tabu Search algorithm for the Map Labeling Problem 17th

A Tabu Search Algorithm for the Map Labeling Problem

引用

17th Italian Workshop on Artificial Life and Evolutionary Computation (WIVACE)

作者： Cavallaro, Claudia Cutello, Vincenzo Pavone, Mario Zito, Francesco Univ Catania Dept Math & Comp Sci v Andrea Doria 6 I-95125 Catania Italy

ISBN: (纸本)9783031574290;9783031574306

In this paper we propose an algorithm based on the Tabu Search metaheuristic for the Map Labeling problem, i.e. the relevant problem in cartography of assigning labels to specific points of interests in a clear and readable way. It is a combinatorial problem known to be NP- complete and therefore it needs to be tackled by means of good and efficient heuristics. In our experiments, we used real maps of Italian cities, Rome and Venice in particular.

关键词： Metaheuristics Tabu Search Map Labeling Combinatorial Optimization NP-complete approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved hardness and approximation results for single allocation hub location problems

引用

THEORETICAL COMPUTER SCIENCE 2021年 864卷 10-19页

作者： Wang, Xing Chen, Guangting Chen, Yong Lin, Guohui Wang, Yonghao Zhang, An Hangzhou Dianzi Univ Dept Math Hangzhou Peoples R China Taizhou Univ Taizhou Peoples R China Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Hangzhou Dianzi Univ Comp Sci & Technol Hangzhou Peoples R China

Given a metric graph G = (V, E, w) and an integer k, we aim to find a single allocation k-hub location, which is a spanning subgraph consisting of a clique of size k such that every node outside of the clique is adjacent to exactly one node inside the clique. For various objective functions studied in the literature, we present improved hardness and approximation results. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Hub location Metric NP-hardness Inapproximability approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm for uniform bounded facility location problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2013年第2期26卷 284-291页

作者： Weng Kerui China Univ Geosci Sch Econ & Management Wuhan 430070 Peoples R China

The uniform bounded facility location problem (UBFLP) seeks for the optimal way of locating facilities to minimize total costs (opening costs plus routing costs), while the maximal routing costs of all clients are at most a given bound M. After building a mixed 0-1 integer programming model for UBFLP, we present the first constant-factor approximation algorithm with an approximation guarantee of 6.853+I mu for UBFLP on plane, which is composed of the algorithm by Dai and Yu (Theor. Comp. Sci. 410:756-765, 2009) and the schema of Xu and Xu (J. Comb. Optim. 17:424-436, 2008). We also provide a heuristic algorithm based on Benders decomposition to solve UBFLP on general graphes, and the computational experience shows that the heuristic works well.

关键词： Facility location Routing costs bound approximation algorithm Benders decomposition

来源：评论

学校读者我要写书评

暂无评论

Energy-Efficient Real-Time Job Mapping and Resource Management in Mobile-Edge Computing 45

Energy-Efficient Real-Time Job Mapping and Resource Manageme...

引用

45th Real Time Systems Symposium

作者： Gao, Chuanchao Kumar, Niraj Easwaran, Arvind Nanyang Technol Univ Coll Comp & Data Sci Singapore Singapore Nanyang Technol Univ Energy Res Inst NTU Interdisciplinary Grad Programme Singapore Singapore

ISBN: (纸本)9798331540265;9798331540272

Mobile-edge computing (MEC) has emerged as a promising paradigm for enabling Internet of Things (IoT) devices to handle computation-intensive jobs. Due to the imperfect parallelization of algorithms for job processing on servers and the impact of IoT device mobility on data communication quality in wireless networks, it is crucial to jointly consider server resource allocation and IoT device mobility during job scheduling to fully benefit from MEC, which is often overlooked in existing studies. By jointly considering job scheduling, server resource allocation, and IoT device mobility, we investigate the deadline-constrained job offloading and resource management problem in MEC with both communication and computation contentions, aiming to maximize the total energy saved for IoT devices. For the offline version of the problem, where job information is known in advance, we formulate it as an Integer Linear Programming problem and propose an approximation algorithm, LHJS, with a constant performance guarantee. For the online version, where job information is only known upon release, we propose a heuristic algorithm, LBS, that is invoked whenever a job is released. Finally, we conduct experiments with parameters from real-world applications to evaluate their performance.

关键词： Mobile-Edge Computing Job Offloading and Scheduling with Deadlines approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Streaming Fair k-Center Clustering over Massive Dataset with Performance Guarantee 28th

Streaming Fair k-Center Clustering over Massive Dataset with...

引用

28th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD)

作者： Lin, Zeyu Guo, Longkun Jia, Chaoqi Fuzhou Univ Sch Math & Stat Fuzhou 350116 Peoples R China RMIT Univ Sch Accounting Informat Syst & Supply Chain Melbourne Vic 3000 Australia Qilu Univ Technol Sch Comp Sci Shandong Acad Sci Jinan 250316 Peoples R China

ISBN: (纸本)9789819722617;9789819722594

Emerging applications are imposing challenges for incorporating fairness constraints into k-center clustering in the streaming setting. Different from the traditional k-center problem, the fairness constraints require that the input points be divided into disjoint groups and the number of centers from each group is constrained by a given upper bound. Moreover, observing the applications of fair k-center inmassive datasets, we consider the problem in the streaming setting, where the data points arrive in a streaming manner that each point can be processed at its arrival. As themain contributions, we propose a two-pass streaming algorithm for the fair k-center problem with two groups, achieving an approximation ratio of 3 + epsilon and consuming only O(k log n) memory and O(k) update time, matching the state-of-art ratio for the offline setting. Then, we show that the algorithm can be easily improved to a one-pass streaming algorithm with an approximation ratio of 7+ epsilon and the same memory complexity and update time. Moreover, we show that our algorithm can be simply tuned to solve the case with an arbitrary number of groups while achieving the same ratio and space complexity. Lastly, we carried out extensive experiments to evaluate the practical performance of our algorithm compared with the state-of-the-art algorithms.

关键词： Fair k-center clustering Streaming algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Local Search algorithm for Radius-Constrained k-Median 18th

A Local Search Algorithm for Radius-Constrained k-Median

引用

18th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Chi, Gaojie Guo, Longkun Fuzhou Univ Fuzhou Peoples R China

ISBN: (纸本)9789819723393;9789819723409

Given a set X of n points in a metric space and a radius R, we consider the combining version of k-center and k-median which is with the same objective as k-median, but with the constraint that any x in X is assigned to a center within the range R. In this paper, we propose a bicriteria approximation algorithm achieving a bicriteria approximation ratio of (3 + epsilon, 7), by incorporating local search with the technology of finding key balls with consequent center exchanges therein. Compared to the state-of-the-art approximation ratio of (8, 4) that is based on an LP formulation for k-median, we improve the ratio of the total distance from 8 to 3 + epsilon at the price of compromising the ratio of radius from 4 to 7.

关键词： local search k-median k-center approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

The LP-rounding plus greed approach for partial optimization revisited

引用

Frontiers of Computer Science 2022年第1期16卷 67-75页

作者： Peng ZHANG School of Software Shandong UniversityJinan250101China

There are many optimization problems having the following common property:Given a total task consisting of many subtasks,the problem asks to find a solution to complete only part of these *** include the k-Forest problem and the k-Multicut problem,*** problems are called partial optimization problems,which are often *** this paper,we systematically study the LP-rounding plus greed approach,a method to design approximation algorithms for partial optimization *** approach is simple,powerful and *** show how to use this approach to design approximation algorithms for the k-Forest problem,the k-Multicut problem,the k-Generalized connectivity problem,etc.

关键词： k-Forest k-Multicut partial optimization LP-rounding Greedy algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：