StringologyTimes

Data Structures and Algorithms: 2020/7/15-21

1: Graph Sparsification by Universal Greedy Algorithms
2: Competitively Pricing Parking in a Tree
3: A Pairwise Fair and Community-preserving Approach to k-Center Clustering
4: On the hop-constrained Steiner tree problems
5: Downsampling for Testing and Learning in Product Distributions
6: An algorithm for integrating peer-to-peer ridesharing and schedule-based transit system for first mile/last mile access
7: Improved algorithms for online load balancing
8: A Faster Exact Algorithm to Count X3SAT Solutions
9: Minimum Weight Pairwise Distance Preservers
10: A linear-time parameterized algorithm for computing the width of a DAG
11: Leafy Spanning Arborescences in DAGs
12: On Indexing and Compressing Finite Automata
13: An $\tilde{O}(n^{5/4})$ Time $\varepsilon$-Approximation Algorithm for RMS Matching in a Plane
14: Online Generalized Network Design Under (Dis)Economies of Scale
15: Adapting the Directed Grid Theorem into an FPT Algorithm
16: Permutree sorting
17: Vertex Sparsification for Edge Connectivity
18: Directed Shortest Paths via Approximate Cost Balancing
19: Static pricing for multi-unit prophet inequalities
20: Approximating the (Continuous) Fr'echet Distance
21: Optimal Coreset for Gaussian Kernel Density Estimation
22: Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon
23: Rapid Mixing for Colorings via Spectral Independence
24: The Swendsen-Wang Dynamics on Trees
25: Maximizing coverage while ensuring fairness: a tale of conflicting objective
26: Augmented Sparsifiers for Generalized Hypergraph Cuts with Applications to Decomposable Submodular Function Minimization
27: Rapid mixing from spectral independence beyond the Boolean domain
28: The Sparse Hausdorff Moment Problem, with Application to Topic Models
29: Private Approximations of a Convex Hull in Low Dimensions
30: Dynamic Products of Ranks
31: Optimal Robust Linear Regression in Nearly Linear Time
32: String Sanitization Under Edit Distance: Improved and Generalized
33: A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
34: Improved Deterministic Network Decomposition
35: Quantum algorithms for graph problems with cut queries
36: Substring Complexity in Sublinear Space
37: Improved Approximation Factor for Adaptive Influence Maximization via Simple Greedy Strategies
38: Optimal Vertex Fault-Tolerant Spanners in Polynomial Time
39: Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time
40: Polyhedral value iteration for discounted games and energy games
41: Planar Distance Oracles with Better Time-Space Tradeoffs
42: Dynamic Geometric Independent Set
43: Memoryless Algorithms for the Generalized $k$-server Problem on Uniform Metrics
44: Dominated Minimal Separators are Tame (Nearly All Others are Feral)
45: Adaptive Exact Learning in a Mixed-Up World: Dealing with Periodicity, Errors and Jumbled-Index Queries in String Reconstruction
46: Parameterized Complexity of Graph Burning
47: Efficient Exact Algorithms for Maximum Balanced Biclique Search in Bipartite Graphs
48: Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalities
49: All-Pairs LCA in DAGs: Breaking through the $O(n^{2.5})$ barrier
50: Flow-augmentation II: Undirected graphs
51: Parameter estimation for Gibbs distributions
52: On Algorithms for Solving the Rubik’s Cube
53: Efficient Linear and Affine Codes for Correcting Insertions/Deletions
54: The Combinatorial Santa Claus Problem or: How to Find Good Matchings in Non-Uniform Hypergraphs
55: Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover
56: The Edit Distance to $k$-Subsequence Universality
57: Query Complexity of Global Minimum Cut
58: Frequency Estimation in Data Streams: Learning the Optimal Hashing Scheme
59: An APX for the Maximum-Profit Routing Problem with Variable Supply
60: Additive Approximation Schemes for Load Balancing Problems
61: Formally Verified Trades in Financial Markets
62: A $2^{n/2}$-Time Algorithm for $\sqrt{n}$-SVP and $\sqrt{n}$-Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP
63: Reconstructing weighted voting schemes from partial information about their power indices
64: GRMR: Generalized Regret-Minimizing Representatives
65: Exploitation of Multiple Replenishing Resources with Uncertainty
66: FPT Algorithms for Finding Near-Cliques in $c$-Closed Graphs
67: $2$-blocks in strongly biconnected directed graphs
68: The Energy Complexity of BFS in Radio Networks
69: A polynomial time 12-approximation algorithm for restricted Santa Claus problem
70: Learning the Positions in CountSketch
71: On Distribution Testing in the Conditional Sampling Model
72: A Big Data Approach for Sequences Indexing on the Cloud via Burrows Wheeler Transform
73: On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications
74: Learning from Data to Speed-up Sorted Table Search Procedures: Methodology and Practical Guidelines
75: Quantum algorithms for escaping from saddle points
76: Solving Sparse Linear Systems Faster than Matrix Multiplication
77: Optimal $\ell_1$ Column Subset Selection and a Fast PTAS for Low Rank Approximation
78: Modular and Submodular Optimization with Multiple Knapsack Constraints via Fractional Grouping
79: Maximum Weight Disjoint Paths in Outerplanar Graphs via Single-Tree Cut Approximators
80: Online Carpooling using Expander Decompositions
81: Explicit two-deletion codes with redundancy matching the existential bound
82: Online Discrepancy Minimization for Stochastic Arrivals
83: Breaking the $2^n$ barrier for 5-coloring and 6-coloring
84: A 3/2-Approximation for the Metric Many-visits Path TSP
85: A Framework for Consistency Algorithms
86: Finding large induced sparse subgraphs in $C_{>t}$-free graphs in quasipolynomial time