Time table of all LIRMM seminars

Open problems session of AlGCo-team

Most classical combinatorial optimization problems on graphs use weights without uncertainty. Typically, each edge is associated with an integer or a probability, and computing a solution means finding a subgraph that satisfies a certain property while minimizing/maximizing the sum of weights/product of probabilities. However, this type of modeling can sometimes be insufficient when it is difficult to determine the weights from real data. For example, if we want to group members of a parliament according to their tendency to vote together, we can associate two members of the parliament with an edge and a
probability that they will vote together. However, it can be difficult to establish this probability if the number of votes for which these two members were present together is small. One solution to this is to associate an interval [l_e, u_e] with each edge e, which will model the imprecision of this data. One possible realization is a weighted graph, where for each edge e, we associate a weight p_e such that l_e <= p_e <= u_e. A solution can therefore be optimal in one realization but not in another. One of the objectives will then be to enumerate all solutions S such that there exists a realization where S is
optimal. Another question is to determine which edges are possible (i.e., appear in at least one solution) or necessary (i.e., appear in all solutions). In this presentation, we will focus on two problems: K-partition with imprecise probabilities and Minimum weight spanning tree with imprecise weights.