Search

We consider a new problem of designing a network with small s - t effective resistance. In this problem, we are given an undirected graph G = (V,E) , two designated vertices s,t ∈ V , and a budget k . The goal is to choose a subgraph of G with at most k edges to minimize the s - t effective resistance. This problem is an interpolation between the shortest path problem and the minimum cost flow problem and has applications in electrical network design. We present several algorithmic and hardness results for this problem and its variants. On the hardness side, we show that the problem is NP-hard, and the weighted version is hard to approximate within a factor smaller than two assuming the small-set expansion conjecture. On the algorithmic side, we analyze a convex programming relaxation of the problem and design a constant factor approximation algorithm. The key of the rounding algorithm is a randomized path-rounding procedure based on the optimality conditions and a flow decomposition of the fractional solution. We also use dynamic programming to obtain a fully polynomial time approximation scheme when the input graph is a series-parallel graph, with better approximation ratio than the integrality gap of the convex program for these graphs.

We present a spectral approach to design approximation algorithms for network design problems. We observe that the underlying mathematical questions are the spectral rounding problems, which were studied in spectral sparsification and in discrepancy theory. We extend these results to incorporate additional non-negative linear constraints, and show that they can be used to significantly extend the scope of network design problems that can be solved. Our algorithm for spectral rounding is an iterative randomized rounding algorithm based on the regret minimization framework. In some settings, this provides an alternative spectral algorithm to achieve constant factor approximation for the classical survivable network design problem, and partially answers a question of Bansal about survivable network design with concentration property. We also show many other applications of the spectral rounding results, including weighted experimental design and additive spectral sparsification., Comment: Improved bound on one-sided spectral rounding by a randomized swapping algorithm. Added the proof of the deterministic algorithm for additive sparsifers

We present a local search framework to design and analyze both combinatorial algorithms and rounding algorithms for experimental design problems. This framework provides a unifying approach to match and improve all known results in D/A/E-design and to obtain new results in previously unknown settings. For combinatorial algorithms, we provide a new analysis of the classical Fedorov's exchange method. We prove that this simple local search algorithm works well as long as there exists an almost optimal solution with good condition number. Moreover, we design a new combinatorial local search algorithm for E-design using the regret minimization framework. For rounding algorithms, we provide a unified randomized exchange algorithm to match and improve previous results for D/A/E-design. Furthermore, the algorithm works in the more general setting to approximately satisfy multiple knapsack constraints, which can be used for weighted experimental design and for incorporating fairness constraints into experimental design., Improved probability bound in Theorem 1.4. A preliminary version accepted by SODA 2021

We present a spectral analysis of a continuous scaling algorithm for matrix scaling and operator scaling. The main result is that if the input matrix or operator has a spectral gap, then a natural gradient flow has linear convergence. This implies that a simple gradient descent algorithm also has linear convergence under the same assumption. The spectral gap condition for operator scaling is closely related to the notion of quantum expander studied in quantum information theory. The spectral analysis also provides bounds on some important quantities of the scaling problems, such as the condition number of the scaling solution and the capacity of the matrix and operator. These results can be used in various applications of scaling problems, including matrix scaling on expander graphs, permanent lower bounds on random matrices, the Paulsen problem on random frames, and Brascamp-Lieb constants on random operators. In some applications, the inputs of interest satisfy the spectral condition and we prove significantly stronger bounds than the worst case bounds.

In the Minimum Bounded Degree Spanning Tree problem, we are given an undirected graph G = ( V, E ) with a degree upper bound B v on each vertex v ∈ V , and the task is to find a spanning tree of minimum cost that satisfies all the degree bounds. Let OPT be the cost of an optimal solution to this problem. In this article we present a polynomial-time algorithm which returns a spanning tree T of cost at most OPT and d T ( v ) ≤ B v + 1 for all v , where d T ( v ) denotes the degree of v in T . This generalizes a result of Fürer and Raghavachari [1994] to weighted graphs, and settles a conjecture of Goemans [2006] affirmatively. The algorithm generalizes when each vertex v has a degree lower bound A v and a degree upper bound B v , and returns a spanning tree with cost at most OPT and A v - 1 ≤ d T ( v ) ≤ B v + 1 for all v ∈ V . This is essentially the best possible. The main technique used is an extension of the iterative rounding method introduced by Jain [2001] for the design of approximation algorithms.

We present an approximation algorithm for the minimum bounded degree Steiner network problem that returns a Steiner network of cost at most two times the optimal and the degree on each vertex $$v$$v is at most $$\min \{b_v + 3r_{\mathrm{max}}, 2b_v+2\}$$min{bv+3rmax,2bv+2}, where $$r_{\mathrm{max}}$$rmax is the maximum connectivity requirement and $$b_v$$bv is the given degree bound on $$v$$v. This unifies, simplifies, and improves the previous results for this problem.

The Paulsen problem is a basic open problem in operator theory: Given vectors $u_1, \ldots, u_n \in \mathbb R^d$ that are $\epsilon$-nearly satisfying the Parseval's condition and the equal norm condition, is it close to a set of vectors $v_1, \ldots, v_n \in \mathbb R^d$ that exactly satisfy the Parseval's condition and the equal norm condition? Given $u_1, \ldots, u_n$, the squared distance (to the set of exact solutions) is defined as $\inf_{v} \sum_{i=1}^n \| u_i - v_i \|_2^2$ where the infimum is over the set of exact solutions. Previous results show that the squared distance of any $\epsilon$-nearly solution is at most $O({\rm{poly}}(d,n,\epsilon))$ and there are $\epsilon$-nearly solutions with squared distance at least $\Omega(d\epsilon)$. The fundamental open question is whether the squared distance can be independent of the number of vectors $n$. We answer this question affirmatively by proving that the squared distance of any $\epsilon$-nearly solution is $O(d^{13/2} \epsilon)$. Our approach is based on a continuous version of the operator scaling algorithm and consists of two parts. First, we define a dynamical system based on operator scaling and use it to prove that the squared distance of any $\epsilon$-nearly solution is $O(d^2 n \epsilon)$. Then, we show that by randomly perturbing the input vectors, the dynamical system will converge faster and the squared distance of an $\epsilon$-nearly solution is $O(d^{5/2} \epsilon)$ when $n$ is large enough and $\epsilon$ is small enough. To analyze the convergence of the dynamical system, we develop some new techniques in lower bounding the operator capacity, a concept introduced by Gurvits to analyze the operator scaling algorithm., Comment: Added Subsection 1.4; Incorporated comments and fixed typos; Minor changes in various places