• Login
    View Item 
    •   SMARTech Home
    • College of Computing (CoC)
    • Algorithms and Randomness Center (ARC)
    • Modern Aspects of Submodularity
    • View Item
    •   SMARTech Home
    • College of Computing (CoC)
    • Algorithms and Randomness Center (ARC)
    • Modern Aspects of Submodularity
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Introduction to Discrete Convex Analysis

    Thumbnail
    View/Open
    04murota.mp4 (135.6Mb)
    04murota_videostream.html (985bytes)
    Date
    2012-03-19
    Author
    Murota, Kazuo
    Metadata
    Show full item record
    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.
    URI
    http://hdl.handle.net/1853/43257
    Collections
    • Modern Aspects of Submodularity [27]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology