SHERP

About strongly polynomial time algorithms for quadratic optimization over submodular constraints

Cited 0 time in webofscience Cited 0 time in scopus
Authors
Hochbaum, Dorit S.; Hong, Sung-Pil
Issue Date
1995
Publisher
Springer Verlag
Citation
Mathematical Programming 69 (1995) 269-309
Keywords
Quadratic programming; Submodular constraints; Kuhn-Tucker conditions; Lexicographically optimal flow; Parametric maximum flow
Abstract
We present new strongly polynomial algorithms for special cases of convex separable quadratic minimization over submodular constraints. The main results are: an O(NM log(N2/M)) algorithm for the problem Network defined on a network on M arcs and N nodes; an O(n log n) algorithm for the tree problem on n variables; an O(n log n) algorithm for the Nested problem,
and a linear time algorithm for the Generalized Upper Bound problem. These algorithms are the best known so rar for these problems. The status of the general problem and open questions are presented as weil.
ISSN
0025-5610 (print)1436-4646 (online)
Language
English
URI
http://hdl.handle.net/10371/5329
DOI
https://doi.org/10.1007/BF01585561
https://doi.org/10.1007/BF01585561
Files in This Item:
There are no files associated with this item.
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Industrial Engineering (산업공학과)Journal Papers (저널논문_산업공학과)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse