Linear-Time Separation Algorithms for the Three-Index Assignment Polytope

Abstract

Balas and Saltzman identified several classes of facet inducing inequalities for the three-index assignment polytope, and gave O(n to the 4th power) separation algorithms for two of them. We give O(n cubed) separation algorithms for these two classes of facets, and also for a third class. Since the three-index assignment problem has n cubed variables, these algorithms are linear-time and their complexity is best possible. (kr)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1990
Accession Number
ADA228854

Entities

People

  • Egon Balas
  • Liqun Qi

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Coefficients
  • Contracts
  • Inequalities
  • Military Research
  • Schools
  • Students
  • Three Dimensional
  • Two Dimensional
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.