Minimum transversals of maximum matchings as approximate solutions to the bisection problem (Q1913329): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Approximation algorithms for multi-dimensional assignment problems with decomposable costs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A class of bounded approximation algorithms for graph partitioning / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3997942 / rank | |||
Normal rank |
Latest revision as of 12:07, 24 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimum transversals of maximum matchings as approximate solutions to the bisection problem |
scientific article |
Statements
Minimum transversals of maximum matchings as approximate solutions to the bisection problem (English)
0 references
1995
0 references
The bisection problem requires to find a partition of the vertex set of a given complete graph with \(2m\) vertices and weighted edges into two parts of size \(m\), optimizing the sum of the (nonnegative) weights of the internal edges. The problem is NP-complete. If the objective function is to be maximized and the edges satisfy the triangle inequality, approximate solutions are obtained by first determining a maximum weight matching and then selecting a bisection that does not cut any of the matching edges---a heuristic which is poor if the objective function is to be minimized. The paper proves the following theorem: Given a weighted complete graph satisfying the relaxed triangle inequality \(c(u,v)\leq\tau\cdot(c(u,w)+c(w,v))\) for all \(u,v,w\in X\) for some \(\tau\geq 1\), the minimum weight \(c_{\text{trans}}\) of (``\(M\)-transversal'') bisections cutting all edges of a given maximum weight perfect matching \(M\) is bounded from above in terms of the weight \(c_{\min}\) of an overall minimum bisection as follows: \(c_{\text{trans}}\leq(\tau^2+{1\over 2}\tau+{1\over 2})\cdot c_{\min}\). In this inequality, for each fixed \(\tau\geq 1\), the factor \(\tau^2+{1\over 2}\tau+{1\over 2}\) is asymptotically best possible.
0 references
transversals
0 references
bisection problem
0 references
matching
0 references
0 references
0 references