Algorithmic and structural aspects of Covering and Packing problems on graphs
Solution-phase processing of two-dimensional nanomaterials for printed and flexibl...
| Full text | |
| Author(s): |
Miyazawa, Flavio K.
;
Moura, Phablo F. S.
;
Ota, Matheus J.
;
Wakabayashi, Yoshiko
Total Authors: 4
|
| Document type: | Journal article |
| Source: | European Journal of Operational Research; v. 293, n. 3, p. 11-pg., 2021-04-24. |
| Abstract | |
This work addresses the balanced connected k-partition problem (BCPk), which is formally defined as follows. Given a connected graph G = (V, E) with nonnegative weights on the vertices, find a partition {V-i}(i=1)(k) of V such that each class V-i induces a connected subgraph of G, and the weight of a class with the minimum weight is as large as possible. This problem, known to be NP-hard, has been largely investigated under different approaches and perspectives: exact algorithms, approximation algorithms for some values of k or special classes of graphs, and inapproximability results. On the practical side, BCPk is used to model many applications arising in image processing, cluster analysis, operating systems and robotics. We propose three linear programming formulations for BCPk. The first one contains only binary variables and a potentially large number of constraints that can be separated in polynomial time in the corresponding linear relaxation. We introduce new valid inequalities and design polynomial-time separation algorithms for them. The other two formulations are based on flows and have a polynomial number of constraints and variables. Our computational experiments show that the exact algorithms based on the proposed formulations outperform the other exact approaches presented in the literature. (C) 2021 Elsevier B.V. All rights reserved. (AU) | |
| FAPESP's process: | 16/21250-3 - Algorithmic and structural aspects of Covering and Packing problems on graphs |
| Grantee: | Phablo Fernando Soares Moura |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |
| FAPESP's process: | 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points |
| Grantee: | Flávio Keidi Miyazawa |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 17/22611-2 - Algorithmic and structural aspects of covering and packing problems on graphs |
| Grantee: | Phablo Fernando Soares Moura |
| Support Opportunities: | Scholarships abroad - Research Internship - Post-doctor |
| FAPESP's process: | 16/01860-1 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings |
| Grantee: | Reinaldo Morabito Neto |
| Support Opportunities: | Research Projects - Thematic Grants |