6 papers
Exact and Asymptotic Analysis of Greedy Online Facility Assignment on Cycle Metrics
Md. Tanzeem Rahat, Md. Rawha Siddiqi Riad, Md. Manzurul Hasan
We identify the free-facility gaps of greedy online assignment on a cycle with the discrete additive coalescent and use this connection to determine the exact expected assignment c…
Competitive Analysis of Online Facility Assignment Algorithms on Discrete Grid Graphs: Performance Bounds and Remediation Strategies
Lamya Alif, Raian Tasnim Saoda, Sumaiya Afrin +3
We study the \emph{Online Facility Assignment} (OFA) problem on a discrete grid graph under the standard model of Ahmed, Rahman, and Kobourov: a fixed set of facilities…
Expected Cost of Greedy Online Facility Assignment on Regular Polygons (v3)
Md. Rawha Siddiqi Riad, Md. Tanzeem Rahat, Md. Manzurul Hasan
We study a greedy online facility assignment process on a regular -gon, where unit-capacity facilities occupy the vertices and customers arrive sequentially at uniformly random…
Permutation Matching Under Parikh Budgets: Linear-Time Detection, Packing, and Disjoint Selection
MD Nazmul Alam Shanto, Md. Tanzeem Rahat, Md. Manzurul Hasan
We study permutation (jumbled/Abelian) pattern matching over a general alphabet . Given a pattern P of length m and a text T of length n, the classical task is to decide whether…
The Longest Common Bitonic Subsequence: Match-Sensitive Algorithms and Conditional Hardness
Md. Tanzeem Rahat, Md. Manzurul Hasan, Sadia Sharmin
The longest common bitonic subsequence problem asks for a longest common subsequence of two ordered sequences whose values strictly increase and then strictly decrease; either phas…
A Space-Efficient Algorithm for Longest Common Almost Increasing Subsequence of Two Sequences
Md Tanzeem Rahat, Md. Manzurul Hasan, Debajyoti Mondal
Let and be two number sequences of length and , respectively, where . Given a positive number , a common almost increasing sequence is a c…