StringologyTimes

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

1: Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-Means
2: Linear Programming Based Near-Optimal Pricing for Laminar Bayesian Online Selection
3: Online Submodular Maximization: Beating 1/2 Made Simple
4: Deterministic (1/2 + {\epsilon})-Approximation for Submodular Maximization over a Matroid
5: A new lower bound for classic online bin packing
6: Improving the smoothed complexity of FLIP for max cut problems
7: Faster Algorithms for All-Pairs Bounded Min-Cuts
8: Finding a marked node on any graph by continuous-time quantum walk
9: Exact Distance Oracles for Planar Graphs with Failing Vertices
10: A PTAS for $\ell_p$-Low Rank Approximation
11: Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing
12: Waring Rank, Parameterized and Exact Algorithms
13: Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation
14: Almost optimal query algorithm for hitting set using a subset query
15: Using statistical encoding to achieve tree succinctness never seen before
16: Quantum Chebyshev’s Inequality and Applications
17: Tracking the $\ell_2$ Norm with Constant Update Time
18: Dynamic Sampling from Graphical Models
19: Optimization of the n-dimensional sliding window inter-channel correlation algorithm for multi-core architecture
20: Fisher zeros and correlation decay in the Ising model
21: Distributed Triangle Detection via Expander Decomposition
22: The Online $k$-Taxi Problem
23: Derandomizing the Lovasz Local Lemma via log-space statistical tests
24: Supermodular Locality Sensitive Hashes
25: Massively Parallel Symmetry Breaking on Sparse Graphs: MIS and Maximal Matching
26: Deterministic oblivious distribution (and tight compaction) in linear time
27: The Scheduler is Very Powerful in Competitive Analysis of Distributed List Accessing
28: An Information-theoretic Framework for the Lossy Compression of Link Streams
29: Time-Bounded Influence Diffusion with Incentives
30: An ETH-Tight Exact Algorithm for Euclidean TSP
31: The parameterised complexity of computing the maximum modularity of a graph
32: Quantified boolean formula problem
33: Learning Sums of Independent Random Variables with Sparse Collective Support
34: A Fixed-Parameter Linear-Time Algorithm to Compute Principal Typings of Planar Flow Networks
35: Reconstructing Latent Orderings by Spectral Clustering
36: Fast and Deterministic Approximations for $k$-Cut
37: Approximation Schemes for Low-Rank Binary Matrix Approximation Problems
38: A $\phi$-Competitive Algorithm for Scheduling Packets with Deadlines
39: A Tale of Santa Claus, Hypergraphs and Matroids
40: About BIRDS project (Bioinformatics and Information Retrieval Data Structures Analysis and Design)
41: Prophet Secretary Through Blind Strategies
42: Exact Algorithms for Finding Well-Connected 2-Clubs in Real-World Graphs: Theory and Experiments
43: Optimal Las Vegas Approximate Near Neighbors in $\ell_p$
44: The colored longest common prefix array computed via sequential scans
45: Generalized Metric Repair on Graphs
46: Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
47: Multi-Resolution Hashing for Fast Pairwise Summations
48: Coloring in Graph Streams
49: Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
50: On Euclidean Methods for Cubic and Quartic Jacobi Symbols
51: Biclustering Using Modified Matrix Bandwidth Minimization and Biogeography-based Optimization
52: An Improved Speedup Factor for Sporadic Tasks with Constrained Deadlines under Dynamic Priority Scheduling
53: Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity
54: Red-Blue-Partitioned MST, TSP, and Matching
55: Fast Matrix Inversion and Determinant Computation for Polarimetric Synthetic Aperture Radar
56: Faster Exact and Approximate Algorithms for $k$-Cut