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

IEEE 96th Vehicular Technology Conference (VTC-Fall)

作者： Roy, Bodhayan Suppakitpaisarn, Vorapong Manna, Bubai Nguyen, Cam Ly IIT Kharagpur Kharagpur W Bengal India Univ Tokyo Tokyo Japan Criteo KK Tokyo Japan

ISBN: (纸本)9781665454681

Several works recently focus on monitoring air quality of critical areas using sensors attached to buses. They aim to monitor the maximum number of critical areas using a limited number of sensors. In practice, we may want to have information for all critical areas. We work on the problem of covering all the areas using the minimum number of sensors in this work. We show that, even when the bus routes are not pre-defined, the problem is NP-hard and is significantly harder than the problem of the previous works. Then, we develop two algorithms for the case that the routes are pre-defined. Those algorithms include a fixed parameter tractability and a 2-approximation algorithm for a special case of the problem. Our experiment results show that, although we usually give the similar number of sensors as the algorithm in the previous works, our algorithms have a shorter computation time than the classical greedy algorithm.

关键词： Sensor Networks Air Quality Monitoring Minimum Target Coverage approximation algorithm Fixed-Parameter Tractability

来源：评论

学校读者我要写书评

暂无评论

The Smallest Grammar Problem Revisited

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2021年第1期67卷 317-328页

作者： Bannai, Hideo Hirayama, Momoko Hucke, Danny Inenaga, Shunsuke Jez, Artur Lohrey, Markus Reh, Carl Philipp Tokyo Med & Dent Univ Dept Data Sci Algorithm Design & Anal Tokyo 1138510 Japan Kyushu Univ Dept Informat Fukuoka 8190395 Japan Univ Siegen Dept Elect Engn & Comp Sci D-57076 Siegen Germany Univ Wroclaw Inst Comp Sci PL-50383 Wroclaw Poland

In a seminal paper, Charikar et al. derive upper and lower bounds on the approximation ratios for several grammar-based compressors, but in all cases there is a gap between the lower and upper bound. Here the gaps for LZ78 and BISECTION are closed by showing that the approximation ratio of LZ78 is Theta((n/log n)(2/3)), whereas the approximation ratio of BISECTION is Theta(n/log n). In addition, the lower bound for RePair is improved from Omega(root log n) to Omega(log n/ log log n). Finally, results of Arpe and Reischuk relating grammar-based compression for arbitrary alphabets and binary alphabets are improved.

关键词： String compression smallest grammar problem approximation algorithm LZ78 RePair

来源：评论

学校读者我要写书评

暂无评论

Improved Streaming algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint

引用

algorithmICA 2021年第3期83卷 879-902页

作者： Huang, Chien-Chung Kakimura, Naonori CNRS Ecole Normale Super Paris France Keio Univ Yokohama Kanagawa Japan

In this paper, we consider the problem of maximizing amonotone submodular function subject to a knapsack constraint in a streaming setting. In such a setting, elements arrive sequentially and at any point in time, and the algorithm can store only a small fraction of the elements that have arrived so far. For the special case that all elements have unit sizes (i.e., the cardinality-constraint case), one can find a (0.5 - epsilon)-approximate solution in O( K epsilon(-1)) space, where K is the knapsack capacity (Badanidiyuru et al. KDD 2014). The approximation ratio is recently shown to be optimal (Feldman et al. STOC 2020). In thiswork, we propose a (0.4 - epsilon)-approximation algorithm for the knapsackconstrained problem, using space that is a polynomial of K and epsilon. This improves on the previous best ratio of 0.363 - epsilon with space of the same order. Our algorithm is based on a careful combination of various ideas to transform multiple-pass streaming algorithms into a single-pass one.

关键词： Submodular functions Streaming algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimizing Redundant Sensing Data Transmissions in Energy-Harvesting Sensor Networks via Exploring Spatial Data Correlations

引用

IEEE INTERNET OF THINGS JOURNAL 2021年第1期8卷 512-527页

作者： Guo, Zhenjie Peng, Jian Xu, Wenzheng Liang, Weifa Wu, Weigang Xu, Zichuan Guo, Bing Wu, Yue Ivan Sichuan Univ Coll Comp Sci Chengdu 610065 Peoples R China Australian Natl Univ Res Sch Comp Sci Canberra ACT 2601 Australia Sun Yat Sen Univ Key Lab Machine Intelligence & Adv Comp Sch Data & Comp Sci Guangdong Prov Key Lab Big Data Anal & Proc Guangzhou 510006 Peoples R China Sun Yat Sen Univ Guangzhou 510006 Peoples R China Dalian Univ Technol Sch Software Dalian 116024 Peoples R China

Energy harvesting rates of sensors in renewable (e.g., solar energy) wireless sensor networks are not only lower than their energy consumption rates but also temporally varying. Existing studies exploited spatial data correlations among sensors to reduce their energy consumptions, where the data correlations mean that the sensing data of nearby sensors have high similarities. They assumed that the sensing data of nearby sensors are very likely to highly correlated. They adopted a coarse-grained spatial-correlation model, in which sensors are partitioned into different clusters such that the sensors in the same cluster have high data similarities with each other. Then, only the sensor with the maximum residual energy in each cluster sends its sensing data, while the other sensors do not. We, however, notice that the data similarities among nearby sensors in real sensor networks may vary significantly, i.e., ranging from very similar to not similar at all. Since the existing algorithms require that the sensors in the same cluster have high data similarities with each other, the sensors in a network may be partitioned into many clusters and each cluster consists of only a few sensors, where two nearby sensors belong to two different clusters if the sensing data of the two sensors are not highly correlated. Therefore, in the existing studies, many sensors have to send all their data as there are many clusters. Unlike the existing studies, in this article, we first propose a fine-grained spatial correlation model, in which sensors are partitioned into only a few clusters and each cluster consists of many sensors. Then, each cluster master sensor sends all its data to the sink, while the majority of other sensors in the cluster transmit only their nonredundant data, thereby significantly saving sensor energy consumptions. We formulate a novel sensor clustering problem under the proposed model, which is to partition sensors into different clusters and choose a representati

关键词： approximation algorithm energy-harvesting sensor networks redundant sensing data spatial data correlations

来源：评论

学校读者我要写书评

暂无评论

Makespan minimization with OR-precedence constraints

引用

JOURNAL OF SCHEDULING 2021年第3期24卷 319-328页

作者： Happach, Felix Tech Univ Munich Sch Management Dept Math Munich Germany

We consider a variant of the NP-hard problem of assigning jobs to machines to minimize the completion time of the last job. Usually, precedence constraints are given by a partial order on the set of jobs, and each job requires all its predecessors to be completed before it can start. In this paper, we consider a different type of precedence relation that has not been discussed as extensively and is called OR-precedence. In order for a job to start, we require that at least one of its predecessors is completed-in contrast to all its predecessors. Additionally, we assume that each job has a release date before which it must not start. We prove that a simple List Scheduling algorithm due to Graham (Bell Syst Tech J 45(9):1563-1581, 1966) has an approximation guarantee of 2 and show that obtaining an approximation factor of 4/3 - epsilon is NP-hard. Further, we present a polynomial-time algorithm that solves the problem to optimality if preemptions are allowed. The latter result is in contrast to classical precedence constraints where the preemptive variant is already NP-hard. Our algorithm generalizes previous results for unit processing time jobs subject to OR-precedence constraints, but without release dates. The running time of our algorithm is O(n(2)) for arbitrary processing times and it can be reduced to O(n) for unit processing times, where n is the number of jobs. The performance guarantees presented here match the best-known ones for special cases where classical precedence constraints and OR-precedence constraints coincide.

关键词： Scheduling Precedence constraints approximation algorithm Makespan

来源：评论

学校读者我要写书评

暂无评论

On the Upgrade of Service Function Chains With Heterogeneous NFV Platforms

引用

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT 2021年第4期18卷 4311-4323页

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

The fast development of high-performance and flexible SmartNICs and programmable data plane switches (PDP-SWs) has motivated people to consider the deployment of virtual network functions (vNFs) on them. Hence, together with traditional virtual machines (VMs), SmartNICs and PDP-SWs form heterogeneous network function virtualization (NFV) platforms for realizing vNF service chains (vNF-SCs). In this work, we consider the transition from software-based homogeneous NFV platforms to the heterogeneous ones, and study how to optimize the service upgrade of vNF-SCs. Specifically, the service upgrade is divided into two steps, which are 1) selecting servers/switches in the substrate network (SNT) to upgrade, which is done by adding SmartNICs to servers and replacing traditional switches with PDP-SWs, under a fixed budget, and 2) redeploying the existing vNF-SCs in the updated SNT to maximize the quality-of-service (QoS) improvement on latency reductions. We first formulate an integer linear programming (ILP) model to optimize the overall service upgrade, then design two correlated optimizations for its two steps, and finally propose polynomial-time approximation algorithms to solve the optimizations. The results of extensive simulations confirm that our proposed algorithm outperforms the existing benchmarks in various network scenarios, and achieves better tradeoff between performance and time-efficiency.

关键词： Hardware Optimization approximation algorithms Heuristic algorithms Substrates Quality of service Servers Network function virtualization (NFV) heterogeneous NFV platforms service function chain (SFC) approximation algorithm facility location multiple knapsack linear programming (LP) relaxation and randomized rounding

来源：评论

学校读者我要写书评

暂无评论

AN EXACT algorithm FOR STABLE INSTANCES OF THE k-MEANS PROBLEM WITH PENALTIES IN FIXED-DIMENSIONAL EUCLIDEAN SPACE

引用

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION 2021年第5期18卷 3487-3498页

作者： Yuan, Fan Xu, Dachuan Du, Donglei Li, Min Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China Beijing Univ Technol Beijing Inst Sci & Engn Comp Beijing 100124 Peoples R China Univ New Brunswick Fac Management Fredericton NB E3B 5A3 Canada Shandong Normal Univ Sch Math & Stat Jinan 250014 Shandong Peoples R China

We study stable instances of the k-means problem with penalties in fixed-dimensional Euclidean space. An instance of the problem is called alpha-stable if this instance exists a sole optimal solution and the solution keeps unchanged when distances and penalty costs are scaled by a factor of no more than alpha. Stable instances of clustering problem have been used to explain why certain heuristic algorithms with poor theoretical guarantees perform quite well in practical. For any fixed epsilon > 0, we show that when using a common multi-swap local-search algorithm, a (1 + epsilon)-stable instance of the k-means problem with penalties in fixed-dimensional Euclidean space can be solved accurately in polynomial time.

关键词： Local search stable instance k-means approximation algorithm fixed-dimensional Euclidean space

来源：评论

学校读者我要写书评

暂无评论

Deterministic and Randomized Actuator Scheduling With Guaranteed Performance Bounds

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2021年第4期66卷 1686-1701页

作者： Siami, Milad Olshevsky, Alexander Jadbabaie, Ali Northeastern Univ Dept Elect & Comp Engn Boston MA 02115 USA MIT Inst Data Syst & Soc 77 Massachusetts Ave Cambridge MA 02139 USA

In this article, we investigate the problem of actuator selection for linear dynamical systems. We develop a framework to design a sparse actuator schedule for a given large-scale linear system with guaranteed performance bounds using deterministic polynomial-time and randomized approximately linear-time algorithms. First, we introduce systemic controllability metrics for linear dynamical systems that are monotone and homogeneous with respect to the controllability Gramian. We show that several popular and widely used optimization criteria in the literature belong to this class of controllability metrics. Our main result is to provide a polynomial-time actuator schedule that on average selects only a constant number of actuators at each time step, independent of the dimension, to furnish a guaranteed approximation of the controllability metrics in comparison to when all actuators are in use. Our results naturally apply to the dual problem of sensor selection, in which we provide a guaranteed approximation to the observability Gramian. We illustrate the effectiveness of our theoretical findings via several numerical simulations using benchmark examples.

关键词： Actuators Controllability Robot sensing systems Observability Schedules Measurement Linear systems approximation algorithm complexity theory controllability dynamic scheduling linear dynamical systems sparse sensor and actuator selections

来源：评论

学校读者我要写书评

暂无评论

Strategy-proof mechanism for time-varying batch virtual machine allocation in clouds

引用

CLUSTER COMPUTING-THE JOURNAL OF NETWORKS SOFTWARE TOOLS AND APPLICATIONS 2021年第4期24卷 3709-3724页

作者： Zhang, Jixian Xie, Ning Yang, Xutao Zhang, Xuejie Li, Weidong Yunnan Univ Sch Informat Sci & Engn Kunming 650504 Yunnan Peoples R China Yunnan Univ Sch Math & Stat Kunming 650504 Yunnan Peoples R China

Time-varying resource allocation allows users to define their own unique resource requirement plans during different time periods. This mode of allocation can increase the flexibility of resource usage and reduce resource usage costs for users. Moreover, combining this approach with an auction mechanism can enable resource providers to obtain greater social welfare and benefits;therefore, such resource allocation has become a hot topic in cloud computing. This paper addresses the problem of time-varying batch virtual machine (VM) allocation and pricing in the cloud. Specifically, (1) we propose a novel integer programming model for the time-varying batch VM allocation problem, and (2) we design two truthful auction mechanisms to solve the allocation and pricing problem in a competitive environment. The optimal mechanism includes a dynamic programming (DP)-based resource allocation algorithm and a Vickrey-Clarke-Groves (VCG)-based payment price algorithm. Meanwhile, we also design a greedy mechanism that includes a dominant-resource-based allocation algorithm and a dichotomy-based payment price algorithm. We prove the economic characteristics, including truthfulness and individual rationality, of the above two mechanisms. Furthermore, we prove the approximation ratio of the allocation algorithm in the greedy mechanism. Compared to state-of-the-art research, our approach is characterized by high social welfare, a high served user ratio and a short execution time.

关键词： Cloud computing Time-varying batch VM allocation Truthful mechanism Dominant resources approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Security-Aware Planning of Packet-Over-Optical Networks in Consideration of OTN Encryption

引用

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

作者： Chen, Feng Song, Man Zhou, Fen Zhu, Zuqing Univ Sci & Technol China Sch Informat Sci & Technol Hefei 230027 Peoples R China Univ Lille Ctr Digital Syst Inst Mines Tlcom IMT Lille Douai F-59000 Lille France

The fast development of cloud computing and Big Data applications has promoted virtualization technologies such as network function virtualization (NFV), which in turn dramatically increased the amount of sensitive data being transmitted over the optical networks for datacenter interconnections (DCIs). To ensure the physical-layer security in DCIs, people have developed optical transport network (OTN) encryption technologies, i.e., leveraging high-speed encryption cards (ECs) to encrypt OTN payload frames. Although experimental studies have confirmed the benefits of ECs in terms of line-speed processing, low latency, and small encryption overhead, the problem of how to utilize them to build a secure packet-over-optical network with high cost-effectiveness has not been explored yet. In this paper, we study how to realize cost-effective and security-aware multilayer planning in a packet-over-optical network that covers both trusted and untrusted zones, in consideration of OTN encryption. We first formulate an integer linear programming (ILP) model to minimize the total capital expenditure (CAPEX) of the multilayer planning, which includes the costs of OTN linecards (LCs), ECs, and bandwidth resources, and solve the optimization exactly. Then, we prove the NP-hardness of the multilayer planning, and to reduce the time complexity, we propose a column generation (CG) model and design a more time-efficient approximation algorithm based on it. Our simulation results confirm the performance and advantages of our CG-based proposal, i.e., it is much more time-efficient than solving the ILP directly, and outperform the existing heuristic in terms of total CAPEX and costs of used LCs and ECs.

关键词： Multilayer network planning optical transport network (OTN) OTN encryption physical-layer security column generation approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：