Back to search

Georgia Institute of Technology

Hardness and tractability for structured numerical problems

Abstract

dc:description.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).

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Computer Science
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zhang, Peng
Advisor dc:contributor.advisor
  • Peng, Richard
Committee members dc:contributor.committeemember
  • Chow, Edmond
  • Drineas, Petros
  • Mihail, Milena
  • Vempala, Santosh

Subjects

dc:subject × 6

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/60735

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Zhang, Peng. Hardness and tractability for structured numerical problems. Doctoral thesis, Georgia Institute of Technology, 2018. http://hdl.handle.net/1853/60735