Polynomial-Time Algorithms for Linear and Convex Optimization on Jump Systems
Please always quote using this URN: urn:nbn:de:0297-zib-9122
- The concept of jump system, introduced by Buchet and Cunningham (1995), is a set of integer points with a certain exchange property. In this paper, we discuss several linear and convex optimization problems on jump systems and show that these problems can be solved in polynomial time under the assumption that a membership oracle for a jump system is available. We firstly present a polynomial-time implementation of the greedy algorithm for the minimization of a linear function. We then consider the minimization of a separable-convex function on a jump system, and propose the first polynomial-time algorithm for this problem. The algorithm is based on the domain reduction approach developed in Shioura (1998). We finally consider the concept of M-convex functions on constant-parity jump systems which has been recently proposed by Murota (2006). It is shown that the minimization of an M-convex function can be solved in polynomial time by the domain reduction approach.
Author: | Akiyoshi Shioura, Ken'ichiro Tanaka |
---|---|
Document Type: | ZIB-Report |
Tag: | bisubmodular function; bisubmodular polyhedron; discrete convex function; jump system; polynomial-time algorithm |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization |
Date of first Publication: | 2006/04/11 |
Series (Serial Number): | ZIB-Report (06-19) |
ZIB-Reportnumber: | 06-19 |
Published in: | Appeared in: SIAM Journal on Discrete Mathematics, 21 (2) (2007) , 504-522 |