SPOC18 "Machine Learning, Networks and Combinatorial Optimization"

Onglets principaux

Date: 
Vendredi, 14 décembre, 2018

18ème séminaire du groupe POC

Le VENDREDI 14 DECEMBRE 2018

Au laboratoire LAMSADE de l’Université Dauphine
Place du Maréchal de Lattre de Tassigny
75017 PARIS Cedex

Pour l'accès voiture et transport en commun

Les salles seront indiquées ultérieurement

Sur le thème

"Machine Learning, Networks
and Combinatorial Optimization"

Ce séminaire est libre d'accès mais merci de vous inscrire en utilisant l'onglet situé en-haut de page pour faciliter l'organisation.
Cliquer ici pour voir la liste des inscrits

It will take place at December 14, 2018 from 9am to 5pm.

----

The list of speakers:

- Immanuel Bomze, University of Vienna

- Yann Chevaleyre, Paris-Dauphine University

- Bistra Dilkina, University of Southern California

- Bernard Gendron, University of Montreal, Canada

- Marco Lübbecke, RWTH Aachen

- Enrico Malaguti, University of Bologna

- Michele Monaci, University of Bologna

 

Please find below some of the abstracts, the missing abstracts will be given as soon as possible.

 

Robust clustering in social networks
Immanuel Bomze, University of Vienna
(joint work with Michael Kahr and Markus Leitner, all University of Vienna)

During the last decades the importance of considering data uncertainty in optimization problems has become increasingly apparent, since small
fluctuations of input data may lead to comparably bad decisions in many
practical problems when uncertainty is ignored. If the probability
distribution of the uncertain data is not known (or cannot be estimated with sufficient accuracy), a common technique is to estimate bounds on the uncertain data (i.e., define uncertainty sets) and to identify optimal solutions that are robust against data fluctuations within these bounds. This approach leads to the robust optimization paradigm that allows to consider uncertain objectives and constraints.

Optimization problems where only the objective is uncertain arise, for instance, prominently in the analysis of social networks.
This stems from the fact that the strength of social ties (i.e., the amount of influence individuals exert on each other) or the willingness of individuals to adopt and share information can, for example, only be roughly estimated based on observations.

A fundamental problem arising in social network analysis regards the identification of communities (e.g., work groups, interest groups), which can be modeled as a Dominant Set Clustering Problem which in turn leads to a Standard Quadratic Optimization Problems (StQP). Here the link strengths enter the objective while the constraints are
familiar probability constraints, so that they can be considered certain.

Hence we investigate data uncertainty in the objective function of StQPs, considering different uncertainty sets, and derive implications for the complexity of robust variants of the corresponding deterministic counterparts. We can show that considering data uncertainty in a StQP results in another StQP of the same complexity if ellipsoidal, spherical or boxed uncertainty sets are assumed. Moreover we discuss implications when considering polyhedral uncertainty sets, and derive rigorous bounds for this case.

------

Optimization in Social Networks
Michele Monaci, University of Bologna

A large number of Online Social Networks (OSNs) are nowadays available on the web, providing platforms for fast information diffusion and exchange among their users.
The great popularity and expansion of OSNs have drastically changed the landscape of communications in the cyber space. In some cases, OSNs represent one of the major news sources as well as the most effective channels for viral marketing. Indeed, many people have integrated popular online social sites into their everyday lives, and rely on them for information sharing. While this can be exploited for marking purposes, OSNs are also particularly prone to generate and spread misinformation, which can have pernicious influences on individuals or society. This raises a number of relevant problems to be dealt with by different actors that operate on a social network. In this talk we describe some optimization problems that are relevant in the study of a social network. 
Motivated from viral marketing, we introduce the Generalized Least Cost Influence Problem (GLCIP), in which one is asked to identify key players in an OSN so that a certain number of users in the network are reached.  We present a model that is more general than other models from the literature, and hence more likely to be suitable for real-world applications.
We introduce a mathematical formulation based on the concept of activation functions, and valid inequalities that can be used to strengthen the formulation.
Exact and heuristic solution methods are developed and compared for the problem on a large benchmark of instances. Our computational results show that the proposed approach is a viable way to solve the GLCIP and that it outperforms the state-of-the-art approaches for the previously considered relevant special cases of the GLCIP.
 
-----
 
Design and Control of a Public Contract with an approach combining game theory and optimization.
Enrico Malaguti, University of Bologna
 
In all modern economies, it is common for governments and local authorities to regularly outsource services to the market. Depending on the nature of the object or service to be purchased, the transaction can be performed as a one-time activity or give rise to a long-term relationship with the provider. This talk is about the latter case, where a public entity, denoted as Agency, outsources a service to be provided to the citizens through a contract with a Provider. We address the informative asymmetry between the two players, Agency and Provider, from a game theoretical perspective, and propose a control strategy based on the solution of an optimization problem. We show that an improved control results in an incentive, for the Provider, to provide reliable information about its own performance. We report and discuss a case study arising in local public transportation.
 

-----

The organizers,
Ivana Ljubic
Fabio Furini