StringologyTimes

Data Structures and Algorithms: 2021/7/01-07

1: Coresets for Clustering with Missing Values
2: The Power of Adaptivity for Stochastic Submodular Cover
3: Nearly-Tight and Oblivious Algorithms for Explainable Clustering
4: String Comparison on a Quantum Computer Using Hamming Distance
5: Grid Recognition: Classical and Parameterized Computational Perspectives
6: Robust and Fully-Dynamic Coreset for Continuous-and-Bounded Learning (With Outliers) Problems
7: A Simple Linear-Time Algorithm for the Common Refinement of Rooted Phylogenetic Trees on a Common Leaf Set
8: Improved Analysis of Online Balanced Clustering
9: $L_p$ Isotonic Regression Algorithms Using an $L_0$ Approach
10: Backtracking (the) Algorithms on the Hamiltonian Cycle Problem
11: Evidence for Long-Tails in SLS Algorithms
12: On Variants of Facility Location Problem with Outliers
13: Compression by Contracting Straight-Line Programs
14: Asymptotically Optimal Welfare of Posted Pricing for Multiple Items with MHR Distributions
15: Orienting (hyper)graphs under explorable stochastic uncertainty
16: Modular counting of subgraphs: Matchings, matching-splittable graphs, and paths
17: Online Euclidean Spanners
18: On the Bike Spreading Problem
19: Almost Tight Approximation Algorithms for Explainable Clustering
20: Near-optimal Algorithms for Explainable k-Medians and k-Means
21: Decision tree heuristics can fail, even in the smoothed setting
22: Sequential importance sampling for estimating expectations over the space of perfect matchings
23: Online Matching in Sparse Random Graphs: Non-Asymptotic Performances of Greedy Algorithm
24: An Improved Fixed-Parameter Algorithm for 2-Club Cluster Edge Deletion
25: Linear Probing Revisited: Tombstones Mark the Death of Primary Clustering
26: Average-Case Communication Complexity of Statistical Problems
27: Engineering MultiQueues: Fast Relaxed Concurrent Priority Queues
28: Recombinant Sort: N-Dimensional Cartesian Spaced Algorithm Designed from Synergetic Combination of Hashing, Bucket, Counting and Radix Sort
29: Solving Infinite-Domain CSPs Using the Patchwork Property
30: On Tightness of Tsaknakis-Spirakis Descent Methods for Approximate Nash Equilibria
31: Algorithms for normalized multiple sequence alignments
32: Closing the gap for single resource constraint scheduling
33: Sublinear-Space Approximation Algorithms for Max r-SAT
34: Fine-Grained Completeness for Optimization in P
35: Dynamic programming by polymorphic semiring algebraic shortcut fusion
36: Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering
37: Spanner Approximations in Practice
38: Tight Guarantees for Multi-unit Prophet Inequalities and Online Stochastic Knapsack
39: DIRECTGO: A new DIRECT-type MATLAB toolbox for derivative-free global optimization
40: Incremental Edge Orientation in Forests
41: Unifying Width-Reduced Methods for Quasi-Self-Concordant Optimization
42: On Arithmetically Progressed Suffix Arrays and related Burrows-Wheeler Transforms
43: On the Hardness of Compressing Weights
44: Irregular Invertible Bloom Look-Up Tables
45: Noisy Boolean Hidden Matching with Applications
46: A General Approach to Approximate Multistage Subgraph Problems
47: Making Three Out of Two: Three-Way Online Correlated Selection
48: Defeating duplicates: A re-design of the LearnedSort algorithm
49: Distance Estimation Between Unknown Matrices Using Sublinear Projections on Hamming Cube
50: DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search
51: Dueling Bandits with Team Comparisons
52: Submodular Order Functions and Assortment Optimization
53: MAJORITY-3SAT (and Related Problems) in Polynomial Time
54: Space Efficient Two-Dimensional Orthogonal Colored Range Counting
55: Telescoping Filter: A Practical Adaptive Filter
56: Twin-width and polynomial kernels
57: On the Fault-Tolerant Online Bin Packing Problem
58: Fractional homomorphism, Weisfeiler-Leman invariance, and the Sherali-Adams hierarchy for the Constraint Satisfaction Problem
59: Budgeted Dominating Sets in Uncertain Graphs
60: An Approximation Algorithm for Maximum Stable Matching with Ties and Constraints
61: Reconfiguring (non-spanning) arborescences
62: Refined Computational Complexities of Hospitals/Residents Problem with Regional Caps
63: A Heuristic for Direct Product Graph Decomposition
64: Oblivious Median Slope Selection