StringologyTimes

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

1: Time complexity of the Analyst’s Traveling Salesman algorithm
2: Graph Coloring and Semidefinite Rank
3: A Probabilistic Approach to The Perfect Sum Problem
4: Loop unrolling of UCA models: distance labeling
5: Better Private Algorithms for Correlation Clustering
6: The near exact bin covering problem
7: Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
8: A Framework for Distributed Quantum Queries in the CONGEST Model
9: The Dichotomous Affiliate Stable Matching Problem: Approval-Based Matching with Applicant-Employer Relations
10: Constant matters: Fine-grained Complexity of Differentially Private Continual Observation
11: A QUBO formulation for the Tree Containment problem
12: Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv
13: Finding Safe Zones of policies Markov Decision Processes
14: Induced Disjoint Paths and Connected Subgraphs for $H$-Free Graphs
15: Globally Convergent Policy Search over Dynamic Filters for Output Estimation
16: A Partition-and-Merge Algorithm for Solving the Steiner Tree Problem in Large Graphs
17: A PTAS for Packing Hypercubes into a Knapsack
18: Polynomial Kernels for Tracking Shortest Paths
19: Exact Matching in Graphs of Bounded Independence Number
20: Parameterized Complexity of Graph Partitioning into Connected Clusters
21: Counting Temporal Paths
22: A Dynamic Low-Rank Fast Gaussian Transform
23: List Locally Surjective Homomorphisms in Hereditary Graph Classes
24: Making Life More Confusing for Firefighters
25: Towards Optimal Lower Bounds for k-median and k-means Coresets
26: Dynamic size counting in population protocols
27: Near Optimal Reconstruction of Spherical Harmonic Expansions
28: Compressed Matrix Computations
29: Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
30: Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
31: A survey of BWT variants for string collections
32: Parallel algorithm for pattern matching problems under substring consistent equivalence relations
33: Approximation Algorithms for Flexible Graph Connectivity
34: A logic-based algorithmic meta-theorem for mim-width
35: Enumeration of chordal planar graphs and maps
36: On Problems Related to Unbounded SubsetSum: A Unified Combinatorial Approach
37: Minimal Absent Words on Run-Length Encoded Strings
38: Cutting a tree with Subgraph Complementation is hard, except for some small trees
39: Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts
40: Improved Combinatorial Approximation Algorithms for MAX CUT in Sparse Graphs
41: On the Robustness of CountSketch to Adaptive Inputs