4 Presentations

• 
  10:30 AM - 10:55 AM

  Managing Hard and Soft Constraints for Online Shopping

  • Bandar Mohammed, presenter, University of Regina
  • Malek Mouhoub, University of Regina

  We propose a shopping website, based on a constraint solver, taking into account the customer requirements and preferences modeled respectively as a set of hard and soft constraints; and providing him with a list of options corresponding to the best solutions satisfying the hard constraints and maximizing the soft ones.

• 
  10:55 AM - 11:20 AM

  Stochastic Online Bipartite Resource Allocation

  • Antoine Legrain, presenter, MIT
  • Patrick Jaillet, Massachusetts Institute of Technology

  Each time you send a request to Google, there are some advertisements on your page. Google uses your request to choose the best announcers for you. The goal of Google is to maximize its profit. The difficulty of online problems is to make a decision without knowing all the requests. In fact we don't know the future requests but we know the whole historic : we want to use this information. We are trying to use Bayesian Inference to improve the current algorithms.

• 
  11:20 AM - 11:45 AM

  Discovering Potential Collaboration Opportunities Using EMVNS Algorithm

  • Adel Bessadok, presenter, Institut supérieur de gestion de Gabès
  • Pierre Hansen, HEC Montréal

  The communities of scientific researchers all around the world are intensively involved in collaborative networks to ensure they remain competitive. Discovering potential collaboration opportunities is a promising study field in social networks. Conventional Social Network Analysis (SNA) provides us with sufficient information about the already collaborating authors, the frequency of this collaboration, and how many intermediaries exist between them. Clustering techniques and SNA are used to discover hidden communities that would be sensible to collaborate. In fact, each instance can be seen as a random variable generated by a mixture model of K Gaussian possible distributions. To estimate such Gaussian mixture model parameters we often apply the Expectation-Maximization (EM) algorithm.
  However EM is an iterative algorithm and it is very sensitive of the choice of initial values that can severely affect the time to attain convergence of the algorithm and its efficiency in finding an appropriate optimization for constructing proper statistical models of the data. We alleviate this defect by embedding the EM algorithm within the variable Neighborhood Search (VNS) methaheurestic framework.

• 
  11:45 AM - 12:10 PM

  Regret-Based Online Ranking for a Growing Digital Library

  • Erick Delage, presenter, GERAD, HEC Montréal

  We consider the problem of online ranking using “clickthrough” data: queries are sequentially made and answered using a list from which the user selects his favourite item (on Google or an e-commerce site). We present a new ranking algorithm that uses such online data to improve future ranking decisions. We show that its average performance converges to the best rate achievable by a fixed policy selected with the benefit of hindsight. This property can be preserved even if new items are added. Empirical work shows that, while the method can be conservative, a greedy variant outperforms many popular ranking algorithms.