Newton's Method for Fractional Combinatorial Optimization,

Abstract

We consider Newton's method for the linear fractional combinatorial optimization. First we show a strongly polynomial bound on the number of iterations for the general case. Then we consider the transshipment problem when the maximum arc cost is being minimized. This problem can be reduced to the maximum mean-weight cut problem, which is a special case of the linear fractional combinatorial optimization. We prove that Newton's method runs in O(m) iterations for the maximum mean weight cut problem. One iteration is dominated by the maximum flow computation, so the overall running time is O(m2n). The previous fastest algorithm is based on Meggido's parametric search method and runs in O(n3m) time.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1992
Accession Number
ADA323687

Entities

People

  • Thomas Radzik

Organizations

  • Stanford University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Commerce
  • Commodities
  • Computations
  • Computer Science
  • Computers
  • Flow Network
  • Government (Foreign)
  • Governments
  • Graphs
  • Inequalities
  • Iterations
  • Numbers
  • Operations Research
  • Optimization
  • Standards

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research