Vítor Gomes Chagas
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Vítor Gomes Chagas has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- Greis Yvet Oropeza Quesquén
Universidade Estadual de Campinas
3 shared publications - Samuel Plaça de Paula
Universidade Estadual de Campinas
3 shared publications - Ueverton dos Santos Souza
Fluminense Federal University, Niteroi, Brazil
3 shared publications - Flavio Keidi Miyazawa
University of Campinas
2 shared publications - Lucas de Oliveira Silva
Universidade Estadual de Campinas
2 shared publications - Manuel Iori
DISMI University of Modena and Reggio Emilia Reggio Emilia Italy
2 shared publications
Latest Publications
- Open Access
- 28 August 2026
- Published by Elsevier in SSRN Electronic Journal
Realizing Graphs with Cut Constraints
Given a finite, non-increasing degree sequence, the Graph Realization problem asks whether a labeled simple graph realizes it. We study its generalization with prescribed sizes for selected nontrivial edge cuts. Let w be the maximum size of a constrained vertex set. We prove polynomial-time solvability when w <= 3 and any two constrained triples intersect in at most one vertex. Without that intersection condition, the problem is NP-complete already for w = 3, even when every required degree is 1 or 3. It is also NP-complete for w = 4 when all larger constrained sets are pairwise disjoint, and every required degree equals 1. Finally, for w <= 6, we prove NP-completeness even when the realization must be a subgraph of a union of 6-cycles. These results establish sharp complexity boundaries governed by constraint width and intersection structure.
- 28 August 2026
- Published by Elsevier in SSRN Electronic Journal
Open AccessRealizing Graphs with Cut Constraints
Given a finite, non-increasing degree sequence, the Graph Realization problem asks whether a labeled simple graph realizes it. We study its generalization with prescribed sizes for selected nontrivial edge cuts. Let w be the maximum size of a constrained vertex set. We prove polynomial-time solvability when w <= 3 and any two constrained triples intersect in at most one vertex. Without that intersection condition, the problem is NP-complete already for w = 3, even when every required degree is 1 or 3. It is also NP-complete for w = 4 when all larger constrained sets are pairwise disjoint, and every required degree equals 1. Finally, for w <= 6, we prove NP-completeness even when the realization must be a subgraph of a union of 6-cycles. These results establish sharp complexity boundaries governed by constraint width and intersection structure.
- 27 July 2026
- Published by Wiley in International Transactions in Operational Research
The quadratic bin packing problem: exact formulations and algorithms
In this article, we introduce and study the quadratic bin packing problem (QBPP), which generalizes the classical bin packing problem by introducing a fixed cost for each used bin and a pairwise cost (or profit) incurred whenever two items are packed together. Beyond its theoretical relevance, the QBPP is of practical interest due to its numerous real‐world applications, mainly related to cluster analysis. To address the QBPP, we propose three compact mixed‐integer linear programming (MILP) formulations, along with a set‐partitioning formulation. For each compact model, we present an enhanced version with a strengthened continuous relaxation, while, for the set‐partitioning formulation, we develop a tailored branch‐and‐price algorithm. Computational experiments on benchmark instances demonstrated that, while the enhanced compact formulations can be effectively solved by a standard MILP solver for small‐sized instances, the branch‐and‐price approach delivered superior performance overall, especially on larger and more challenging instances.
- 27 July 2026
- Published by Wiley in International Transactions in Operational Research
The quadratic bin packing problem: exact formulations and algorithms
In this article, we introduce and study the quadratic bin packing problem (QBPP), which generalizes the classical bin packing problem by introducing a fixed cost for each used bin and a pairwise cost (or profit) incurred whenever two items are packed together. Beyond its theoretical relevance, the QBPP is of practical interest due to its numerous real‐world applications, mainly related to cluster analysis. To address the QBPP, we propose three compact mixed‐integer linear programming (MILP) formulations, along with a set‐partitioning formulation. For each compact model, we present an enhanced version with a strengthened continuous relaxation, while, for the set‐partitioning formulation, we develop a tailored branch‐and‐price algorithm. Computational experiments on benchmark instances demonstrated that, while the enhanced compact formulations can be effectively solved by a standard MILP solver for small‐sized instances, the branch‐and‐price approach delivered superior performance overall, especially on larger and more challenging instances.
- Open Access
Realizing Graphs with Cut Constraints
Given a finite non-decreasing sequence $d=(d_1,\ldots,d_n)$ of natural numbers, the Graph Realization problem asks whether $d$ is a graphic sequence, i.e., there exists a labeled simple graph such that $(d_1,\ldots,d_n)$ is the degree sequence of this graph. Such a problem can be solved in polynomial time due to the Erdős and Gallai characterization of graphic sequences. Since vertex degree is the size of a trivial edge cut, we consider a natural generalization of Graph Realization, where we are given a finite sequence $d=(d_1,\ldots,d_n)$ of natural numbers (representing the trivial edge cut sizes) and a list of nontrivial cut constraints $\mathcal{L}$ composed of pairs $(S_j,\ell_j)$ where $S_j\subset \{v_1,\ldots,v_n\}$, and $\ell_j$ is a natural number. In such a problem, we are asked whether there is a simple graph with vertex set $V=\{v_1,\ldots,v_n\}$ such that $v_i$ has degree $d_i$ and $\partial(S_j)$ is an edge cut of size $\ell_j$, for each $(S_j,\ell_j)\in \mathcal{L}$. We show that such a problem is polynomial-time solvable whenever each $S_j$ has size at most three. Conversely, assuming P $\neq$ NP, we prove that it cannot be solved in polynomial time when $\mathcal{L}$ contains pairs with sets of size four, and our hardness result holds even assuming that each $d_i$ of $d$ equals $1$.Open AccessRealizing Graphs with Cut Constraints
Given a finite non-decreasing sequence $d=(d_1,\ldots,d_n)$ of natural numbers, the Graph Realization problem asks whether $d$ is a graphic sequence, i.e., there exists a labeled simple graph such that $(d_1,\ldots,d_n)$ is the degree sequence of this graph. Such a problem can be solved in polynomial time due to the Erdős and Gallai characterization of graphic sequences. Since vertex degree is the size of a trivial edge cut, we consider a natural generalization of Graph Realization, where we are given a finite sequence $d=(d_1,\ldots,d_n)$ of natural numbers (representing the trivial edge cut sizes) and a list of nontrivial cut constraints $\mathcal{L}$ composed of pairs $(S_j,\ell_j)$ where $S_j\subset \{v_1,\ldots,v_n\}$, and $\ell_j$ is a natural number. In such a problem, we are asked whether there is a simple graph with vertex set $V=\{v_1,\ldots,v_n\}$ such that $v_i$ has degree $d_i$ and $\partial(S_j)$ is an edge cut of size $\ell_j$, for each $(S_j,\ell_j)\in \mathcal{L}$. We show that such a problem is polynomial-time solvable whenever each $S_j$ has size at most three. Conversely, assuming P $\neq$ NP, we prove that it cannot be solved in polynomial time when $\mathcal{L}$ contains pairs with sets of size four, and our hardness result holds even assuming that each $d_i$ of $d$ equals $1$. - 22 December 2023
- Published by Springer Nature
- p. 145-159
Approximation Schemes Under Resource Augmentation for Knapsack and Packing Problems of Hyperspheres and Other Shapes
- 22 December 2023
- Published by Springer Nature
- p. 145-159
Approximation Schemes Under Resource Augmentation for Knapsack and Packing Problems of Hyperspheres and Other Shapes
- Open Access
- 21 November 2023
- Published by Universidade Estadual de Campinas
Exact algorithms for the quadratic bin packing problem
- 21 November 2023
- Published by Universidade Estadual de Campinas
Open AccessExact algorithms for the quadratic bin packing problem
- 30 June 2020
- Published by Sociedade Brasileira de Computação
- p. 97-100
Formulação de fluxo em arcos para problemas de agrupamento capacitado
Neste trabalho, apresentamos uma formulação baseada em modelos de fluxo em arcos, originalmente projetados para problemas de empacotamento, e agora aplicada a problemas de agrupamento. Consideramos os problemas de Correlation Clustering e Graph Partitioning com pesos nos vértices e custo associado a cada cluster utilizado. Discutimos as vantagens de tal formulação comparada a outras estratégias presentes na literatura.
- 30 June 2020
- Published by Sociedade Brasileira de Computação
- p. 97-100
Formulação de fluxo em arcos para problemas de agrupamento capacitado
Neste trabalho, apresentamos uma formulação baseada em modelos de fluxo em arcos, originalmente projetados para problemas de empacotamento, e agora aplicada a problemas de agrupamento. Consideramos os problemas de Correlation Clustering e Graph Partitioning com pesos nos vértices e custo associado a cada cluster utilizado. Discutimos as vantagens de tal formulação comparada a outras estratégias presentes na literatura.