Name
Abstract | ||
|---|---|---|
We show that the problem of finding a perfect matching satisfying a single equality constraint with a 0–1 coefficients in an n × n incomplete bipartite graph, polynomially reduces to a special case of the same peoblem called the partitioned case. Finding a solution matching for the partitioned case in the incomlpete bipartite graph, is equivalent to minimizing a partial sum of the variables over
<img src="/fulltext-image.asp?format=htmlnonpaginated&src=H5713328W8264747_html\10878_2004_Article_268450_TeX2GIFIE1.gif" border="0" alt="
$$Q_{n_{1,} n_2 }^{n,r_1 } $$
" /> = the convex hull of incidence vectors of solution matchings for the partitioned case in the complete bipartite graph. An important strategy to solve this minimization problem is to develop a polyhedral characterization of
<img src="/fulltext-image.asp?format=htmlnonpaginated&src=H5713328W8264747_html\10878_2004_Article_268450_TeX2GIFIE2.gif" border="0" alt="
$$Q_{n_{1,} n_2 }^{n,r_1 } $$
" />. Towards this effort, we present two large classes of valid inequalities for
<img src="/fulltext-image.asp?format=htmlnonpaginated&src=H5713328W8264747_html\10878_2004_Article_268450_TeX2GIFIE3.gif" border="0" alt="
$$Q_{n_{1,} n_2 }^{n,r_1 } $$
" />, which are proved to be facet inducing using a facet lifting scheme. |
Year | DOI | Venue |
|---|---|---|
2000 | https://doi.org/10.1023/A:1009878328812 | Journal of Combinatorial Optimization |
Keywords | DocType | Volume |
constrained assignment problem,integer hull,facet inducing inequalities,facet lifting scheme | Journal | 4 |
Issue | ISSN | Citations |
3 | 1382-6905 | 3 |
PageRank | References | Authors |
0.58 | 2 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Abdo Y. Alfakih | 1 | 103 | 11.35 |
| Tongnyoul Yi | 2 | 22 | 2.14 |
| Katta G. Murty | 3 | 602 | 95.15 |