(Near-)linear-time randomized algorithms for row minima in monge partial matrices and related problems

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

Abstract

We revisit classical problems about searching in totally monotone and Monge matrices, which have many applications in computational geometry and other areas. We present a number of new results, including the following: • A randomized algorithm that finds the row minima in an n×n Monge staircase matrix in O(n) expected time; this improves a longstanding O(nα(n)) bound by Klawe and Kleitman (1990) for totally monotone staircase matrices. • A randomized algorithm that reports the K smallest elements (in an arbitrary order) in an n × n Monge (complete or staircase) matrix in O(n + K) expected time; this improves and extends a previous O(n+K log n) algorithm by Kravets and Park [SODA'90]. • A randomized algorithm that reports the K smallest elements (in an arbitrary order) in an n × n totally monotone (complete) matrix in O(n+ K log n) expected time. • A randomized algorithm that reports the ki smallest elements in the i-th row, for every i, in an n × n totally monotone (complete) matrix in O((n + K) log n) expected time, where K = Pi ki. • A randomized algorithm that finds the row minima in an n × n totally monotone “v-matrix” in O(nα(n) log n log log n) expected time; this answers an open question by Klawe [SODA'90]. The log n factor can be removed in the Monge case.

Original languageEnglish (US)
Title of host publicationACM-SIAM Symposium on Discrete Algorithms, SODA 2021
EditorsDaniel Marx
PublisherAssociation for Computing Machinery
Pages1465-1482
Number of pages18
ISBN (Electronic)9781611976465
StatePublished - 2021
Event32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 - Alexandria, Virtual, United States
Duration: Jan 10 2021Jan 13 2021

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

Conference32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021
CountryUnited States
CityAlexandria, Virtual
Period1/10/211/13/21

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of '(Near-)linear-time randomized algorithms for row minima in monge partial matrices and related problems'. Together they form a unique fingerprint.

Cite this