Research in Graph Algorithms and Combinatorial Optimization.

Abstract

This project focused on designing fast algorithms for basic combinational optimization problems, including maximum flow, matching, multicommodity flow, and generalized flow. Many important applications are naturally stated as variants of these problems, and hence improved algorithms for these problems immediately lead to improved algorithms for a wide variety of applications. Our goal was to improve both sequential and parallel complexity. In many applications, solving a multicommodity or a generalized flow problem is only a first step in approximately solving an NP-complete problem; in the majority of such cases there is no need to have an exact solution of the problem. One of the focuses of the project was design of efficient approximation algorithms.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 06, 1995
Accession Number
ADA292630

Entities

People

  • Serge Plotkin

Organizations

  • Stanford University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Commodities
  • Computational Complexity
  • Computer Programming
  • Computer Science
  • Computers
  • Evolutionary Algorithms
  • Heuristic Methods
  • Linear Programming
  • Multiprocessors
  • Networks
  • Optimization
  • Polynomials
  • Scheduling (Production)
  • Separators
  • Simplex Method
  • Simulations

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research