Algorithms for Exploiting Approximate Network Structure
Abstract
This project proposes a new framework for efficient, robust, and noise-tolerant network algorithms that guarantee near-optimal solutions to NP-hard problems by exploiting structure inherent in real-world networks. Specifically, it aims to bridge the gap between ÒmessyÓ real networks and the very rigid structural graph classes shown to be algorithmically useful in theoretical computer science. The projectÕs primary approach is to model real-world networks as consisting of a majority that belongs to a structural graph class, plus a few deviations resulting from measurement errors, unusual behaviors, and/or unexplained exceptions. Using this, the PIs will develop algorithms which exploit this more approximate form of graph structure and guarantee near- optimal solutions and polynomial running time for any network that is ÒcloseÓ to a structural graph class. To this end, the project will develop two families of approximation algorithms for several well-studied structural graph classes. The first will automatically isolate the deviations from the highly structured majority of a network, that is, approximating a notion of Òedit distanceÓ to a graph class. The second will solve desired optimization problems with guaranteed trade- offs between the amount of deviation and quality of produced solutions. The PIs believe these approaches will be applicable to a variety of important structural classes. This project will focus on graph classes arising naturally from hierarchical or Òtree- likeÓ networks, in particular using bounded tree-width and its specializations to model the structured majority. The PIs will implement and validate developed algorithms on real-world and synthetic data, focusing on networks with hypothesized tree-like structure, and plan to release all code on a community version control repository under a permissive open source license.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Oct 11, 2018
- Source ID
- W911NF1710271
Entities
People
- Vida Blair Sullivan
Organizations
- Army Contracting Command
- Defense Advanced Research Projects Agency
- North Carolina State University