Search NASA⌕ Search

DOE OSTI · 1055603

combinatorial optimization with demands (LDRD Final Report)

Abstract

This report summarizes the research conducted and results obtained under the Laboratory Directed Research and Development (LDRD) project, “Combinatorial Optimization with Demands ,” from October 2010 to September 2012. Complex resource allocation problems are ubiquitous in mission-driven applications. We investigated resource allocation problems endowed with additional parameters called demands, which allow for richer modeling. Demand endowed resource allocation problems are considerably harder to solve than their traditional counterparts, and we developed a conceptually simple but powerful new framework called iterative packing which allowed us to address the added complexity of demands. By leveraging iterative packing , we designed approximation algorithms to solve a large class of hard resource allocation problems with demands. Approximation algorithms are efficient heuristics which also offer a performance guarantee on the worst case deviation from the cost of an optimal solution. Our algorithms offer better performance guarantees over previously known algorithms; moreover, we are able to show that our algorithms provide performance guarantees that are likely close to best possible.

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

Parekh, Ojas, Carr, Robert D., Pritchard, David. 2012-09-01. combinatorial optimization with demands (LDRD Final Report). https://doi.org/10.2172/1055603

Cite the original work for its findings. Save a collection to share your selection of sources.