TY - GEN

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

AU - Chan, Timothy M.

N1 - Funding Information:
This research has been supported in part by NSF Grant CCF-1814026.
Publisher Copyright:
Copyright © 2021 by SIAM

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85104224043&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85104224043&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85104224043

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1465

EP - 1482

BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

A2 - Marx, Daniel

PB - Association for Computing Machinery

T2 - 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

Y2 - 10 January 2021 through 13 January 2021

ER -