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