StringologyTimes

Data Structures and Algorithms: 2016/11/22-28

1: Simple Mechanisms for Subadditive Buyers via Duality
2: A Framework for Analyzing Resparsification Algorithms
3: Fine-Grained Complexity and Conditional Hardness for Sparse Graphs
4: A Data Structure for Nearest Common Ancestors with Linking
5: A New Approach to Laplacian Solvers and Flow Problems
6: Quasi-regular sequences and optimal schedules for security games
7: Distributable Consistent Multi-Object Matching
8: Approximate Furthest Neighbor with Application to Annulus Query
9: Correlation Clustering with Low-Rank Matrices
10: Asymptotic expansions for factorial moments of some distributions in the analysis of algorithms
11: Lazy Local Search Meets Machine Scheduling
12: The Heterogeneous Capacitated $k$-Center Problem
13: Sampling Random Spanning Trees Faster than Matrix Multiplication
14: Depth of vertices with high degree in random recursive trees
15: Approximating k-Forest with Resource Augmentation: A Primal-Dual Approach
16: Purchasing a C_4 online
17: Data Structures for Weighted Matching and Extensions to $b$-matching and $f$-factors
18: Efficient Delivery Policy to Minimize User Traffic Consumption in Guaranteed Advertising
19: Optimal Pricing for Submodular Valuations with Bounded Curvature
20: Faster Population Counts Using AVX2 Instructions
21: Symbolic BDD and ADD Algorithms for Energy Games
22: Special cases of the quadratic shortest path problem
23: Simultaneous Feedback Edge Set: A Parameterized Perspective
24: Knapsack Problems: A Parameterized Point of View
25: Timing Matters: Online Dynamics in Broadcast Games
26: A Faster Algorithm for Cuckoo Insertion and Bipartite Matching in Large Graphs
27: Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion
28: Testing submodularity and other properties of valuation functions
29: On ($1$, $\epsilon$)-Restricted Max-Min Fair Allocation Problem
30: Burrows-Wheeler transform and LCP array construction in constant space
31: Search on a Line by Byzantine Robots
32: Detecting communities is hard, and counting them is even harder
33: On preparing ground states of gapped Hamiltonians: An efficient Quantum Lov'asz Local Lemma
34: An Efficient Streaming Algorithm for the Submodular Cover Problem
35: Whom to befriend to influence people
36: Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method
37: Number Balancing is as hard as Minkowski’s Theorem and Shortest Vector
38: A Linear-time Algorithm for Integral Multiterminal Flows in Trees
39: Fixed-Parameter Algorithms for DAG Partitioning
40: A spectral gap precludes low-dimensional embeddings
41: On the Size of Lempel-Ziv and Lyndon Factorizations
42: On Low-Space Differentially Private Low-rank Factorization in the Spectral Norm
43: Online Knapsack Problem and Budgeted Truthful Bipartite Matching
44: Faster Randomized Worst-Case Update Time for Dynamic Subgraph Connectivity
45: Hierarchical Hyperlink Prediction for the WWW