StringologyTimes

Data Structures and Algorithms: 2023/8/08-14

1: Matrix Completion in Almost-Verification Time
2: Dependent Cluster Mapping (DCMAP): Optimal clustering of directed acyclic graphs for statistical inference
3: 0-1 Knapsack in Nearly Quadratic Time
4: On the Node-Averaged Complexity of Locally Checkable Problems on Trees
5: Tolerant Testing of High-Dimensional Samplers with Subcube Conditioning
6: Linear Time Construction of Cover Suffix Tree and Applications
7: Defending Hash Tables from Subterfuge with Depth Charge
8: Chrisimos: A useful Proof-of-Work for finding Minimal Dominating Set of a graph
9: Communication-Efficient Search under Fully Homomorphic Encryption for Federated Machine Learning
10: Generating News-Centric Crossword Puzzles As A Constraint Satisfaction and Optimization Problem
11: Deterministic $k$-Vertex Connectivity in $k^2$ Max-flows
12: Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition
13: Improved Approximation Algorithms for the Joint Replenishment Problem with Outliers, and with Fairness Constraints
14: Comparative analysis of mathematical formulations for the two-dimensional guillotine cutting problem
15: Controlling Tail Risk in Online Ski-Rental
16: Mean-Biased Processes for Balanced Allocations
17: MNL-Prophet: Sequential Assortment Selection under Uncertainty
18: Algorithms for Encoding and Decoding 3D Hilbert Orderings
19: On the equivalence of Occam algorithms
20: Simple Analysis of Priority Sampling
21: Competitive Analysis of Online Facility Assignment for General Layout of Servers on a Line
22: Lossy Kernelization for (Implicit) Hitting Set Problems
23: Breaking a Barrier in Constructing Compact Indexes for Parameterized Pattern Matching
24: Finding Long Directed Cycles Is Hard Even When DFVS Is Small Or Girth Is Large
25: Simpler constant factor approximation algorithms for weighted flow time – now for any $p$-norm
26: A Better-Than-1.6-Approximation for Prize-Collecting TSP
27: Parameterized Matroid-Constrained Maximum Coverage
28: An Approximation Algorithm for Ancestral Maximum-Likelihood and Phylogeography Inference Problems under Time Reversible Markov Evolutionary Models
29: Optimal FIFO grouping in public transit networks
30: Exploration of graphs with excluded minors
31: $(1-\epsilon)$-Approximation of Knapsack in Nearly Quadratic Time