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

    On the Complexity of Clustering Problems

    Thumbnail
    View/Open
    louis.mp4 (426.5Mb)
    louis_videostream.html (1.013Kb)
    transcription.txt (44.67Kb)
    thumbnail.jpg (159.9Kb)
    Date
    2018-09-10
    Author
    Louis, Anand
    Metadata
    Show full item record
    Abstract
    Euclidean k-means clustering, a problem having numerous applications, is NP-hard in the worst case but often solved efficiently in practice using simple heuristics. A quest for understanding the properties of real-world data sets that allow efficient clustering has lead to the notion of the perturbation resilience. In the first part of the talk, I'll describe an algorithm to recover the optimal k-means clustering in perturbation resilient instances. In some cases, clustering with the k-means objective may result in a few clusters of very large cost and many clusters of small cost. This can be undesirable when we have a budget constraint on the cost of each cluster. Motivated by this, we study the "min-max k-means" clustering objective. In the second part of the talk, I'll show approximation algorithms for the min-max k-means problem. Based on joint works with Amit Deshpande and Apoorv Vikram Singh.
    URI
    http://hdl.handle.net/1853/60429
    Collections
    • ARC Talks and Events [88]

    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