StringologyTimes

Data Structures and Algorithms: 2024/4/22-28

1: Stochastic Multi-round Submodular Optimization with Budget
2: Sublinear Time Low-Rank Approximation of Toeplitz Matrices
3: Faster Algorithms for Dual-Failure Replacement Paths
4: Engineering Edge Orientation Algorithms
5: Decline and Fall of the ICALP 2008 Modular Decomposition algorithm
6: A Tight Subexponential-time Algorithm for Two-Page Book Embedding
7: Individual Rationality in Topological Distance Games is Surprisingly Hard
8: Semirandom Planted Clique and the Restricted Isometry Property
9: Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines
10: Computing the LCP Array of a Labeled Graph
11: An inexact augmented Lagrangian algorithm for unsymmetric saddle-point systems
12: On the sizes of BDDs and ZDDs representing matroids
13: It’s Hard to HAC with Average Linkage!
14: $\alpha_i$-Metric Graphs: Hyperbolicity
15: On the Number of Steps of CyclePopping in Weakly Inconsistent U(1)-Connection Graphs
16: Parameterized Maximum Node-Disjoint Paths
17: Near-Universally-Optimal Differentially Private Minimum Spanning Trees
18: Renting Servers for Multi-Parameter Jobs in the Cloud
19: Minimum Consistent Subset in Trees and Interval Graphs
20: Online Disjoint Set Covers: Randomization is not Necessary
21: A Note on Approximating Weighted Nash Social Welfare with Additive Valuations
22: Detecting Disjoint Shortest Paths in Linear Time and More
23: Hardness and Tight Approximations of Demand Strip Packing
24: Seed Selection in the Heterogeneous Moran Process
25: Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better
26: Unweighted Layered Graph Traversal
27: Fault-Tolerant Bounded Flow Preservers
28: Dynamic PageRank: Algorithms and Lower Bounds
29: Parallel and (Nearly) Work-Efficient Dynamic Programming
30: On Approximating the Dynamic and Discrete Network Flow Problem
31: More Asymmetry Yields Faster Matrix Multiplication
32: Cost-Driven Data Replication with Predictions
33: Scalable Distributed String Sorting
34: Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
35: Layered List Labeling
36: Computing Hamiltonian Paths with Partial Order Restrictions
37: Multilayer Correlation Clustering
38: Kernelization Dichotomies for Hitting Subgraphs under Structural Parameterizations
39: On the Streaming Complexity of Expander Decomposition
40: Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy
41: Constrained Level Planarity is FPT with Respect to the Vertex Cover Number
42: Approximation Algorithms for Hop Constrained and Buy-at-Bulk Network Design via Hop Constrained Oblivious Routing
43: Parameterized Complexity of Efficient Sortation
44: Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
45: Solving the Graph Burning Problem for Large Graphs
46: PASGAL: Parallel And Scalable Graph Algorithm Library
47: Distributed computation of temporal twins in periodic undirected time-varying graphs
48: Set Selection with Uncertain Weights: Non-Adaptive Queries and Thresholds
49: Exact and Approximate High-Multiplicity Scheduling on Identical Machines
50: Internal Pattern Matching in Small Space and Applications
51: Understanding the Cluster LP for Correlation Clustering
52: Root-to-Leaf Scheduling in Write-Optimized Trees
53: Half-space separation in monophonic convexity
54: Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
55: Recent Increments in Incremental View Maintenance
56: Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimes
57: Generalizing Roberts’ characterization of unit interval graphs
58: Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach
59: Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
60: Parameterized Linear Time Transitive Closure
61: Varia\c{c}~oes do Problema de Dist\^ancia de Rearranjos
62: Testing $C_k$-freeness in bounded-arboricity graphs
63: Revisiting Majumdar-Ghosh spin chain model and Max-cut problem using variational quantum algorithms