Loading...
Please wait, while we are loading the content...
Similar Documents
The Clique Partition Problem with Minimum Clique Size Requirement 1
| Content Provider | Semantic Scholar |
|---|---|
| Author | Ji, Xiaoyun Mitchell, John E. |
| Copyright Year | 2005 |
| Abstract | Given a complete graph Kn = (V;E), with edge weight ce on each edge, we consider the problem of partitioning the vertices of graph Kn into subcliques that each have at least S vertices, so as to minimize the total weight of the edges that have both endpoints in the same subclique. It is an extension of the classic Clique Partition Problem that can be well solved using triangle inequalities, but the additional size requirement here makes it much harder to solve. The previously known inequalities are not good enough to solve even a small size problem within a reasonable amount of time. In this paper, we’ll discuss the polyhedral structure and introduce new kinds of cutting planes: pigeon cutting planes and ∞ower cutting planes. We will report the computational results with a branch-and-cut algorithm conflrming the strength of these new cutting planes. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.rpi.edu/~mitchj/papers/cppmin.pdf |
| Alternate Webpage(s) | http://homepages.rpi.edu/~mitchj/papers/cppmin.pdf |
| Alternate Webpage(s) | http://www.optimization-online.org/DB_FILE/2005/05/1125.pdf |
| Alternate Webpage(s) | http://eaton.math.rpi.edu/faculty/Mitchell/papers/cppmin.pdf |
| Alternate Webpage(s) | http://www.rensselaer.edu/~mitchj/papers/cppmin.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
