This paper presents an open-source, parallel AI environment (named OpengraphGym) to facilitate the application of reinforcement learning (RL) algorithms to address combinatorial graph optimization problems. This envir...
详细信息
ISBN:
(纸本)9783030867973;9783030504250
This paper presents an open-source, parallel AI environment (named OpengraphGym) to facilitate the application of reinforcement learning (RL) algorithms to address combinatorial graph optimization problems. This environment incorporates a basic deep reinforcement learning method, and several graph embeddings to capture graph features, it also allows users to rapidly plug in and test new RL algorithms and graph embeddings for graph optimization problems. This new open-source RL framework is targeted at achieving both high performance and high quality of the computed graph solutions. This RL framework forms the foundation of several ongoing research directions, including 1) benchmark works on different RL algorithms and embedding methods for classic graphproblems;2) advanced parallel strategies for extreme-scale graph computations, as well as 3) performance evaluation on real-world graph solutions.
With the maturity and popularity of Internet of Things (IoT), the notion of Social Internet of Things (SIoT) has been proposed to support novel applications and networking services for the IoT in more effective and ef...
详细信息
With the maturity and popularity of Internet of Things (IoT), the notion of Social Internet of Things (SIoT) has been proposed to support novel applications and networking services for the IoT in more effective and efficient ways. Although there are many works for SIoT, they focus on designing the architectures and protocols for SIoT under the specific schemes. How to efficiently utilize the collaboration capability of SIoT to complete complex tasks remains unexplored. Therefore, we propose a new problem family, namely, Task-Optimized SIoT Selection (TOSS), to find the best group of IoT objects for a given set of tasks in the task pool. TOSS aims to select the target SIoT group such that the target SIoT group is able to easily communicate with each other while maximizing the accuracy of performing the given tasks. We propose two problem formulations, named Bounded Communication-loss TOSS (BC-TOSS) and Robustness Guaranteed TOSS (RG-TOSS), for different scenarios and prove that they are both NP-hard and inapproximable. We propose a polynomial-time algorithm with a performance guarantee for BC-TOSS, and an efficient polynomial-time algorithm to obtain good solutions for RG-TOSS. Moreover, as RG-TOSS is NP-hard and inapproximable within any factor, we further propose Structure-Aware Reinforcement Learning (SARL) to leverage the graph Convolutional Networks (GCN) and Deep Reinforcement Learning (DRL) to effectively solve RG-TOSS. Further, since we use graph models to simulate the problem instance for DRL, which is different from the real ones, we propose Structure-Aware Meta Reinforcement Learning (SAMRL) for fast adapting to new domains. Experimental results on multiple real datasets indicate that our proposed algorithms outperform the other deterministic and learning-based baseline approaches.
We study the verification problem in distributed networks, stated as follows. Let H be a subgraph of a network G where each vertex of G knows which edges incident on it are in H. We would like to verify whether H has ...
详细信息
We study the verification problem in distributed networks, stated as follows. Let H be a subgraph of a network G where each vertex of G knows which edges incident on it are in H. We would like to verify whether H has some properties, e. g., if it is a tree or if it is connected (every node knows at the end of the process whether H has the specified property or not). We would like to perform this verification in a decentralized fashion via a distributed algorithm. The time complexity of verification is measured as the number of rounds of distributed communication. In this paper we initiate a systematic study of distributed verification and give almost tight lower bounds on the running time of distributed verification algorithms for many fundamental problems such as connectivity, spanning connected subgraph, and s-t cut verification. We then show applications of these results in deriving strong unconditional time lower bounds on the hardness of distributed approximation for many classical optimizationproblems including minimum spanning tree (MST), shortest paths, and minimum cut. Many of these results are the first nontrivial lower bounds for both exact and approximate distributed computation, and they resolve previous open questions. Moreover, our unconditional lower bound of approximating MST subsumes and improves upon the previous hardness of approximation bound of Elkin [M. Elkin, SIAM J. Comput., 36 (2006), pp. 433-456] as well as the lower bound for (exact) MST computation of Peleg and Rubinovich [D. Peleg and V. Rubinovich, SIAM J. Comput., 30 (2000), pp. 1427-1442]. Our result implies that there can be no distributed approximation algorithm for MST that is significantly faster than the current exact algorithm for any approximation factor. Our lower bound proofs show an interesting connection between communication complexity and distributed computing which turns out to be useful in establishing the time complexity of exact and approximate distributed computati
Borodin et al. (Algorithmica 37(4):295-326, 2003) gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin (Algorithmica 40(4):271-291, 2004) extended their work to facility location...
详细信息
Borodin et al. (Algorithmica 37(4):295-326, 2003) gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin (Algorithmica 40(4):271-291, 2004) extended their work to facility location and set cover problems. We generalize their model to include other optimizationproblems, and apply the generalized framework to graphproblems. Our goal is to define an abstract model that captures the intrinsic power and limitations of greedy algorithms for various graph optimization problems, as Borodin et al. (Algorithmica 37(4):295-326, 2003) did for scheduling. We prove bounds on the approximation ratio achievable by such algorithms for basic graphproblems such as shortest path, weighted vertex cover, Steiner tree, and independent set. For example, we show that, for the shortest path problem, no algorithm in the FIXED priority model can achieve any approximation ratio (even one dependent on the graph size), but the well-known Dijkstra's algorithm is an optimal ADAPTIVE priority algorithm. We also prove that the approximation ratio for weighted vertex cover achievable by ADAPTIVE priority algorithms is exactly 2. Here, a new lower bound matches the known upper bounds (Johnson in J. Comput. Syst. Sci. 9(3):256-278, 1974). We give a number of other lower bounds for priority algorithms, as well as a new approximation algorithm for minimum Steiner tree problem with weights in the interval [1,2].
Our motivation for this work is the remarkable discovery that many large-scale real-world graphs ranging from Internet and World Wide Web to social and biological networks appear to exhibit a power-law distribution: t...
详细信息
Our motivation for this work is the remarkable discovery that many large-scale real-world graphs ranging from Internet and World Wide Web to social and biological networks appear to exhibit a power-law distribution: the number of nodes y(i) of a given degree i is proportional to i(-beta) where beta > 0 is a constant that depends on the application domain. There is practical evidence that combinatorial optimization in power-law graphs is easier than in general graphs, prompting the basic theoretical question: Is combinatorial optimization in power-law graphs easy? Does the answer depend on the power-law exponent beta? Our main result is the proof that many classical NP-hard graph-theoretic optimizationproblems remain NP-hard on power-law graphs for certain values of beta. In particular, we show that some classical problems, such as CLIQUE and COLORING, remain NP-hard for all beta >= 1. Moreover, we show that all the problems that satisfy the so-called "optimal substructure property" remain NP-hard for all beta >= 0. This includes classical problems such as MINIMUM VERTEX COVER, MAXIMUM INDEPENDENT SET, and MINIMUM DOMINATING SET. Our proofs involve designing efficient algorithms for constructing graphs with prescribed degree sequences that are tractable with respect to various optimizationproblems. (C) 2007 Elsevier B.V. All rights reserved.
暂无评论