Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

New algorithms for distributed submodular maximization.

Tools
- Tools
+ Tools

Barbosa, Rafael da Ponte (2017) New algorithms for distributed submodular maximization. PhD thesis, University of Warwick.

[img]
Preview
PDF
WRAP_Theses_Barbosa_2017.pdf - Submitted Version - Requires a PDF viewer.

Download (1212Kb) | Preview
Official URL: http://webcat.warwick.ac.uk/record=b3110710~S15

Request Changes to record.

Abstract

A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as submodular maximization problems. In many of these applications, the amount of data collected is quite large and it is growing at a very fast pace. For example, the wide deployment of sensors has led to the collection of large amounts of measurements of the physical world. Similarly, medical data and human activity data are being captured and stored at an ever increasing rate and level of detail. This data is often high-dimensional and complex, and it needs to be stored and/or processed in a distributed fashion. Following a recent line of work, we present here parallel algorithms for these problems, and analyze the compromise between quality of the solutions obtained and the amount of computational overhead.

On the one hand, we develop strategies for bringing existing algorithms for constrained submodular maximization in the sequential setting to the distributed setting. The algorithms presented achieve constant approximation factors in two rounds, and near optimal approximation ratios in only a constant number of rounds. Our techniques also give a fast sequential algorithm for non-monotone maximization subject to a matroid constraint.

On the other hand, for unconstrained submodular maximization, we devise parallel algorithms combining naive random sampling and Double Greedy steps, and investigate how much the quality of the solutions degrades with less coordination.

Item Type: Thesis or Dissertation (PhD)
Subjects: Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Library of Congress Subject Headings (LCSH): Parallel algorithms, Distributed algorithms, Machine learning
Official Date: February 2017
Dates:
DateEvent
February 2017UNSPECIFIED
Institution: University of Warwick
Theses Department: Department of Computer Science
Thesis Type: PhD
Publication Status: Unpublished
Supervisor(s)/Advisor: Ene, Alina
Extent: vi, 88 leaves
Language: eng

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us