A Spectral Approach to Network Design
From MaRDI portal
Publication:5092510
DOI10.1137/20M1330762zbMath1502.05136OpenAlexW3011353849MaRDI QIDQ5092510
Publication date: 22 July 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/20m1330762
Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On generalizations of network design problems with degree bounds
- Freedman's inequality for matrix martingales
- Network design via iterative rounding of setpair relaxations
- A factor 2 approximation algorithm for the generalized Steiner network problem
- A unified algorithm for degree bounded survivable network design
- On selecting a maximum volume sub-matrix of a matrix and related problems
- Covering problems for Brownian motion on spheres
- On tail probabilities for martingales
- The electrical resistance of a graph captures its commute and cover times
- On graphs with algebraic connectivity equal to minimum edge density
- Chain-constrained spanning trees
- Approximating MIN-cost chain-constrained spanning trees: a reduction from weighted to unweighted problems
- Four deviations suffice for rank 1 matrices
- Near-optimal discrete optimization for experimental design: a regret minimization approach
- Queries and concept learning
- Interlacing families. I: Bipartite Ramanujan graphs of all degrees
- Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
- Design networks with bounded pairwise distance
- Subgraph sparsification and nearly optimal ultrasparsifiers
- Approximating Minimum-Cost $k$-Node Connected Subgraphs via Independence-Free Graphs
- Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates
- Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design
- Approximating the smallest k -edge connected spanning subgraph by LP-rounding
- Iterative Methods in Combinatorial Optimization
- Spectral Sparsification of Graphs
- Improved Algorithm for Degree Bounded Survivable Network Design Problem
- Survivable Network Design with Degree or Order Constraints
- On the L ∞ -Norm of Extreme Points for Crossing Supermodular Directed Network LPs
- Approximating the Minimum-Degree Steiner Tree to within One of Optimal
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
- Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
- Fastest Mixing Markov Chain on a Graph
- A General Approximation Technique for Constrained Forest Problems
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Twice-Ramanujan Sparsifiers
- Sparse Sums of Positive Semidefinite Matrices
- An SDP-based algorithm for linear-sized spectral sparsification
- Algorithmic discrepancy beyond partial coloring
- Graph Clustering using Effective Resistance
- O (log 2 k / log log k )-approximation algorithm for directed Steiner tree
- On a generalization of iterated and randomized rounding
- An almost-linear time algorithm for uniform random spanning tree generation
- Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design
- Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements
- Optimal Design of Experiments
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Fast Generation of Random Spanning Trees and the Effective Resistance Metric
- Steiner Tree Approximation via Iterative Randomized Rounding
- Additive Approximation for Bounded Degree Survivable Network Design
- Cover times, blanket times, and majorizing measures
- Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
- Minimizing Effective Resistance of a Graph
- Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal
- Approximation algorithms for degree-constrained minimum-cost network-design problems
- Graph Sparsification by Effective Resistances
- Network Design for s - t Effective Resistance
This page was built for publication: A Spectral Approach to Network Design
