Pith. sign in

REVIEW

The Complexity of DC-Switching Problems

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1411.4369 v1 pith:CWI3AFTJ submitted 2014-11-17 cs.CC math.OC

Karsten Lehmann , Alban Grastien , Pascal Van Hentenryck This is my paper · ORCID
classification cs.CCmath.OC
keywords problemsswitchingcomplexitydegreemaximumoptimizationadditionallyapproximated
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

This report provides a comprehensive complexity study of line switching in the Linear DC model for the feasibility problem and the optimization problems of maximizing the load that can be served (maximum switching flow, MSF) and minimizing generation cost (optimal transmission switching, OTS). Our results show that these problems are NP-complete and that there is no fully polynomial-time approximation scheme for planar networks with a maximum-node degree of 3. Additionally, we demonstrate that the problems are still NP-hard if we restrict the network structure to cacti with a maximum degree of 3. We also show that the optimization problems can not be approximated within any constant factor.

Discussion (0). Continue with ORCID to comment.

Pith tools