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

Iterative Partial Rounding for Vertex Cover with Hard Capacities

algorithmICA 2021年第1期83卷 45-71页

作者： Kao, Mong-Jen Natl Chung Cheng Univ Dept Comp Sci & Informat Engn Chiayi Taiwan

We provide a simple and novel algorithmic design technique, for which we calliterative partial rounding, that gives a tight rounding-based approximation for vertex cover with hard capacities (VC-HC). In particular, we obtain anf-approximation for VC-HC on hypergraphs, improving over a previous results of Cheung et al. (In: SODA'14, 2014) to the tight extent. This also closes the gap of approximation since it was posted by Chuzhoy and Naor (Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS) 2002, pp. 481--489. IEEE Computer Society, 2002). Our main technical tool for establishing the approximation guarantee is a separation lemma that certifies the existence of a strong partition for solutions that are basic feasible in an extended version of the natural LP. We believe that our rounding technique is of independent interest when hard constraints are considered.

关键词： approximation algorithm Vertex cover Hard capacity Iterative rounding

来源：评论

学校读者我要写书评

暂无评论

One-exact approximate Pareto sets

引用

JOURNAL OF GLOBAL OPTIMIZATION 2021年第1期80卷 87-115页

作者： Herzel, Arne Bazgan, Cristina Ruzika, Stefan Thielen, Clemens Vanderpooten, Daniel Univ Kaiserslautern Dept Math Paul Ehrlich Str 14 D-67663 Kaiserslautern Germany Univ Paris 09 PSL Res Univ CNRS LAMSADE F-75016 Paris France Tech Univ Munich TUM Campus Straubing Biotechnol & Sustainabil Essigberg 3 D-94315 Straubing Germany

Papadimitriou and Yannakakis (Proceedings of the 41st annual IEEE symposium on the Foundations of Computer Science (FOCS), pp 86-92, 2000) show that the polynomial-time solvability of a certain auxiliary problem determines the class of multiobjective optimization problems that admit a polynomial-time computable (1+epsilon, ... , 1+epsilon)-approximate Pareto set (also called an epsilon-Pareto set). Similarly, in this article, we characterize the class of multiobjective optimization problems having a polynomial-time computable approximate epsilon-Pareto set that is exact in one objective by the efficient solvability of an appropriate auxiliary problem. This class includes important problems such as multiobjective shortest path and spanning tree, and the approximation guarantee we provide is, in general, best possible. Furthermore, for biobjective optimization problems from this class, we provide an algorithm that computes a one-exact epsilon-Pareto set of cardinality at most twice the cardinality of a smallest such set and show that this factor of 2 is best possible. For three or more objective functions, however, we prove that no constant-factor approximation on the cardinality of the set can be obtained efficiently.

关键词： Multiobjective optimization approximation algorithm Approximate Pareto set scalarization

来源：评论

学校读者我要写书评

暂无评论

Improved Coverage and Connectivity via Weighted Node Deployment in Solar Insecticidal Lamp Internet of Things

引用

IEEE INTERNET OF THINGS JOURNAL 2021年第12期8卷 10170-10186页

作者： Yang, Fan Shu, Lei Yang, Yuli Liu, Ye Gordon, Timothy Nanjing Agr Univ Coll Engn Nanjing 210031 Peoples R China Jiangsu Normal Univ Sch Math & Stat Xuzhou 221116 Jiangsu Peoples R China Nanjing Agr Univ NAU Lincoln Joint Res Ctr Intelligent Engn Nanjing 210031 Peoples R China Univ Lincoln Coll Sci Sch Engn Lincoln LN6 7TS England Univ Lincoln Sch Engn Lincoln LN6 7TS England Nanjing Agr Univ Sch Artificial Intelligence Nanjing 210031 Peoples R China

As an important physical control technology, solar insecticidal lamp (SIL) can effectively prevent and control the occurrence of pests. The combination of SILs and wireless sensor networks (WSNs) initiates a novel agricultural Internet of Things (IoT), i.e., SIL-IoTs, to simultaneously kill pests and transmit pest information. In this article, we study the weighted SIL deployment problem (wSILDP) in SIL-IoTs, where weighted locations on ridges are prespecified and some of them are selected to deploy SILs. Different from the existing studies whose optimization objective is to minimize the deployment cost, we consider the deployment cost and the total weight of selected locations jointly. We formulate the wSILDP as the weighted set cover (WSC) problem and propose a layered deployment method based on greedy algorithm (LDMGA) to solve the defined optimization problem. The LDMGA is composed of two phases. First, SILs are deployed layer by layer from the boundary to the center until the entire farmland is completely covered. Second, on the basis of three design operations, i.e., substitution, deletion and fusion, the suboptimal locations obtained in the first phase are fine-tuned to achieve the minimum deployment cost together with the maximum total weight for meeting the coverage and connectivity requirements. Simulation results clearly demonstrate that the proposed method outperforms three peer algorithms in terms of deployment cost and total weight.

关键词： Internet of Things Wireless sensor networks Agriculture Peer-to-peer computing Heuristic algorithms approximation algorithms Optimization approximation algorithm restricted deployment locations solar insecticidal lamps Internet of Things (SIL-IoTs) weighted set cover (WSC) problem weighted SIL deployment problem (wSILDP) wireless sensor network (WSN)

来源：评论

学校读者我要写书评

暂无评论

Application-Driven Provisioning of Service Function Chains Over Heterogeneous NFV Platforms

引用

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT 2021年第3期18卷 3037-3048页

作者： Dong, Lu da Fonseca, Nelson L. S. Zhu, Zuqing Univ Sci & Technol China Sch Informat Sci & Technol Hefei 230027 Peoples R China Univ Estadual Campinas Inst Comp BR-13083852 Campinas Brazil

Although network function virtualization (NFV) has been proven to be beneficial in terms of equipment cost, service delivery flexibility, and time-to-market, most of the studies in this area only addressed homogeneous NFV platforms (e.g., with virtual machines (VMs) only). In this work, we argue that by leveraging heterogeneous NFV platforms such as VMs, docker containers, and programmable hardware accelerators (e.g., SmartNICs), one could achieve better flexibility and cost-effectiveness to support virtual network function service chains (vNF-SCs) with various quality-of-service (QoS) requirements. Therefore, we study application-driven provisioning of vNF-SCs over heterogeneous NFV platforms, and design a polynomial-time approximation algorithm to tackle the problem for near-optimal solutions. We first introduce a layered auxiliary graph (LAG) based approach to model the problem of vNF-SC provisioning, and then formulate a novel integer linear programming (ILP) model based on it. Specifically, the ILP model minimizes the total cost of vNF-SC deployment while ensuring that the QoS requirements of all the vNF-SCs are satisfied. To solve the ILP time-efficiently, we propose an approximation algorithm based on linear programming (LP) relaxation and randomized rounding. Extensive simulations confirm that with significantly improved time-efficiency, our proposed algorithm can provide near-optimal solutions whose gaps to the exact ones are bounded.

关键词： approximation algorithms Quality of service Network function virtualization Containers Hardware Optimization Heuristic algorithms Network function virtualization (NFV) heterogeneous NFV platforms service function chaining approximation algorithm linear relaxation

来源：评论

学校读者我要写书评

暂无评论

Hybrid Flow Table Installation: Optimizing Remote Placements of Flow Tables on Servers to Enhance PDP Switches for In-Network Computing

引用

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT 2021年第1期18卷 429-440页

作者： Xue, Yuhan Zhu, Zuqing Univ Sci & Technol China Sch Informat Sci & Technol Hefei 230027 Peoples R China

Recently, the programmable data plane (PDP) switches have been considered as the key enablers for in-network computing. However, the limited memory resources in them for flow tables might restrict their performance. This work addresses this challenge by studying how to optimize the placements of flow tables in the external memory on multiple servers, and to access them with remote direct memory access (RDMA) for ensuring low latency. Specifically, we consider a data-center network (DCN) that uses PDP switches as top-of-rack (ToR) switches, and propose and optimize the hybrid flow table installation (hFT-INST) on each ToR switch. With hFT-INST, the switch can either store flow tables in its local memory or use RDMA to install and access them remotely in its rack servers. We first design the protocol and operation procedure of hFT-INST. Then, regarding the key problem of hFT-INST, i.e., how to place the flow tables on the external memory on different servers, we take a few practical parameters into account, and formulate a mixed integer linear programming (MILP) model to tackle it. Next, the optimization in the MILP is transformed into a capacitated facility location problem (CFLP) with additional constraints. We further transform it into a k-median problem through pre-processing, and design a polynomial-time approximation algorithm to solve the problem. Extensive simulations confirm the performance of our proposed algorithm. We also prototype our design of the hFT-INST, and conduct experiments to demonstrate its feasibility.

关键词： Software-defined networking (SDN) in-network computing P4 programmable data plane (PDP) remote direct memory access (RDMA) approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A metric approach for scheduling problems with minimizing the maximum penalty

引用

APPLIED MATHEMATICAL MODELLING 2021年第Part2期89卷 1163-1176页

作者： Lazarev, Alexander A. Lemtyuzhnikova, Darya V. Werner, Frank Inst Control Sci 65 Profsoyuznaya St Moscow 117997 Russia Moscow Inst Aviat Technol 4 Volokolamsk Highway Moscow 125993 Russia Otto von Guericke Univ Fak Math Magdeburg 39016 Russia

NP-hard scheduling problems with the criterion of minimizing the maximum penalty, e.g. maximum lateness, are considered. For such problems, a metric which delivers an upper bound on the absolute error of the objective function value is introduced. Taking the given instance of some problem and using the introduced metric, the nearest instance is determined for which a polynomial or pseudo-polynomial algorithm is known. A schedule is constructed for this determined instance which is then applied to the original instance. It is shown how this approach can be applied to different scheduling problems. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Scheduling Minimization of maximum penalty Maximum lateness Metric approach approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Beampattern Synthesis via the Constrained Subarray Layout Optimization

引用

IEEE TRANSACTIONS ON ANTENNAS AND PROPAGATION 2021年第1期69卷 182-194页

作者： Feng, Lifang Cui, Guolong Yu, Xianxiang Kong, Lingjiang Univ Elect Sci & Technol China Sch Informat & Commun Engn Chengdu 611731 Peoples R China

This article deals with a joint design of subarray layout vector (LV) and weighted coefficient of radiation element (RE) to achieve desired beampattern for a new array architecture. We first present an architecture of thinned array composed of multiple regular subarrays (ACMRS) and establish corresponding subarray layout and beampattern models. Then, we formulate a new optimization problem aiming to minimize the peak sidelobe level (PSL) and the LV norm under the constraints of power beampattern and subarray layout. The resulting problem is quite challenging to solve due to the highly nonconvex discrete LV and double-sided quadratic constraints. In this respect, we formulate the resultant hybrid optimization problem into a new alternating direction method of multipliers (ADMM) form via introducing a series of auxiliary variables, and propose an approximation algorithm based on ADMM. In each iteration of the proposed ADMM, the tractable and small-sized subproblems are globally or locally solved in parallel. Finally, numerical simulations show that the proposed method can obtain a lower PSL beampattern and a thinner (i.e., fewer REs or subarrays) array while satisfying the given constraints. Furthermore, fullwave simulation also shows that it has good reliability in the application of beampattern synthesis for real array.

关键词： Alternating direction method of multipliers (ADMM) approximation algorithm beampattern synthesis hybrid optimization problem subarray layout thinned array weight vector design

来源：评论

学校读者我要写书评

暂无评论

A three-stage supply chain scheduling problem based on the nursing assistants' daily work in a hospital

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2021年第4期42卷 896-908页

作者： Fan, Jing Shi, Hui Shanghai Polytech Univ Shanghai 201209 Peoples R China Shanghai Jiao Tong Univ Sch Med Shanghai Gen Hosp Shanghai 200080 Peoples R China

In a hospital, the nursing assistants in wards are always responsible for delivering patients to do some medical examinations, and the nursing assistants in the medical departments need take these patients back to the corresponding wards after examinations. We transform this actual problem about nursing assistants' daily work into a three-stage supply chain scheduling problem if patients are regarded as jobs, the ward as the customer, the nursing assistants as vehicles and the medical department as the processing machine in the factory. The capacity of each vehicle is limited because the nursing assistant only can deliver several patients once. And the transportation schedule back and forth between the customer and the factory are the same in view of the actual arrangement. In order to reduce the average consumption time of patients, the objective is to minimize the total flowtime, that is, the sum of arrival time of every completed job back to the customer. We show that the problem is NP-hard in the strong sense, and provide an approximation algorithm with the performance ratio of 2. Moreover, we study some polynomially solvable cases of the problem.

关键词： Three-stage supply chain scheduling problem Strongly NP-hard approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Estimating the Clustering Coefficient Using Sample Complexity Analysis 15th

Estimating the Clustering Coefficient Using Sample Complexit...

引用

15th Latin American Symposium on Theoretical Informatics

作者： de Lima, Alane M. da Silva, Murilo V. G. Vignatti, Andre L. Univ Fed Parana Dept Comp Sci Curitiba Parana Brazil

ISBN: (纸本)9783031206238;9783031206245

In this work we present a sampling algorithm for estimating the local clustering of each vertex of a graph. Let G be a graph with n vertices, m edges, and maximum degree Delta. We present an algorithm that, given G and fixed constants 0 < epsilon, delta, p < 1, outputs the values for the local clustering coefficient within epsilon error with probability 1 - delta, for every vertex v of G, provided that the (exact) local clustering of v is not "too small." We use VC dimension theory to give a bound for the number of edges required to be sampled by the algorithm. We show that the algorithm runs in time O(Delta lg Delta+m). We also show that the running time drops to, possibly, sublinear time if we restrict G to belong to some well-known graph classes. In particular, for planar graphs the algorithm runs in time O(Delta). In the case of bounded-degree graphs the running time is O(1) if a bound for the value of Delta is given as a part of the input, and O(n) otherwise.

关键词： Clustering coefficient approximation algorithm Sampling VC dimension

来源：评论

学校读者我要写书评

暂无评论

Color-Spanning Problem for Line Segments 22nd

Color-Spanning Problem for Line Segments

引用

22nd International Conference on Computational Science and its Applications (ICCSA)

作者： Maji, Sukanya Sadhu, Sanjib Natl Inst Technol Durgapur Dept CSE Durgapur India

ISBN: (纸本)9783031105227;9783031105210

The color-spanning problem for a given set of colored geometric objects finds a region that contains at least one object of each color. This paper studies the color-spanning problem for a given set of colored line segments L lying in R-2. For n line segments, each associated with any of m colors (3 <= m < n), we compute (i) one (resp. two congruent disjoint) color-spanning vertical strip (resp. strips) of minimum width in O(n) time after O(n log n) preprocessing task, (ii) one (resp. two congruent disjoint) color-spanning axis parallel square (resp. squares) of minimum perimeter in O(n(n - m)) (resp. O(n(3))) time. The same results also exist if the inputs to the aforesaid problems are n simple polygons or disks. Our algorithm improved the time complexity of finding the minimum perimeter color-spanning square problem for the segments [1] by log n factor. Finally, we show the root 2 approximation algorithm for computing one (resp. two congruent disjoint) color-spanning disk (resp. disks) of minimum radius for L.

关键词： Computational geometry Color-spanning objects Line sweeping approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：