Antagonistic Graph Coloring Under Uncertainty
Abstract
The primary aim of the proposed research is to develop mathematical models and related computational techniques for a specialized class of graph-theoretic models. Specifically, we are concerned with determining optimal (or near optimal) strategies for "coloring" vertices (or nodes) on a graph within a specified time window with high probability, subject to certain constraints. In this context, the term coloring is distinguished from the classical, NP-hard graph coloring problem, in which the objective is to color the nodes in such a way that no two adjacent nodes share the same color. The problem considered here places no such restrictions on the coloring and views nodes simply as either colored or uncolored. The problem also shares similarities with the classical traveling salesman problem (TSP) in which a salesman is required to complete a tour of all the nodes, returning ultimately to his starting point. In the context of our problem, the salesman is not required to complete a tour, but rather must visit a certain subset of nodes within a given time window with high probability. The class of problems considered herein is further complicated by the fact that, over time, nodes can independently uncolor themselves with a certain probability. This behavior undoubtedly adds complexity to the problem and prolongs the time needed to color a subset of nodes of interest. Even if uncoloring is not permitted, the problems proposed herein present formidable modeling and computational challenges due to the curses of dimensionality, and the fact that the status of nodes evolves randomly over time. To overcome these challenges, we will develop novel stochastic optimization models, along with associated solution techniques, to explicitly account for information uncertainty and data that are revealed over time.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 14, 2017
- Source ID
- FA87501710090
Entities
People
- Jeffrey Kharoufeh
Organizations
- Defense Advanced Research Projects Agency
- Rome Laboratory
- University of Pittsburgh