TY - GEN A1 - Shioura, Akiyoshi T1 - Note on L#-convex Function Minimization Algorithms: Comparison of Murota's and Kolmogorov's Algorithms N2 - The concept of L##-convexity is introduced by Fujishige--Murota (2000) as a discrete convexity for functions defined over the integer lattice. The main aim of this note is to understand the difference of the two algorithms for L##-convex function minimization: Murota's steepest descent algorithm (2003) and Kolmogorov's primal algorithm (2005). T3 - ZIB-Report - 06-03 Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8979 ER - TY - GEN A1 - Shioura, Akiyoshi A1 - Tanaka, Ken'ichiro T1 - Polynomial-Time Algorithms for Linear and Convex Optimization on Jump Systems N2 - 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. T3 - ZIB-Report - 06-19 KW - jump system KW - discrete convex function KW - bisubmodular function KW - bisubmodular polyhedron KW - polynomial-time algorithm Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9122 ER -