Name
Abstract | ||
|---|---|---|
The purpose of this paper is to characterize all matroids M that satisfy the following minimax relation: for any nonnegative integral weight function w defined on E(M), $${\begin{aligned} & {\rm Maximum} \{ k: M\,{\rm has}\,k\,{\rm circuits\,(repetition\,allowed)\,such\,that\,each\,element}\,e\,{\rm of}\,M\\ &\quad\quad\quad\quad\quad {\rm is\,used\,at\,most}\,2w(e)\,{\rm times\,by\,these\,circuits}\}\\ =\,&{\rm Minimum}\left\{\sum\nolimits_{x\in X} w(x): X\,{\rm is\,a\,collection\,of\,elements\,(repetition\,allowed)\,of}\,M \right.\\ &\quad \quad\quad\quad\quad\left.\vphantom{\sum_{x\in X}} {\rm such\,that\,every\,circuit\,in}\,M\,{\rm meets}\,X\,{\rm at\,least\,twice}\right\}. \end{aligned}}$$ Our characterization contains a complete solution to a research problem on 2-edge-connected subgraph polyhedra posed by Cornuéjols, Fonlupt, and Naddef in 1985, which was independently solved by Vandenbussche and Nemhauser in Vandenbussche and Nemhauser (J. Comb. Optim. 9:357–379, 2005). |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/s10107-007-0205-6 | Math. Program. |
Keywords | Field | DocType |
traveling salesman problem.,rm time,matroid,rm circuit,2-edge-connected subgraph polyhedron,following minimax relation,nonnegative integral weight function,polyhedron,rm minimum,complete solution,matroids m,j. comb,total dual integrality,circuit,rm maximum,traveling salesman problem | Matroid,Discrete mathematics,Mathematical optimization,Combinatorics,Total dual integrality,Mathematics,Minimax problem | Journal |
Volume | Issue | ISSN |
119 | 1 | 1436-4646 |
Citations | PageRank | References |
4 | 0.44 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guoli Ding | 1 | 444 | 51.58 |
| Wenan Zang | 2 | 305 | 39.19 |