Publications
Detailed Information
About strongly polynomial time algorithms for quadratic optimization over submodular constraints
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Hochbaum, Dorit S. | - |
dc.contributor.author | Hong, Sung-Pil | - |
dc.date.accessioned | 2009-07-08T05:26:45Z | - |
dc.date.available | 2009-07-08T05:26:45Z | - |
dc.date.issued | 1995 | - |
dc.identifier.citation | Mathematical Programming 69 (1995) 269-309 | en |
dc.identifier.issn | 0025-5610 (print) | - |
dc.identifier.issn | 1436-4646 (online) | - |
dc.identifier.uri | https://hdl.handle.net/10371/5329 | - |
dc.description.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. | en |
dc.description.sponsorship | This research has been supported in part by ONR grant N00014-91-J-1241. | en |
dc.language.iso | en | - |
dc.publisher | Springer Verlag | en |
dc.subject | Quadratic programming | en |
dc.subject | Submodular constraints | en |
dc.subject | Kuhn-Tucker conditions | en |
dc.subject | Lexicographically optimal flow | en |
dc.subject | Parametric maximum flow | en |
dc.title | About strongly polynomial time algorithms for quadratic optimization over submodular constraints | en |
dc.type | Article | en |
dc.contributor.AlternativeAuthor | 홍성필 | - |
dc.identifier.doi | 10.1007/BF01585561 | - |
dc.identifier.doi | 10.1007/BF01585561 | - |
dc.citation.journaltitle | Mathematical Programming | - |
- Appears in Collections:
- Files in This Item:
- There are no files associated with this item.
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.