About strongly polynomial time algorithms for quadratic optimization over submodular constraints

About strongly polynomial time algorithms for quadratic optimization over submodular constraints

0.00 Avg rating0 Votes
Article ID: iaor19971133
Country: Netherlands
Volume: 69
Issue: 2
Start Page Number: 269
End Page Number: 309
Publication Date: Aug 1995
Journal: Mathematical Programming (Series A)
Authors: ,
Abstract:

The authors present new strongly polynomial algorithms for special cases of convex separable quadratic minimization over submodular constraints. The main results are: an O(NMlog(N2/M)) algorithm for the problem Network defined on a network on M arcs and N nodes; an O(nlogn) algorithm for the tree problem on n variables; an O(nlogn) algorithm for the Nested problem, and a linar time algorithm for the Generalized Upper Bound problem. These algorithms are the best known so far for these problems. The status of the general problem and open questions are presented as well.

Reviews

Required fields are marked *. Your email address will not be published.