Show simple item record

dc.contributor.authorMurota, Kazuoen_US
dc.date.accessioned2012-04-12T18:44:30Z
dc.date.available2012-04-12T18:44:30Z
dc.date.issued2012-03-19
dc.identifier.urihttp://hdl.handle.net/1853/43257
dc.descriptionPresented at the Georgia Tech Algorithms & Randomness Center workshop: Modern Aspects of Submodularity, March 19-22, 2012.en_US
dc.descriptionRuntime: 48:19 minutes.en_US
dc.description.abstractDiscrete convex analysis is a theory that aims at a discrete analogue of convex analysis for nonlinear discrete optimization. Technically it is a nonlinear generalization of matroid/submodular function theory; matroids are generalized to M-convex functions and submodular set functions to L-convex function.This talk consists of two parts: In the first part fundamental concepts and theorems in discrete convex analysis are explained with reference to familiar combinatorial optimization problems like minimum spanning tree, shortest path, and matching. In view of the recent development in submodular function maximization, minimization and maximization algorithms in discrete convex analysis are explained in the second part of the talk. In particular, M-natural concave functions form a subclass of submodular functions that can be maximized in polynomial time.en_US
dc.format.extent48:19 minutes
dc.language.isoen_USen_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectDiscrete convexityen_US
dc.subjectDiscrete convex functionsen_US
dc.titleIntroduction to Discrete Convex Analysisen_US
dc.typeLectureen_US
dc.typeVideoen_US
dc.contributor.corporatenameGeorgia Institute of Technology. School of Computer Scienceen_US
dc.contributor.corporatenameUniversity of Tokyoen_US


Files in this item

This item appears in the following Collection(s)

Show simple item record