THIS IS A CONTINUATION OF N00014-12-1-1001 Provably Near-Optimal Distributed Online Network Optimization
Abstract
Statement of Work:The main goal of this project is to develop a comprehensive theory of distributed online approximation algorithms for hard network optimization problems.Objective:The main goal of this project is to develop a comprehensive theory of distributed online approximation algorithms for hard network optimization problems. Our framework encompasses three dimensions - locality, uncertainty, and temporality, with two complementary aspects to each dimension. This gives rise to diff erent categories of problems.The hardest problems are those that require decentralized solutions when faced with an adversary that adaptively reveals the input over time.Approach:In this research, the PI develop a variety of models for studying the fundamental tasks of establishing and maintaining connectivity and control in complex networked systems, which capture three important features. 1. Limited communication between agents (necessitating distributed algorithms),2. Online revelation of information over time (including robust and competitive frameworks), with the input selection ranging from the worst-case adversarial to stochastic choice (leading respectively to online and stochastic optimization algorithms), and3. Permit the development of rigorous approximation algorithms with a polynomial running time that provide provably good solutions with worst-case performance guarantees.Overall Merit and ONR Mission/Relevance:The proposed research is innovative in that it proposes the development of rigorous algorithmic-analysis techniques for decentralized online optimization that provides performance predictions through sound estimates of the closeness a decentralized online solution to a centralized, global offline optimal solution; such performance guarantees contribute tremendously to trust in these systems, which is critical for their deployment. The Navy is moving towards deploying large, complex systems that are beyond centralized control. A canonical example of such a system is a fleet of unmanned vehicles with limited communications operating in a dynamic environment. Important characteristics of these systems are that they are decentralized (i.e., system components cantake independent actions), and the environment in which the system operates is not necessarily known a priori, and is revealed over time. The objective of this topic is to develop scientific principles and algorithms for solvingdecentralized, online optimization problems.Progress:In modern data centers and cloud computing systems, jobs often require resources distributed across nodes providing a wide variety of services. Motivated by this, we study the Coupled Placement problem, in which we place jobs into computation and storage nodes with capacity constraints, so as to optimize some costs or profits associated with the placement. The coupled placement problem is a natural generalization of the widely-studied generalized assignment problem (GAP), which concerns the placement of jobs into single nodes providing one kind of service. We also study a further generalization, the k-Sided Placement problem, in which we place jobs into k-tuples of nodes, each node in a tuple offering one of k services. For both the coupled and k-sided placement problems, we consider minimization and maximization versions. In the minimization versions (MinCP and MinkSP), the goal is to achieve minimum placement cost, while incurring a minimum blowup in the capacity of the individual nodes. Our first main result is an algorithm for MinkSP that achieves optimal cost while increasing capacities by at most a factor of k + 1, also yielding the first constant-factor approximation for MinCP. In the maximization versions (MaxCP and MaxkSP), the goal is to maximize the total weight of the jobs that are placed under hard capacity constraints. MaxkSP can be expressed as a k-column sparse integer program, and can be approximated to within a factor of O(k) factor using randomized rounding of a linear progra
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 23, 2016
- Source ID
- N000141612788
Entities
People
- Ramamoorthi Ravi
Organizations
- Massachusetts Institute of Technology
- Office of Naval Research
- United States Navy