Using Online Algorithms to Solve NP-Hard Problems More Efficiently in Practice

Abstract

This thesis develops online algorithms that can be used to solve a wide variety of NP-hard problems more efficiently in practice. The common approach taken by all our online algorithms is to improve the performance of one or more existing algorithms for a specific NP-hard problem by adapting the algorithms to the sequence of problem instance(s) they are run on. We begin by presenting an algorithm for solving a specific class of online resource allocation problems. Our online algorithm can be applied in environments where abstract jobs arrive one at a time, and one can complete the jobs by investing time in a number of abstract activities. Provided the jobs and activities satisfy certain technical conditions, our online algorithm is guaranteed to perform almost as well as any fixed schedule for investing time in the various activities, according to two natural measures of performance: 1. the average time required to complete each job, and 2. the number of jobs completed within time T, for some fixed deadline T>0. In particular, our online algorithm's guarantees apply if the job can be written as a monotone, submodular function of a set of pairs of the form (upsilon, tau), where tau is the time invested in activity upsilon. Under the 1st objective, the offline version of this problem generalizes MIN-SUM SET COVER and the related PIPELINED SET COVER problem. Under the 2nd objective, the offline version of this problem generalizes the problem of maximizing a monotone, submodular set function subject to a knapsack constraint. Our online algorithm has potential applications in a number of areas, including the design of algorithm portfolios, database query processing, and sensor placement. We apply this online algorithm to the following problem. We are given k algorithms, and are fed, one at a time, a sequence of problem instances to solve. We may solve each instance using any of the algorithms, we may interleave the execution of the algorithms, and we may restart them.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 2007
Accession Number
ADA476807

Entities

People

  • Matthew T. Streeter

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Energy and Power Technologies
  • Human Systems
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Computational Complexity
  • Computational Science
  • Computer Science
  • Distribution Functions
  • Dynamic Programming
  • Information Processing
  • Information Science
  • Logistics Planning
  • Machine Learning
  • Mathematical Programming
  • Mathematics
  • Operations Research
  • Optimization
  • Probability Distributions
  • Random Variables

Fields of Study

  • Computer science

Readers

  • Neural Network Machine Learning.
  • Operations Research
  • Parallel and Distributed Computing.