@inproceedings{SchwartzSchlechteSwarat, author = {Schwartz, Stephan and Schlechte, Thomas and Swarat, Elmar}, title = {Designing Inspector Rosters with Optimal Strategies}, series = {Operations Research Proceedings 2016}, booktitle = {Operations Research Proceedings 2016}, doi = {10.1007/978-3-319-55702-1_30}, pages = {217 -- 223}, abstract = {We consider the problem of enforcing a toll on a transportation network with limited inspection resources. We formulate a game theoretic model to optimize the allocation of the inspectors, taking the reaction of the network users into account. The model includes several important aspects for practical operation of the control strategy, such as duty types for the inspectors. In contrast to an existing formulation using flows to describe the users' strategies we choose a path formulation and identify dominated user strategies to significantly reduce the problem size. Computational results suggest that our approach is better suited for practical instances.}, language = {en} } @misc{SchwartzSchlechteSwarat, author = {Schwartz, Stephan and Schlechte, Thomas and Swarat, Elmar}, title = {Designing Inspector Rosters with Optimal Strategies}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61123}, abstract = {We consider the problem of enforcing a toll on a transportation network with limited inspection resources. We formulate a game theoretic model to optimize the allocation of the inspectors, taking the reaction of the network users into account. The model includes several important aspects for practical operation of the control strategy, such as duty types for the inspectors. In contrast to an existing formulation using flows to describe the users' strategies we choose a path formulation and identify dominated user strategies to significantly reduce the problem size. Computational results suggest that our approach is better suited for practical instances.}, language = {en} } @misc{SchwartzBorndoerferBartz, author = {Schwartz, Stephan and Bornd{\"o}rfer, Ralf and Bartz, Gerald}, title = {The Graph Segmentation Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-60750}, abstract = {We investigate a graph theoretical problem arising in the automatic billing of a network toll. Given a network and a family of user paths, we study the graph segmentation problem (GSP) to cover parts of the user paths by a set of disjoint segments. The GSP is shown to be NP-hard but for special cases it can be solved in polynomial time. We also show that the marginal utility of a segment is bounded. Computational results for real-world instances show that in practice the problem is more amenable than the theoretic bounds suggest.}, language = {en} } @inproceedings{BorndoerferSagnolSchwartz, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Schwartz, Stephan}, title = {An Extended Network Interdiction Problem for Optimal Toll Control}, series = {INOC 2015 - 7th International Network Optimization Conference}, volume = {52}, booktitle = {INOC 2015 - 7th International Network Optimization Conference}, doi = {10.1016/j.endm.2016.03.040}, pages = {301 -- 308}, abstract = {We study an extension of the shortest path network interdiction problem and present a novel real-world application in this area. We consider the problem of determining optimal locations for toll control stations on the arcs of a transportation network. We handle the fact that drivers can avoid control stations on parallel secondary roads. The problem is formulated as a mixed integer program and solved using Benders decomposition. We present experimental results for the application of our models to German motorways.}, language = {en} } @misc{Schwartz, type = {Master Thesis}, author = {Schwartz, Stephan}, title = {Bilevel Programming to Optimize the Use of Traffic Control Gantries for Toll Enforcement}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-54180}, language = {en} } @misc{BorndoerferSagnolSchwartz, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Schwartz, Stephan}, title = {An Extended Network Interdiction Problem for Optimal Toll Control}, issn = {1438-0064}, doi = {10.1016/j.endm.2016.03.040}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-55405}, abstract = {We study an extension of the shortest path network interdiction problem and present a novel real-world application in this area. We consider the problem of determining optimal locations for toll control stations on the arcs of a transportation network. We handle the fact that drivers can avoid control stations on parallel secondary roads. The problem is formulated as a mixed integer program and solved using Benders decomposition. We present experimental results for the application of our models to German motorways.}, language = {en} } @misc{BorndoerferElijazyferSchwartz, author = {Bornd{\"o}rfer, Ralf and Elijazyfer, Ziena and Schwartz, Stephan}, title = {Approximating Balanced Graph Partitions}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73675}, abstract = {We consider the problem of partitioning a weighted graph into k connected components of similar weight. In particular, we consider the two classical objectives to maximize the lightest part or to minimize the heaviest part. For a partitioning of the vertex set and for both objectives, we give the first known approximation results on general graphs. Specifically, we give a \$\Delta\$-approximation where \$\Delta\$ is the maximum degree of an arbitrary spanning tree of the given graph. Concerning the edge partition case, we even obtain a 2-approximation for the min-max and the max-min problem, by using the claw-freeness of line graphs.}, language = {en} } @inproceedings{SchwartzBorndoerferBalestrieri, author = {Schwartz, Stephan and Bornd{\"o}rfer, Ralf and Balestrieri, Leonardo}, title = {On Finding Subpaths With High Demand}, series = {Operations Research Proceedings 2017}, booktitle = {Operations Research Proceedings 2017}, publisher = {Springer International Publishing}, pages = {355 -- 360}, abstract = {We study the problem of finding subpaths with high demand in a given network that is traversed by several users. The demand of a subpath is the number of users who completely cover this subpath during their trip. Especially with large instances, an efficient algorithm for computing all subpaths' demands is necessary. We introduce a path-graph to prevent multiple generations of the same subpath and give a recursive approach to compute the demands of all subpaths. Our runtime analysis shows, that the presented approach compares very well against the theoretical minimum runtime.}, language = {en} } @misc{SchwartzBalestrieriBorndoerfer, author = {Schwartz, Stephan and Balestrieri, Leonardo and Bornd{\"o}rfer, Ralf}, title = {On Finding Subpaths With High Demand}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69280}, abstract = {We study the problem of finding subpaths with high demand in a given network that is traversed by several users. The demand of a subpath is the number of users who completely cover this subpath during their trip. Especially with large instances, an efficient algorithm for computing all subpaths' demands is necessary. We introduce a path-graph to prevent multiple generations of the same subpath and give a recursive approach to compute the demands of all subpaths. Our runtime analysis shows, that the presented approach compares very well against the theoretical minimum runtime.}, language = {en} } @inproceedings{BorndoerferSchwartzBartz, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Bartz, Gerald}, title = {The Graph Segmentation Problem}, series = {INOC 2017 - 8th International Network Optimization Conference}, volume = {64}, booktitle = {INOC 2017 - 8th International Network Optimization Conference}, pages = {35 -- 44}, abstract = {We investigate a graph theoretical problem arising in the automatic billing of a network toll. Given a network and a family of user paths, we study the graph segmentation problem (GSP) to cover parts of the user paths by a set of disjoint segments. The GSP is shown to be NP-hard but for special cases it can be solved in polynomial time. We also show that the marginal utility of a segment is bounded. Computational results for real-world instances show that in practice the problem is more amenable than the theoretic bounds suggest.}, language = {en} } @inproceedings{BorndoerferCaselIssacetal., author = {Bornd{\"o}rfer, Ralf and Casel, Katrin and Issac, Davis and Niklanovits, Aikaterini and Schwartz, Stephan and Zeif, Ziena}, title = {Connected k-partition of k-connected graphs and c-claw-free graphs}, series = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021}, volume = {207}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.27}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-147200}, pages = {27:1 -- 27:14}, abstract = {A connected partition is a partition of the vertices of a graph into sets that induce connected subgraphs. Such partitions naturally occur in many application areas such as road networks, and image processing. In these settings, it is often desirable to partition into a fixed number of parts of roughly of the same size or weight. The resulting computational problem is called Balanced Connected Partition (BCP). The two classical objectives for BCP are to maximize the weight of the smallest, or minimize the weight of the largest component. We study BCP on c-claw-free graphs, the class of graphs that do not have K_{1,c} as an induced subgraph, and present efficient (c -1)-approximation algorithms for both objectives. In particular, for 3-claw-free graphs, also simply known as claw-free graphs, we obtain a 2-approximation. Due to the claw-freeness of line graphs, this also implies a 2-approximation for the edge-partition version of BCP in general graphs. A harder connected partition problem arises from demanding a connected partition into k parts that have (possibly) heterogeneous target weights w_1, ..., w_k. In the 1970s Győri and Lov{\´a}sz showed that if G is k-connected and the target weights sum to the total size of G, such a partition exists. However, to this day no polynomial algorithm to compute such partitions exists for k > 4. Towards finding such a partition T_1, ..., T_k in k-connected graphs for general k, we show how to efficiently compute connected partitions that at least approximately meet the target weights, subject to the mild assumption that each w_i is greater than the weight of the heaviest vertex. In particular, we give a 3-approximation for both the lower and the upper bounded version i.e. we guarantee that each T_i has weight at least w_i/3 or that each T_i has weight most 3w_i, respectively. Also, we present a both-side bounded version that produces a connected partition where each T_i has size at least w_i/3 and at most max({r, 3})w_i, where r ≥1 is the ratio between the largest and smallest value in w_1, ..., w_k. In particular for the balanced version, i.e. w_1 = w_2 = ... = w_k, this gives a partition with 1/3 w_i ≤ w(T_i) ≤ 3w_i.}, language = {en} } @article{Schwartz, author = {Schwartz, Stephan}, title = {An overview of graph covering and partitioning}, series = {Discrete Mathematics}, volume = {345}, journal = {Discrete Mathematics}, number = {8}, doi = {https://doi.org/10.1016/j.disc.2022.112884}, abstract = {While graph covering is a fundamental and well-studied problem, this field lacks a broad and unified literature review. The holistic overview of graph covering given in this article attempts to close this gap. The focus lies on a characterization and classification of the different problems discussed in the literature. In addition, notable results and common approaches are also included. Whenever appropriate, this review extends to the corresponding partitioning problems.}, language = {en} } @inproceedings{BorndoerferSchwartzSurau, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Surau, William}, title = {Rooted Maximum Weight Connected Subgraphs with Balancing and Capacity Constraints}, series = {Proceedings of the 10th International Network Optimization Conference (INOC), Aachen, Germany, June 7-10, 2022}, booktitle = {Proceedings of the 10th International Network Optimization Conference (INOC), Aachen, Germany, June 7-10, 2022}, doi = {10.48786/inoc.2022.12}, pages = {63 -- 68}, abstract = {Finding connected subgraphs of maximum weight subject to additional constraints on the subgraphs is a common (sub)problem in many applications. In this paper, we study the Maximum Weight Connected Subgraph Problem with a given root node and a lower and upper capacity constraint on the chosen subgraph. In addition, the nodes of the input graph are colored blue and red, and the chosen subgraph is required to be balanced regarding its cumulated blue and red weight. This problem arises as an essential subproblem in district planning applications. We show that the problem is NP-hard and give an integer programming formulation. By exploiting the capacity and balancing condition, we develop a powerful reduction technique that is able to significantly shrink the problem size. In addition, we propose a method to strengthen the LP relaxation of our formulation by identifying conflict pairs, i.e., nodes that cannot be both part of a chosen subgraph. Our computational study confirms the positive impact of the new preprocessing technique and of the proposed conflict cuts.}, language = {en} } @misc{Schwartz, author = {Schwartz, Stephan}, title = {An Overview of Graph Covering and Partitioning}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-79431}, abstract = {While graph covering is a fundamental and well-studied problem, this field lacks a broad and unified literature review. The holistic overview of graph covering given in this article attempts to close this gap. The focus lies on a characterization and classification of the different problems discussed in the literature. In addition, notable results and common approaches are also included. Whenever appropriate, our review extends to the corresponding partioning problems.}, language = {en} } @misc{BorndoerferSchwartzSurau, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Surau, William}, title = {Vertex Covering with Capacitated Trees}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82616}, abstract = {The covering of a graph with (possibly disjoint) connected subgraphs is a fundamental problem in graph theory. In this paper, we study a version to cover a graph's vertices by connected subgraphs subject to lower and upper weight bounds, and propose a column generation approach to dynamically generate feasible and promising subgraphs. Our focus is on the solution of the pricing problem which turns out to be a variant of the NP-hard Maximum Weight Connected Subgraph Problem. We compare different formulations to handle connectivity, and find that a single-commodity flow formulation performs best. This is notable since the respective literature seems to have dismissed this formulation. We improve it to a new coarse-to-fine flow formulation that is theoretically and computationally superior, especially for large instances with many vertices of degree 2 like highway networks, where it provides a speed-up factor of 10 over the non-flow-based formulations. We also propose a preprocessing method that exploits a median property of weight constrained subgraphs, a primal heuristic, and a local search heuristic. In an extensive computational study we evaluate the presented connectivity formulations on different classes of instances, and demonstrate the effectiveness of the proposed enhancements. Their speed-ups essentially multiply to an overall factor of 20. Overall, our approach allows the reliabe solution of instances with several hundreds of nodes in a few minutes. These findings are further corroborated in a comparison to existing districting models on a set of test instances from the literature.}, language = {en} } @inproceedings{BorndoerferSchwartzSurau, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Surau, William}, title = {Finding Minimum Balanced Separators - an Exact Approach}, series = {Operations Research Proceedings 2021}, booktitle = {Operations Research Proceedings 2021}, issn = {1438-0064}, doi = {https://doi.org/10.1007/978-3-031-08623-6_24}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-83138}, pages = {154 -- 159}, abstract = {Balanced separators are node sets that split the graph into size bounded components. They find applications in different theoretical and practical problems. In this paper we discuss how to find a minimum set of balanced separators in node weighted graphs. Our contribution is a new and exact algorithm that solves Minimum Balanced Separators by a sequence of Hitting Set problems. The only other exact method appears to be a mixed-integer program (MIP) for the edge weighted case. We adapt this model to node weighted graphs and compare it to our approach on a set of instances, resembling transit networks. It shows that our algorithm is far superior on almost all test instances.}, language = {en} } @misc{BorndoerferSchwartzSurau, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Surau, William}, title = {Rooted Maximum Weight Connected Subgraphs with Balancing and Capacity Constraints}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-84427}, language = {en} } @article{BorndoerferSchwartzSurau, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Surau, William}, title = {Vertex Covering with Capacitated Trees}, series = {Networks}, volume = {81}, journal = {Networks}, number = {2}, doi = {10.1002/net.22130}, pages = {253 -- 277}, abstract = {The covering of a graph with (possibly disjoint) connected subgraphs is a funda-mental problem in graph theory. In this paper, we study a version to cover a graph'svertices by connected subgraphs subject to lower and upper weight bounds, and pro-pose a column generation approach to dynamically generate feasible and promisingsubgraphs. Our focus is on the solution of the pricing problem which turns out to bea variant of the NP-hard Maximum Weight Connected Subgraph Problem. We com-pare different formulations to handle connectivity, and find that a single-commodityflow formulation performs best. This is notable since the respective literature seemsto have widely dismissed this formulation. We improve it to a new coarse-to-fine flowformulation that is theoretically and computationally superior, especially for largeinstances with many vertices of degree 2 like highway networks, where it provides aspeed-up factor of 5 over the non-flow-based formulations. We also propose a pre-processing method that exploits a median property of weight-constrained subgraphs,a primal heuristic, and a local search heuristic. In an extensive computational studywe evaluate the presented connectivity formulations on different classes of instances,and demonstrate the effectiveness of the proposed enhancements. Their speed-upsessentially multiply to an overall factor of well over 10. Overall, our approach allowsthe reliable solution of instances with several hundreds of vertices in a few min-utes. These findings are further corroborated in a comparison to existing districtingmodels on a set of test instances from the literature}, language = {en} }