English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

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 = ∑ i ki. • A randomized algorithm that finds the row minima in an n × n totally monotone “vmatrix” 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.

(Near-)Linear-Time Randomized Algorithms for Row Minima in Monge Partial Matrices and Related Problems