StringologyTimes

Data Structures and Algorithms: 2015/7/08-14

1: Polynomial-time isomorphism test of groups that are tame extensions
2: Efficient Implementation of a Synchronous Parallel Push-Relabel Algorithm
3: On the pathwidth of almost semicomplete digraphs
4: Dynamic Reallocation Problems in Scheduling
5: Random Walks and Evolving Sets: Faster Convergences and Limitations
6: Zero-free regions of partition functions with applications to algorithms and graph limits
7: Locating a Tree in a Reticulation-Visible Network in Cubic Time
8: Independence and Efficient Domination on $P_6$-free Graphs
9: Edge Bipartization faster than $2^k$
10: Directed multicut is W[1]-hard, even for four terminal pairs
11: The “art of trellis decoding” is fixed-parameter tractable
12: Approximate Clustering via Metric Partitioning
13: L infinity Isotonic Regression for Linear, Multidimensional, and Tree Orders
14: Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver
15: Optimal approximate matrix product in terms of stable rank
16: Distinguishing Hidden Markov Chains
17: A Faster Pseudopolynomial Time Algorithm for Subset Sum
18: Multisection in the Stochastic Block Model using Semidefinite Programming
19: On an almost-universal hash function family with applications to authentication and secrecy codes
20: Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions
21: Online Algorithms for Multi-Level Aggregation
22: Maximum matching width: new characterizations and a fast algorithm for dominating set
23: Planar Ultrametric Rounding for Image Segmentation
24: Ride Sharing with a Vehicle of Unlimited Capacity
25: Algorithmic Complexity of Power Law Networks
26: Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
27: Differentially Private Ordinary Least Squares
28: An algorithm for fast computation of the multiresolution discrete Fourier transform
29: Sampling from a log-concave distribution with Projected Langevin Monte Carlo
30: Optimal Auctions vs. Anonymous Pricing
31: Sublinear Distance Labeling
32: Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state-space-time network representations
33: A simplified 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
34: On the Connectedness of Clash-free Timetables
35: Calibrations Scheduling Problem with Arbitrary Lengths and Activation Length
36: Finger Search in Grammar-Compressed Strings
37: A $1.75$ LP approximation for the Tree Augmentation Problem
38: The Maximum Number of 3- and 4-Cliques within a Planar Maximally Filtered Graph
39: A Bloom filter based semi-index on $q$-grams
40: An efficient tree decomposition method for permanents and mixed discriminants
41: Micro-Clustering: Finding Small Clusters in Large Diversity
42: CoveringLSH: Locality-sensitive Hashing without False Negatives
43: Tensor principal component analysis via sum-of-squares proofs
44: Aren’t we all nearest neighbors: Spatial trees, high dimensional reductions and batch nearest neighbor search
45: Deciding Circular-Arc Graph Isomorphism in Parameterized Logspace
46: Time-Space Trade-offs for Triangulations and Voronoi Diagrams
47: On the Turing model complexity of interior point methods for semidefinite programming
48: Testing Shape Restrictions of Discrete Distributions
49: Deadline-aware Power Management in Data Centers
50: A New Framework for Distributed Submodular Maximization
51: Tight Bounds for Subgraph Isomorphism and Graph Homomorphism
52: A Lower Bound on Supporting Predecessor Search in $k$ sorted Arrays