Presentation	2007-04-26 On Convex Optimization over Base Polytopes Kiyohito NAGANO,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	This note considers convex optimization problems over base polytopes of polymatroids. We show that the decomposition algorithm for the separable convex function minimization problems helps us give simple sufficient conditions for the rationality of optimal solutions and that it leads us to some interesting properties, including the equivalence of the lexicographically optimal base problem, introduced by Fujishige, and the submodular utility allocation market problem, introduced by Jain and Vazirani. In addition, we develop an efficient implementation of the decomposition algorithm via parametric submodular function minimization algorithms. Moreover, we show that, in some remarkable cases, non-separable convex optimization problems over base polytopes can be solved in strongly polynomial time.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	submodular functions / convex optimization
Paper #	COMP2007-4
Date of Issue

Conference Information
Committee	COMP
Conference Date	2007/4/19(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	ENG
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	On Convex Optimization over Base Polytopes
Sub Title (in English)
Keyword(1)	submodular functions
Keyword(2)	convex optimization
1st Author's Name	Kiyohito NAGANO
1st Author's Affiliation	University of Tokyo:Kyoto University()
Date	2007-04-26
Paper #	COMP2007-4
Volume (vol)	vol.107
Number (no)	24
Page	pp.pp.-
#Pages	7
Date of Issue