Subcubic Min-Plus Product of Structured Matrices

The All-Pairs Shortest Paths (APSP) problem is one of the most basic problems in computer science. The fastest known algorithms for APSP in 𝑛-node graphs run in 𝑛³⁻⁰⁽¹⁾ time, and it is a big open problem whether a truly subcubic, 𝑂(𝑛³⁻ superscript 𝜀) for 𝜀 > 0 time algorithm exists for APSP. The Min-Plus product of two 𝑛 × 𝑛 matrices is known to be equivalent to APSP, where the optimal running times of the two problems differ by at most a constant factor. A natural way to approach understanding the complexity of APSP is thus understanding what structure (if any) is needed to solve Min-Plus Product in truly subcubic time. The goal of this thesis is to get truly subcubic algorithms for Min-Plus products for less structured inputs than what was previously known, and to apply them to versions of APSP and other problems. This thesis gives sub-cubic algorithms for two interesting cases of structured Min-Plus Products: Min-Plus product between matrices with a constant additive approximate rank and Min-Plus product between monotone matrices, whose definitions are deferred to the main text. These faster algorithms have a wide range of applications, including Geometric APSP, Maximum Subarray, Range Mode and Single Source Replacement Paths.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2021

Author dc:creator

• Xu, Yinzhan

Advisor dc:contributor.advisor

• Vassilevska Williams, Virginia

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/139234

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/139234