Query：
学者姓名：周宏
Refining：
Year
Type
Indexed by
Source
Complex
Co-
Language
Clean All
Abstract ：
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 nonnegative 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 spectral network design. © 2022 Society for Industrial and Applied Mathematics.
Keyword ：
Approximation algorithms Approximation algorithms Iterative methods Iterative methods
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Lau, Lap Chi , Zhou, Hong . A SPECTRAL APPROACH TO NETWORK DESIGN [J]. | SIAM Journal on Optimization , 2022 , 32 (3) : 1018-1064 . |
| MLA | Lau, Lap Chi 等. "A SPECTRAL APPROACH TO NETWORK DESIGN" . | SIAM Journal on Optimization 32 . 3 (2022) : 1018-1064 . |
| APA | Lau, Lap Chi , Zhou, Hong . A SPECTRAL APPROACH TO NETWORK DESIGN . | SIAM Journal on Optimization , 2022 , 32 (3) , 1018-1064 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
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 is an element of 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.
Keyword ：
Effective resistance Effective resistance network design network design
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Chan, Pak Hay , Lau, Lap Chi , Schild, Aaron et al. Network Design for s-t Effective Resistance [J]. | ACM TRANSACTIONS ON ALGORITHMS , 2022 , 18 (3) . |
| MLA | Chan, Pak Hay et al. "Network Design for s-t Effective Resistance" . | ACM TRANSACTIONS ON ALGORITHMS 18 . 3 (2022) . |
| APA | Chan, Pak Hay , Lau, Lap Chi , Schild, Aaron , Wong, Sam Chiu-Wai , Zhou, Hong . Network Design for s-t Effective Resistance . | ACM TRANSACTIONS ON ALGORITHMS , 2022 , 18 (3) . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
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 nonnegative 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 spectral network design.
Keyword ：
network design network design regret minimization regret minimization spectral rounding spectral rounding
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Lau, Lap Chi , Zhou, Hong . A SPECTRAL APPROACH TO NETWORK DESIGN [J]. | SIAM JOURNAL ON COMPUTING , 2022 , 51 (4) : 1018-1064 . |
| MLA | Lau, Lap Chi et al. "A SPECTRAL APPROACH TO NETWORK DESIGN" . | SIAM JOURNAL ON COMPUTING 51 . 4 (2022) : 1018-1064 . |
| APA | Lau, Lap Chi , Zhou, Hong . A SPECTRAL APPROACH TO NETWORK DESIGN . | SIAM JOURNAL ON COMPUTING , 2022 , 51 (4) , 1018-1064 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
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.
Keyword ：
experimental design experimental design local search local search spectral rounding spectral rounding
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Lau, Lap chi , Zhou, Hong . A LOCAL SEARCH FRAMEWORK FOR EXPERIMENTAL DESIGN [J]. | SIAM JOURNAL ON COMPUTING , 2022 , 51 (4) : 900-951 . |
| MLA | Lau, Lap chi et al. "A LOCAL SEARCH FRAMEWORK FOR EXPERIMENTAL DESIGN" . | SIAM JOURNAL ON COMPUTING 51 . 4 (2022) : 900-951 . |
| APA | Lau, Lap chi , Zhou, Hong . A LOCAL SEARCH FRAMEWORK FOR EXPERIMENTAL DESIGN . | SIAM JOURNAL ON COMPUTING , 2022 , 51 (4) , 900-951 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Export
| Results： |
Selected to |
| Format： |
