Introduction to Discrete Convex Analysis

Show simple item record Murota, Kazuo en_US 2012-04-12T18:44:30Z 2012-04-12T18:44:30Z 2012-03-19
dc.description Presented at the Georgia Tech Algorithms & Randomness Center workshop: Modern Aspects of Submodularity, March 19-22, 2012. en_US
dc.description Runtime: 48:19 minutes. en_US
dc.description.abstract Discrete 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.extent 48:19 minutes
dc.language.iso en_US en_US
dc.publisher Georgia Institute of Technology en_US
dc.subject Discrete convexity en_US
dc.subject Discrete convex functions en_US
dc.title Introduction to Discrete Convex Analysis en_US
dc.type Lecture en_US
dc.type Video en_US
dc.contributor.corporatename Georgia Institute of Technology. School of Computer Science en_US
dc.contributor.corporatename University of Tokyo en_US

Files in this item

Files Size Format View Description
04murota.mp4 135.6Mb MPEG-4 video View/ Open Download Video
04murota_streaming.html 926bytes HTML View/ Open Streaming Video

This item appears in the following Collection(s)

Show simple item record