StringologyTimes

Data Structures and Algorithms: 2020/8/01-07

1: On the Two-Dimensional Knapsack Problem for Convex Polygons
2: Contiguous Graph Partitioning For Optimal Total Or Bottleneck Communication
3: On the Computational Complexity of Linear Discrepancy
4: Fast Classical and Quantum Algorithms for Online $k$-server Problem on Trees
5: The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures
6: Bringing UMAP Closer to the Speed of Light with GPU Acceleration
7: Data Oblivious Algorithms for Multicores
8: Relational Algorithms for k-means Clustering
9: Concentration-Bound Analysis for Probabilistic Programs and Probabilistic Recurrence Relations
10: Minimum $2$-vertex strongly biconnected spanning directed subgraph problem
11: Approximating pathwidth for graphs of small treewidth
12: Truly asymptotic lower bounds for online vector bin packing
13: List $k$-Colouring $P_t$-Free Graphs: a Mim-width Perspective
14: The Splay-List: A Distribution-Adaptive Concurrent Skip-List
15: Erratum: Fast and Simple Horizontal Coordinate Assignment
16: An improved Bayesian TRIE based model for SMS text normalization
17: Top-k Connected Overlapping Densest Subgraphs in Dual Networks
18: Automorphism groups of maps in linear time
19: Identifying the $k$ Best Targets for an Advertisement Campaign via Online Social Networks
20: Fast and Near-Optimal Diagonal Preconditioning
21: Bucket Oblivious Sort: An Extremely Simple Oblivious Sort
22: A Data-Structure for Approximate Longest Common Subsequence of A Set of Strings
23: An Algorithm Framework for the Exact Solution and Improved Approximation of the Maximum Weighted Independent Set Problem
24: Robust Minimum Cost Flow Problem Under Consistent Flow Constraints
25: A Note on a Recent Algorithm for Minimum Cut
26: Reducing Isotropy and Volume to KLS: An $O(n^3\psi^2)$ Volume Algorithm
27: GeoTree: a data structure for constant time geospatial search enabling a real-time mix-adjusted median property price index
28: A Time Leap Challenge for SAT Solving
29: Computational Barriers to Estimation from Low-Degree Polynomials
30: Competitive Allocation of a Mixed Manna
31: Fine-Grained Complexity of Regular Expression Pattern Matching and Membership
32: Singularly Optimal Randomized Leader Election
33: Polynomial-time algorithms for Multimarginal Optimal Transport problems with structure
34: Hierarchical Clusterings of Unweighted Graphs
35: Low-Congestion Shortcuts for Graphs Excluding Dense Minors
36: A $2^{O(k)}n$ algorithm for $k$-cycle in minor-closed graph families