Pasar al contenido principal

OPTIMIZATION OVER NONLINEAR MODEL SPACES: WHERE DISCRETE MEETS CONTINUOUS OPTIMIZATION

PCI2024-155092-2

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de Transferencia y Colaboración
Subprograma Subprograma Estatal para impulsar la Colaboración en y entre los Sectores Público y Privado
Convocatoria Proyectos Programación Conjunta Internacional
Año convocatoria 2024
Plan Estatal 2024-2027 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSIDAD DE LA LAGUNA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 1
Encontrada(s) 1 página(s)

Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Generalized Capacitated Vertex Separator Problem: Models and Algorithms

  • Anglada, Sergio
  • Galé, Carmen
  • Salazar-González, Juan José
Given an undirected graph and two numbers q and b, the Capacitated Vertex Separation Problem (CVSP) looks for a vertex subset of minimum cardinality such that the connected components in the subgraph generated after the vertex removal can be packed into no more than q bins of cardinality at most b. This problem has been studied in graph theory, and most of the success in solving it is due to the hypothesis that the objective function minimizes the number of deleted vertices, that is, each node removal contributes identically to the objective function. In our work, this hypothesis is relaxed so each vertex has a cost and a weight, and the problem aims to minimize the total cost of the removed vertices while the total vertex weight in each bin is within the given capacity b, still limiting the number of bins to at most q. We introduce several mathematical formulations for the new problem, called the Generalized Capacitated Vertex Separator Problem (GCVSP), and analyze the performance of algorithms based on such formulations.