Distributed and streaming linear programming in low dimensions

Sepehr Assadi, Nikolai Karpov, Qin Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

We study linear programming and general LP-type problems in several big data (streaming and distributed) models. We mainly focus on low dimensional problems in which the number of constraints is much larger than the number of variables. Low dimensional LP-type problems appear frequently in various machine learning tasks such as robust regression, support vector machines, and core vector machines. As supporting large-scale machine learning queries in database systems has become an important direction for database research, obtaining efficient algorithms for low dimensional LP-type problems on massive datasets is of great value. In this paper we give both upper and lower bounds for LP-type problems in distributed and streaming models. Our bounds are almost tight when the dimensionality of the problem is a fixed constant.

Original languageEnglish (US)
Title of host publicationPODS 2019 - Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
PublisherAssociation for Computing Machinery
Pages236-253
Number of pages18
ISBN (Electronic)9781450362276
DOIs
StatePublished - Jun 13 2019
Externally publishedYes
Event38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. PODS 2019, held in conjunction with the 2019 ACM SIGMOD International Conference on Management of Data, SIGMOD 2019 - Amsterdam, Netherlands
Duration: Jul 1 2019Jul 3 2019

Publication series

NameProceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

Conference

Conference38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. PODS 2019, held in conjunction with the 2019 ACM SIGMOD International Conference on Management of Data, SIGMOD 2019
Country/TerritoryNetherlands
CityAmsterdam
Period7/1/197/3/19

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture

Keywords

  • Distributed algorithms
  • Linear programming
  • Streaming algorithms

Fingerprint

Dive into the research topics of 'Distributed and streaming linear programming in low dimensions'. Together they form a unique fingerprint.

Cite this