Refine
Document Type
- ZIB-Report (8) (remove)
Language
- English (8)
Has Fulltext
- yes (8)
Is part of the Bibliography
- no (8)
Keywords
- Graph Covering (1)
- Graph Partitioning (1)
- combinatorial optimization (1)
- graph segmentation (1)
- network interdiction (1)
- toll billing (1)
Institute
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.
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.
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.
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.
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.
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.
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.