3 présentations

• 
  16h45 - 17h07

  A polytime preprocess algorithm for the maximum independent set problem

  • Samuel Kroger, prés.,
  • Hamidreza Validi, Texas Tech University
  • Illya Hicks, Rice University

  The maximum independent set (MIS) seeks to find a subset of vertices with the maximum size such that no pair of its vertices are adjacent. This paper develops a recursive fixing procedure that generalizes the existing polytime algorithm to solve the maximum independent set problem on chordal graphs, which admit simplicial orderings. We prove that the generalized fixing procedure is safe; i.e., it does not remove all optimal solutions of the MIS problem from the solution space. Our computational results show that the proposed recursive fixing algorithm, along with the basic mixed integer programming (MIP) of the MIS, outperforms the pure MIP formulation of the problem. Our codes, data, and results are available on GitHub.

• 
  17h07 - 17h29

  Induced conflict formulations for second-order k-clubs

  • Yajun Lu, prés.,
  • Balabhaskar Balasundaram, Oklahoma State University

  A k-club is a clique relaxation defined as a vertex subset inducing a subgraph with diameter at most k, originally introduced to model cohesive subgroups in social networks and tightly knit clusters in graph-based data mining. However, k-clubs can be fragile for k ≥ 2, potentially creating subgraphs with low connectivity, such as those containing a cut vertex. This observation led various authors to introduce second-order k-clubs that require additional properties that endow the induced subgraph with fault tolerance and/or increased vertex connectivity. This talk introduces new induced conflict formulations for several second-order k-club models, offering the very first integer programming formulations for some of them. We compare the new formulations against existing formulations from the recent literature where available, investigate the effectiveness of the proposed formulation through theoretical and empirical means, and report encouraging computational evidence that this approach is favorable over existing approaches for challenging optimization problem instances.

• 
  17h29 - 17h51

  From nodal to group centrality: an overview of the state-of-the-art and future directions

  • Chrysafis Vogiatzis, prés., University of Illinois Urbana-Champaign
  • Mustafa Can Camur, Amazon

  Centrality is probably the most well-studied network analysis metric out there. Over the years, centrality has been used as a proxy of importance in settings as diverse as transportation, biological, and social networks. In the last decade, we are though observing a move away from nodal metrics, which assign importance to a node alone, and towards group metrics, which consider groups. It is often desirable for these groups to induce specific structures or motifs. In this talk, we will present an overview of the state-of-the-art and its fast evolution within the operations research and network optimization communities. Then, we will talk about future, exciting we hope, directions, including the limited availability of stochastic metrics, new structures, and emerging applications that can take advantage of the proposed metrics.