StringologyTimes

Data Structures and Algorithms: 2024/10/15-21

1: From Chinese Postman to Salesman and Beyond: Shortest Tour $\delta$-Covering All Points on All Edges
2: Exact Exploration
3: A Generalization of von Neumann’s Reduction from the Assignment Problem to Zero-Sum Games
4: The Lanczos algorithm for matrix functions: a handbook for scientists
5: Comparison Theorems for the Mixing Times of Systematic and Random Scan Dynamics
6: Experimental Design Using Interlacing Polynomials
7: Fully Dynamic $k$-Center Clustering Made Simple
8: Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring
9: The Quasi-probability Method and Applications for Trace Reconstruction
10: Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more
11: Differential Privacy on Trust Graphs
12: Distributionally Robust Newsvendor on a Metric
13: Ranking with Multiple Objectives
14: Orienteering (with Time Windows) on Restricted Graph Classes
15: Even Faster $(\Delta + 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains
16: Quasi-linear distance query reconstruction for graphs of bounded treelength
17: Reconfiguring homomorphisms to reflexive graphs via a simple reduction
18: The state hidden subgroup problem and an efficient algorithm for locating unentanglement
19: On the sample complexity of purity and inner product estimation
20: Prophet Upper Bounds for Online Matching and Auctions
21: Improved Kernelization and Fixed-parameter Algorithms for Bicluster Editing
22: Fast Construction of Partitioned Learned Bloom Filter with Theoretical Guarantees
23: Graph Exploration: The Impact of a Distance Constraint
24: Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
25: Adaptive and oblivious statistical adversaries are equivalent
26: On estimating the trace of quantum state powers
27: EFX Exists for Three Types of Agents
28: On generating $k$-factorable graphic sequences with connected (resp.no connected) $k$-factors
29: FORWARD: Feasibility Oriented Random-Walk Inspired Algorithm for Radial Reconfiguration in Distribution Networks
30: Fair Division in a Variable Setting
31: Packing-Inspired Algorithms for Periodic Scheduling Problems with Harmonic Periods
32: Nonadaptive Noisy Group Testing with Optimal Tests and Decoding
33: Bidirectional Dijkstra’s Algorithm is Instance-Optimal
34: Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
35: A subquadratic certification scheme for P5-free graphs
36: Slipstream: Ebb-and-Flow Consensus on a DAG with Fast Confirmation for UTXO Transactions
37: Efficient Matroid Intersection via a Batch-Update Auction Algorithm
38: Finite matrix multiplication algorithms from infinite groups
39: The Constrained Layer Tree Problem and Applications to Solar Farm Cabling
40: Learning-Augmented Algorithms for the Bahncard Problem
41: A Simplified Parameterized Algorithm for Directed Feedback Vertex Set
42: Improved Explicit Near-Optimal Codes in the High-Noise Regimes
43: Timetable Nodes for Public Transport Network
44: A Simpler Approach for Monotone Parametric Minimum Cut: Finding the Breakpoints in Order
45: Relating Left and Right Extensions of Maximal Repeats