Distributed and Streaming Linear Programming in Low Dimensions
Formal Metadata
| Title | Distributed and Streaming Linear Programming in Low Dimensions |
|
| Title of Series | |
| Number of Parts | 155 |
| Author | |
| License | CC Attribution 3.0 Germany: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. |
| Identifiers | |
| Publisher | |
| Release Date | |
| Language | |
Content Metadata
| Subject Area | |
| Genre | |
| 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. |
|