Electrical flows over spanning trees
Electrical flows over spanning trees
复制标题
跨树上的电流
DOI：
10.1007/s10107-020-01614-x
复制
发表时间：
2021
影响因子：
2.7
通讯作者：
Nikolova, Evdokia
中科院分区：
文献类型：
--
作者：
Gupta, Swati;Khodabakhsh, Ali;Mortagy, Hassan;Nikolova, Evdokia
网络重构问题寻求找到一个有根的树，使得（唯一的）可行电流的能量最小。对潮流支持的树型要求是由配电网的运行约束所驱动的。现有的关于多面体顶点上的凸优化和电流结构的大部分结果都不容易给出这个问题的保证，而早在1989年电力系统界就已经开发了许多启发式方法。我们的主要贡献是给出了网络重构问题的第一个可证明的近似保证。我们为各种设置提供了新的下界和相应的近似因子，范围从一般图，边缘上具有均匀电阻的网格，以及具有均匀边缘电阻和要求的网格。为了获得一般图的结果，我们提出了一种新的（近似）谱图稀疏化方法，这可能是一个独立的兴趣。利用我们的理论结果的见解，我们提出了一种通用的启发式网络重构问题，它比文献中现有的方法快几个数量级，同时获得了相当的性能。
Thenetwork reconfigurationproblem seeks to find a rooted treeTsuch that the energy of the (unique) feasible electrical flow overTis minimized. The tree requirement on the support of the flow is motivated by operational constraints in electricity distribution networks. The bulk of existing results on convex optimization over vertices of polytopes and on the structure of electrical flows do not easily give guarantees for this problem, while many heuristic methods have been developed in the power systems community as early as 1989. Our main contribution is to give the first provable approximation guarantees for the network reconfiguration problem. We provide novel lower bounds and corresponding approximation factors for various settings ranging fromfor general graphs, toover grids with uniform resistances on edges, andfor grids with uniform edge resistances and demands. To obtain the result for general graphs, we propose a new method for (approximate) spectral graph sparsification, which may be of independent interest. Using insights from our theoretical results, we propose a general heuristic for the network reconfiguration problem that is orders of magnitude faster than existing methods in the literature, while obtaining comparable performance.
登录
查看更多内容
DOI：
--
发表时间：
1988
期刊：
International Symposium on Mathematical Foundations of Computer Science
影响因子：
--
作者：
K. Diks;H. Djidjev;O. Sýkora;I. Vrto
通讯作者：
I. Vrto
最小化多面体整数点上的 Lipschitz 连续强凸函数
影响因子：
2.7
作者：
M. Baes;Alberto Del Pia;Y. Nesterov;S. Onn;R. Weismantel
通讯作者：
R. Weismantel
DOI：
10.1090/dimacs/007/01
发表时间：
1991
期刊：
--
影响因子：
--
作者：
N. Alon;R. Karp;D. Peleg;D. West
通讯作者：
N. Alon;R. Karp;D. Peleg;D. West
DOI：
10.1145/1250790.1250887
发表时间：
2007-06
期刊：
--
影响因子：
--
作者：
Mohit Singh;L. Lau
通讯作者：
Mohit Singh;L. Lau
DOI：
10.1109/focs.2018.00042
发表时间：
2018-05
期刊：
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
T. Chu;Yu Gao;Richard Peng;Sushant Sachdeva;Saurabh Sawlani;Junxing Wang
通讯作者：
T. Chu;Yu Gao;Richard Peng;Sushant Sachdeva;Saurabh Sawlani;Junxing Wang