StringologyTimes

Data Structures and Algorithms: 2021/5/15-21

1: Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach
2: Decision Diagrams for Quantum Measurements with Shallow Circuits
3: The Greedy Algorithm is \emph{not} Optimal for On-Line Edge Coloring
4: Optimal Virtual Network Embeddings for Tree Topologies
5: N-ary Huffman Encoding Using High-Degree Trees – A Performance Comparison
6: On the Complexity of Nucleolus Computation for Bipartite b-Matching Games
7: Peak Demand Minimization via Sliced Strip Packing
8: Distributed Resilient Submodular Action Selection in Adversarial Environments
9: Dynamic Spatial Matching
10: Efficient Algorithms for Quantitative Attack Tree Analysis
11: Near-Optimal Time-Energy Trade-Offs for Deterministic Leader Election
12: Dynamic Routing and Spectrum Assignment based on the Availability of Consecutive Sub-channels in Flexi-grid Optical Networks
13: Hamiltonian Cycle Problem is in P
14: PPCA: Privacy-preserving Principal Component Analysis Using Secure Multiparty Computation(MPC)
15: A hierarchical preconditioner for wave problems in quasilinear complexity
16: A New Vertex Connectivity Metric
17: Learning a Latent Simplex in Input-Sparsity Time
18: A Scalable Concurrent Algorithm for Dynamic Connectivity
19: A Neat Linked Queue with the Rear Blank Node
20: Vertex Ordering Problems in Directed Graph Streams
21: Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing
22: 99% Revenue with Constant Enhanced Competition
23: Time and Query Optimal Quantum Algorithms Based on Decision Trees
24: Interference-free Walks in Time: Temporally Disjoint Paths
25: DRIVE: One-bit Distributed Mean Estimation
26: On the Complexity of Robust Bilevel Optimization With Uncertain Follower’s Objective
27: GSF-locality is not sufficient for proximity-oblivious testing
28: A cubic vertex-kernel for Trivially Perfect Editing
29: Approximation Algorithms for Demand Strip Packing
30: The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality
31: Durable Queues: The Second Amendment
32: Online bin packing of squares and cubes
33: Can We Break Symmetry with o(m) Communication?
34: Speed Scaling On Parallel Servers with MapReduce Type Precedence Constraints
35: Pseudo-Hadamard matrices of the first generation and an algorithm for producing them
36: Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth
37: Approximation Algorithms For The Euclidean Dispersion Problems
38: Approximation Algorithms For The Dispersion Problems in a Metric Space
39: Diversity in Kemeny Rank Aggregation: A Parameterized Approach
40: The Simultaneous Assignment Problem
41: Fast Nonblocking Persistence for Concurrent Data Structures
42: Matchings with Group Fairness Constraints: Online and Offline Algorithms
43: (Sub)linear kernels for edge modification problems towards structured graph classes
44: Characterization of Super-stable Matchings
45: On the Parameterized Complexity of Polytree Learning
46: Online Risk-Averse Submodular Maximization
47: A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP
48: Finding All Bounded-Length Simple Cycles in a Directed Graph
49: Balancing the Spread of Two Opinions in Sparse Social Networks
50: Finding all minimum cost flows and a faster algorithm for the K best flow problem
51: Weighted Burrows-Wheeler Compression