Partitioning a network into k pieces is a fundamental problem in network science. A simple measure of partitioning a network is provided by the Max k-Uncut problem. Given an nvertex undirected graph G with nonnegative...
详细信息
Partitioning a network into k pieces is a fundamental problem in network science. A simple measure of partitioning a network is provided by the Max k-Uncut problem. Given an nvertex undirected graph G with nonnegative weights defined on edges, and a positive integer k, the Max k-Uncut problem asks to find a k-partition of the vertices of G to maximize the total weight of edges that are not in the cut. This problem is the complement of the classic Min k-Cut problem, and has close relation to many combinatorial optimization problems, including the famous Densest k-Subgraph problem. In this paper, we propose a greedy approximation algorithm for the Max k-Uncut problem with performance ratio 1 - 2(k-1) n . The algorithm is very simple, which consists of only k -1 min cut computations. The algorithm has fast running time O(kn2) and is hence implementable. The experimental results show that the algorithm has excellent practical performance. (c) 2023 Elsevier B.V. All rights reserved.
Realizing autonomic management control loops is pivotal for achieving self-driving networks. Some studies have recently evidence the feasibility of using Automated Planning (AP) to carry out these loops. However, in p...
详细信息
Realizing autonomic management control loops is pivotal for achieving self-driving networks. Some studies have recently evidence the feasibility of using Automated Planning (AP) to carry out these loops. However, in practice, the use of AP is complicated since network administrators, who are non-experts in Artificial Intelligence, need to define network management policies as AP-goals and combine them with the network status and network management tasks to obtain AP-problems. AP planners use these problems to build up autonomic solutions formed by primitive tasks that modify the initial network state to achieve management goals. Although recent approaches have investigated transforming network management policies expressed in specific languages into low-level configuration rules, transforming these policies expressed in natural language into AP-goals and, subsequently, build up AP-based autonomic management loops remains unexplored. This paper introduces a novel approach, called NORA, to automatically generate AP-problems by translating Goal Policies expressed in natural language into AP-goals and combining them with both the network status and the network management tasks. NORA uses Natural Language Processing as the translation technique and templates as the combination technique to avoid network administrators to learn policy languages or AP-notations. We used a dataset containing Goal Policies to evaluate the NORA's prototype. The results show that NORA achieves high precision and spends a short-time on generating AP-problems, which evinces NORA aids to overcome barriers to using AP in autonomic network management scenarios.
The set cover problem has been studied extensively for many years. Submodular function plays a key role in combinatorial optimization. Extending the set cover problem, we consider three submodular cover problems. The ...
详细信息
The set cover problem has been studied extensively for many years. Submodular function plays a key role in combinatorial optimization. Extending the set cover problem, we consider three submodular cover problems. The first two problems minimize linear and submodular functions, respectively, subject to the same non-submodular cover constraint. The third problem minimizes a submodular function subject to non-submodular cover and precedence constraints. Based on the concepts of submodular ratio and gap, and Lovasz extension, we devise greedy and primal-dual approximation algorithms for these problems.
Given a digraph G = (V, E), the k-path partition problem aims to find a minimum collection of vertex-disjoint directed paths, of order at most k, to cover all the vertices. The problem has various applications. Its sp...
详细信息
Given a digraph G = (V, E), the k-path partition problem aims to find a minimum collection of vertex-disjoint directed paths, of order at most k, to cover all the vertices. The problem has various applications. Its special case on undirected graphs is NP-hard when k >= 3, and has received much study recently from the approximation algorithm perspective. However, the general problem on digraphs is seemingly untouched in the literature. We fill the gap with the first k/2-approximation algorithm, based on a novel concept of enlarging walk to minimize the number of singletons. Secondly, for k = 3, we define a second novel kind of enlarging walks to greedily reduce the number of 2-paths in the 3-path partition and propose an improved 13/9-approximation algorithm. Lastly, for any k >= 7, we present an improved (k + 2)/3-approximation algorithm built on the maximum path-cycle cover followed by a careful 2-cycle elimination process. (c) 2024 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).
In this paper, we study a multiple-terminal extension of the classic Hamiltonian path problem where m salesmen are initially located at different depots and finally stopped at different terminals. To the best of our k...
详细信息
In this paper, we study a multiple-terminal extension of the classic Hamiltonian path problem where m salesmen are initially located at different depots and finally stopped at different terminals. To the best of our knowledge, only 2-approximation algorithm is available in the literature. For arbitrary m >= 2, we first present a Christofides-like heuristic with a tight approximation ratio of 2-1/2m+1. Besides, we also develop a (5/4 + epsilon)-approximation algorithm by divide-and-conquer technique. The (5/4 + epsilon) -approximation algorithm runs in polynomial time for fixed m and E. (C) 2019 Elsevier B.V. All rights reserved.
Base station location has a significant impact on network lifetime performance for a sensor network. For a multihop sensor network, this problem is particularly challenging due to its coupling with data routing. This ...
详细信息
Base station location has a significant impact on network lifetime performance for a sensor network. For a multihop sensor network, this problem is particularly challenging due to its coupling with data routing. This article presents an approximation algorithm that can guarantee (1-epsilon)-optimal network lifetime performance for base station placement problem with any desired error bound epsilon > 0. The proposed (1-epsilon)-optimal approximation algorithm is based on several novel techniques that makes it possible to reduce an infinite search space to a finite-element search space for base station location. The first technique used in this reduction is to discretize cost parameter (associated with energy consumption) with performance guarantee. Subsequently, the continuous search space can be broken up into a finite number of subareas. The second technique is to exploit the cost property of each subarea and represent it by a novel notion called fictitious cost point, each with guaranteed cost bounds. We give a proof that the proposed base station placement algorithm is (1-epsilon)-optimal. This approximation algorithm is simpler and faster than a state-of-the-art algorithm and represents the best known result to the base station placement problem.
The Gromov-Hausdorff distance (dGH) proves to be a useful distance measure between shapes. In order to approximate dGH for X, Y & SUB;Rd, we look into its relationship with dH,iso, the infimum Hausdorff distance u...
详细信息
The Gromov-Hausdorff distance (dGH) proves to be a useful distance measure between shapes. In order to approximate dGH for X, Y & SUB;Rd, we look into its relationship with dH,iso, the infimum Hausdorff distance under Euclidean isometries. As already known for dimension d & GE;2, dH,iso cannot be bounded above by a constant factor times dGH. For d = 1, however, we prove that dH,iso & LE;54dGH. We also show that the bound is tight. In effect, for X, Y & SUB;R with at most n points, this gives rise to an O (n log n)-time algorithm to approximate dGH(X, Y) with an approximation factor of (1 + 1 �. 4 & COPY;2023 Elsevier B.V. All rights reserved.
Colocation data centers (colocations, for short) are developing rapidly and have become ideal participants for emergency demand response (EDR) programs. However, even colocation operators wish to save energy, they can...
详细信息
Colocation data centers (colocations, for short) are developing rapidly and have become ideal participants for emergency demand response (EDR) programs. However, even colocation operators wish to save energy, they cannot achieve energy reduction without coordination from the tenants, because the servers in the colocations are owned and operated by the tenants. To solve the ?uncoordinated relationship? issue between operators and tenants, some works have been done by way of incentivizing the tenants to reduce the energy consumption of their servers. However, apart from servers, the power consumption of the cooling system also accounts for a large portion in a colocation, which should be optimized as well. Unfortunately, the servers and the cooling system are controlled by tenants and operators separately in colocations, and thus ?uncoordinated relationship? issue also exists between IT and cooling systems. In this paper, coarse-grained and fine-grained incentive mechanisms are proposed to solve these problems. approximation algorithms are developed to optimize the energy-saving problems. Furthermore, Vickrey?Clarke?Groves (VCG) theory is introduced into our incentive mechanism design to guarantee the feasibility and truthfulness of the two mechanisms. Trace-driven simulations are performed to validate the effectiveness of the two incentive mechanisms. The results show that compared with the existing incentive mechanisms, up to 20.50% of the energy-saving cost can be reduced in the coarse-grained mechanism and 28.34% of the cost reduction can be achieved in the fine-grained mechanism.
The traveling salesman problem (TSP) is a well studied NP-hard optimization problem. We present a novel heuristic to find approximate solutions for the case of the TSP with Euclidean metric. Our pair-center algorithm ...
详细信息
The traveling salesman problem (TSP) is a well studied NP-hard optimization problem. We present a novel heuristic to find approximate solutions for the case of the TSP with Euclidean metric. Our pair-center algorithm runs in quasi-linear time and on linear space. In practical experiments on a variety of well known benchmarks the algorithm shows linearithmic (i.e., O(n ( n log n ) ) runtime. The solutions found by the pair-center algorithm are very good on smaller problem instances, and better than those generated by any other heuristic with at most quadratic runtime. Eventually, the average gap of the pair-center algorithm on all benchmark instances with less than 1001 points is 0.94% and for all instances with more than 1000 points up to 100 million points is 4.57%.
As an important application of wireless sensor networks (WSNs), deployment of mobile sensors to periodically monitor (sweep cover) a set of points of interest (PoIs) arises in various applications, such as environment...
详细信息
As an important application of wireless sensor networks (WSNs), deployment of mobile sensors to periodically monitor (sweep cover) a set of points of interest (PoIs) arises in various applications, such as environmental monitoring and data collection. For a set of PoIs in an Eulerian graph, the point sweep coverage problem of deploying the fewest sensors to periodically cover a set of PoIs is known to be Non-deterministic Polynomial Hard (NP-hard), even if all sensors have the same velocity. In this paper, we consider the problem of finding the set of PoIs on a line periodically covered by a given set of mobile sensors that has the maximum sum of weight. The problem is first proven NP-hard when sensors are with different velocities in this paper. Optimal and approximate solutions are also presented for sensors with the same and different velocities, respectively. For M sensors and N PoIs, the optimal algorithm for the case when sensors are with the same velocity runs in O(MN) time;our polynomial-time approximation algorithm for the case when sensors have a constant number of velocities achieves approximation ratio 1/2;for the general case of arbitrary velocities, 1/2 alpha and 1/2(1-1/e) approximation algorithms are presented, respectively, where integer alpha >= 2 is the tradeoff factor between time complexity and approximation ratio.
暂无评论