• Login
    View Item 
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Hardness and tractability for structured numerical problems

    Thumbnail
    View/Open
    ZHANG-DISSERTATION-2018.pdf (1012.Kb)
    Date
    2018-08-24
    Author
    Zhang, Peng
    Metadata
    Show full item record
    Abstract
    We study structured linear systems and structured linear programs (LPs) from both algorithm and complexity perspectives. These structured problems commonly arise in combinatorial optimization, machine learning, and operation research. Many of them can be solved significantly faster than general linear systems or linear programs by using additional structures. First, we consider linear systems in matrices which form a slightly larger class of graph Laplacians, referred to as Graph-Structured Block Matrices (GSBMs). In contrast to the existing nearly-linear time solvers for graph Laplacians (Spielman-Teng 2004) and its generalizations (Kyng et al 2016, Cohen et al 2017 and 2018), we prove hardness results for GSBMs: approximately solving linear systems in GSBMs is equally hard as approximately solving arbitrary linear systems. Building upon linear system based hardness assumptions, we then establish conditional lower bounds for packing and covering LPs, which are a special case of LPs with non-negative coefficients, constants and variables. On the algorithmic side, we obtain an asymptotically faster solver for linear systems in 3-D trusses with additional geometric structures. General truss matrices are GSBMs. Moreover, we design a parallel algorithm for approximately solving mixed packing and covering LPs, which improves the algorithm by Young (2001).
    URI
    http://hdl.handle.net/1853/60735
    Collections
    • College of Computing Theses and Dissertations [1191]
    • Georgia Tech Theses and Dissertations [23877]
    • School of Computer Science Theses and Dissertations [79]

    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