StringologyTimes

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

1: A computational study of Gomory-Hu construction tree algorithms
2: Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
3: Online Two-Dimensional Vector Packing with Advice
4: Social Distancing Network Creation
5: Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond
6: Some Optimization Solutions for Relief Distribution
7: A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems
8: A Linear Time Algorithm for Computing Max-Flow Vitality in Undirected Unweighted Planar Graphs
9: Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances
10: Determinants from homomorphisms
11: Deterministic Self-Adjusting Tree Networks Using Rotor Walks
12: Parameterized Sensitivity Oracles and Dynamic Algorithms using Exterior Algebras
13: Memory Bounds for Continual Learning
14: An Algorithm to Find Sums of Powers of Consecutive Primes
15: Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds
16: BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale
17: Partitioning into degenerate graphs in linear time
18: Approximation Algorithms for Interdiction Problem with Packing Constraints
19: Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond $1/2$-Approximation
20: Hierarchical Locality Sensitive Hashing for Structured Data: A Survey
21: String Rearrangement Inequalities and a Total Order Between Primitive Words
22: Facility Location Games Beyond Single-Peakedness: the Entrance Fee Model
23: Smoothed Analysis of the Koml'os Conjecture
24: Graph Product Structure for h-Framed Graphs
25: A Structural Investigation of the Approximability of Polynomial-Time Problems
26: Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs
27: Partitioning Problems with Splittings and Interval Targets
28: Properly learning monotone functions via local reconstruction
29: Faster Fundamental Graph Algorithms via Learned Predictions
30: Mirror Games Against an Open Book Player
31: Budgeted Out-tree Maximization with Submodular Prizes
32: Lattices Without a Big Constant and With Noise
33: Polylogarithmic Sketches for Clustering
34: Tolerant Bipartiteness Testing in Dense Graphs
35: Streaming Algorithms for High-Dimensional Robust Statistics
36: A Review of In-Memory Space-Efficient Data Structures for Temporal Graphs
37: Distances Release with Differential Privacy in Tree and Grid Graph
38: A 3-Approximation Algorithm for a Particular Case of the Hamiltonian p-Median Problem
39: MaxSAT with Absolute Value Functions: A Parameterized Perspective
40: Optimal Closeness Testing of Discrete Distributions Made (Complex) Simple
41: Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching
42: A Branch-and-Price Approach to a Variant of the Cognitive Radio Resource Allocation Problem
43: Speeding Hirschberg Algorithm for Sequence Alignment
44: Allocating with Priorities and Quotas: Algorithms, Complexity, and Dynamics
45: Faster online calibration without randomization: interval forecasts and the power of two choices
46: Polynomial Time Algorithm for ARRIVAL on Tree-like Multigraphs
47: Weighted Packet Selection for Rechargeable Links: Complexity and Approximation
48: Algorithmic QUBO Formulations for k-SAT and Hamiltonian Cycles
49: Generic Dijkstra: correctness and tractability