StringologyTimes

Data Structures and Algorithms: 2021/11/15-21

1: A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs
2: Fast Doubly-Adaptive MCMC to Estimate the Gibbs Partition Function with Weak Mixing Time Bounds
3: Combinatorial Algorithms for Rooted Prize-Collecting Walks and Applications to Orienteering and Minimum-Latency Problems
4: A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection
5: On a Partition LP Relaxation for Min-Cost 2-Node Connected Spanning Subgraphs
6: Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications
7: Improved Decoding of Expander Codes
8: Enumerating Minimal Separators in Ranked Order
9: Conditional Linear Regression for Heterogeneous Covariances
10: Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel
11: Distribution Compression in Near-linear Time
12: Embeddings of Planar Quasimetrics into Directed \ell_1$ and Polylogarithmic Approximation for Directed Sparsest-Cut
13: Global Convergence of Hessenberg Shifted QR I: Exact Arithmetic
14: A Comparison of O(1) and Cyrus-Beck Line Clipping Algorithms in E2 and E3
15: Margin-Independent Online Multiclass Learning via Convex Geometry
16: Monotone Inclusions, Acceleration and Closed-Loop Control
17: Improved Approximations for CVRP with Unsplittable Demands
18: Improved Bounds for Scheduling Flows under Endpoint Capacity Constraints
19: A Simple Algorithm for Computing the Zone of a Line in an Arrangement of Lines
20: Hyperbolicity Computation through Dominating Sets
21: On the Randomized Metric Distortion Conjecture
22: Optimal Oblivious Reconfigurable Networks
23: Improved Pan-Private Stream Density Estimation
24: The Stochastic Boolean Function Evaluation Problem for Symmetric Boolean Functions
25: Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games
26: Minimum Cuts in Directed Graphs via Partial Sparsification
27: An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions
28: Roman Domination in Convex Bipartite Graphs
29: Bipartite Temporal Graphs and the Parameterized Complexity of Multistage 2-Coloring
30: Stream Sampling with Immediate Decision
31: A Hitting Set Relaxation for $k$-Server and an Extension to Time-Windows
32: Matroid-Based TSP Rounding for Half-Integral Solutions
33: Optimal Decremental Connectivity in Non-Sparse Graphs
34: Monitoring Over the Long Term: Intermittent Deployment and Sensing Strategies for Multi-Robot Teams
35: Submodular Optimization for Coupled Task Allocation and Intermittent Deployment Problems
36: On Clustering with Discounts
37: On the Recoverable Traveling Salesman Problem
38: Improved Sample Complexity Bounds for Branch-and-Cut
39: Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
40: Parallel Algorithms for Masked Sparse Matrix-Matrix Products
41: Embeddings and labeling schemes for A(star)
42: Uniform Brackets, Containers, and Combinatorial Macbeath Regions
43: An Improved Analysis of Greedy for Online Steiner Forest
44: An Index for Single Source All Destinations Distance Queries in Temporal Graphs
45: Randomized Algorithms for Monotone Submodular Function Maximization on the Integer Lattice
46: Streaming Deletion Problems Parameterized by Vertex Cover
47: Sparsified Block Elimination for Directed Laplacians
48: On the power of adaptivity in statistical adversaries
49: Faster Sparse Minimum Cost Flow by Electrical Flow Localization
50: Approximation Algorithms for LCS and LIS with Truly Improved Running Times
51: Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings
52: Oblivious Online Contention Resolution Schemes
53: Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds
54: New Binary-Addition Tree Algorithm for the All-Multiterminal Binary-State Network Reliability Problem
55: New Clocks, Optimal Line Formation and Self-Replication Population Protocols