Loss Minimization for Electrical Flows over Spanning Trees on Grids
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916532635828224 |
|---|---|
| author | Ito, Takehiro Kakimura, Naonori Kamiyama, Naoyuki Kobayashi, Yusuke Okamoto, Yoshio |
| author_facet | Ito, Takehiro Kakimura, Naonori Kamiyama, Naoyuki Kobayashi, Yusuke Okamoto, Yoshio |
| contents | We study the electrical distribution network reconfiguration problem, defined as follows. We are given an undirected graph with a root vertex, demand at each non-root vertex, and resistance on each edge. Then, we want to find a spanning tree of the graph that specifies the routing of power from the root to each vertex so that all the demands are satisfied and the energy loss is minimized. This problem is known to be NP-hard in general. When restricted to grids with uniform resistance and the root located at a corner, Gupta, Khodabaksh, Mortagy and Nikolova [Mathematical Programming 2022] invented the so-called Min-Min algorithm whose approximation factor is theoretically guaranteed. Our contributions are twofold. First, we prove that the problem is NP-hard even for grids; this resolves the open problem posed by Gupta et al. Second, we give a refined analysis of the Min-Min algorithm and improve its approximation factor under the same setup. In the analysis, we formulate the problem of giving an upper bound for the approximation factor as a non-linear optimization problem that maximizes a convex function over a polytope, which is less commonly employed in the analysis of approximation algorithms than linear optimization problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_14583 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Loss Minimization for Electrical Flows over Spanning Trees on Grids Ito, Takehiro Kakimura, Naonori Kamiyama, Naoyuki Kobayashi, Yusuke Okamoto, Yoshio Data Structures and Algorithms Optimization and Control 68W25, 90C27 We study the electrical distribution network reconfiguration problem, defined as follows. We are given an undirected graph with a root vertex, demand at each non-root vertex, and resistance on each edge. Then, we want to find a spanning tree of the graph that specifies the routing of power from the root to each vertex so that all the demands are satisfied and the energy loss is minimized. This problem is known to be NP-hard in general. When restricted to grids with uniform resistance and the root located at a corner, Gupta, Khodabaksh, Mortagy and Nikolova [Mathematical Programming 2022] invented the so-called Min-Min algorithm whose approximation factor is theoretically guaranteed. Our contributions are twofold. First, we prove that the problem is NP-hard even for grids; this resolves the open problem posed by Gupta et al. Second, we give a refined analysis of the Min-Min algorithm and improve its approximation factor under the same setup. In the analysis, we formulate the problem of giving an upper bound for the approximation factor as a non-linear optimization problem that maximizes a convex function over a polytope, which is less commonly employed in the analysis of approximation algorithms than linear optimization problems. |
| title | Loss Minimization for Electrical Flows over Spanning Trees on Grids |
| topic | Data Structures and Algorithms Optimization and Control 68W25, 90C27 |
| url | https://arxiv.org/abs/2412.14583 |