Bottleneck subset-type restricted matching problems
- PDF / 297,225 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 63 Downloads / 254 Views
Bottleneck subset-type restricted matching problems Oleg Duginov1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We introduce two problems related to finding in a weighted complete bipartite graph a special matching such that the maximum weight of its some subsets is minimal. We discuss their applications and show the strong NP-hardness of both problems. We show that one problem cannot be approximated in polynomial time within a factor of less than 2 and another problem cannot be approximated in polynomial time within a factor of α(n), where α(n) is an arbitrary polynomial-time computable function, unless P = NP. Keywords Matching · Edge weighted complete bipartite graph · Computational complexity · Inapproximability
1 Introduction We consider two bottleneck subset-type combinatorial optimisation problems that generalise the well-known Min- Max Weighted Matching problem (Barketau et al. 2015): Given an edge weighted complete bipartite graph with a partition of its part into non-empty and disjoint subsets, the problem is to find a maximal matching of this graph such that the maximum sum of weights of those edges of the matching that cover vertices of a subset from the partition is minimal. We establish a connection of the first considered problem with a problem of planning container transportation in railroad transshipment yards [for a survey on operational planning in railroad transshipment yards, we refer to Boysen et al. (2013)] and a connection of the second considered problem with an operational problem that arose out of a real-time factory automation [for general information on operational planning in production lines, we refer to Bozma and Kalalioˇglu (2012)]. We study questions of the computational complexity and the approximation complexity of the considered problems.
B 1
Oleg Duginov [email protected] Belarusian State University, Nezavisimosti Ave., 4, 220030 Minsk, Belarus
123
Journal of Combinatorial Optimization
2 Problem definitions and applications We use standard graph-theoretic notations and terminology from the Diestel’s book (2017) and consider only finite undirected graphs G = (V , E) with vertex set V = V (G) and edge set E = E(G) without multiple edges and loops. A graph G = (V , E) is bipartite if its vertex set can be partitioned into two nonempty disjoint subsets V = U ∪ W so that each edge of the graph has its ends in different sets U and W . For such graph we write G = (U ∪ W , E). Subsets U and W are called parts of the graph G. If wherein |U | = |W |, then the bipartite graph G is balanced bipartite. If each vertex of the part U is adjacent to each vertex of the part W , then the bipartite graph G is complete bipartite. A subset M of edge set E(G) of a graph G is a matching if the set M does not contain adjacent edges, i.e., edges that have a common end vertex. We say a vertex v ∈ V (G) is covered by the matching M if the vertex v is incident with an edge of the matching M. A matching M of the graph G is perfect if all vertices of the graph G are cove
Data Loading...
