Program

Schedule

4 March (at the Institute of Mathematics, building A5, address: 18 Hoang Quoc Viet, Hanoi):

5 March (at the Institute of Mathematics, address: 18 Hoang Quoc Viet, Hà Nội):

6 March: excursion to Ninh Binh. Departure at 7h30 from the Army Guest House Hotel, address: 33 Pham Ngu Lao, Hanoi.

7 March (at the Institute for Advanced Study in Mathematics, address: 1 Dai Co Viet, Hanoi)

Abstracts:

  • Guiseppe Italiano, Dynamic Graph Algorithms

The design of dynamic graph algorithms is one of the classic areas in theoretical computer science. In this setting, the input of a graph problem is being changed via a sequence of updates, such as edge insertions and deletions. A dynamic graph algorithm aims at maintaining a given property P on a graph subject to dynamic updates. A dynamic graph algorithm should process queries on property P quickly, and perform update operations faster than recomputing from scratch, as carried out by the fastest static algorithm. We say that an algorithm is fully dynamic if it can handle both edge insertions and edge deletions. A partially dynamic algorithm can handle either edge insertions or edge deletions, but not both: we say that it is incremental if it supports insertions only, and decremental if it supports deletions only. This course will consist of two parts. The goal of the first part is to present the main algorithmic techniques used to solve dynamic problems on undirected graphs. To illustrate those techniques, we will focus particularly on dynamic minimum spanning trees and on connectivity problems. In the second part we deal with dynamic problems on directed graphs, and we investigate as paradigmatic problems the dynamic maintenance of transitive closure and shortest paths. Interestingly enough, dynamic problems on directed graphs seem much harder to solve than their counterparts on undirected graphs, and require completely different techniques and tools.


  • Frédéric Meunier, Envy-free division of a cake: the poisoned case, and other variations

Given a cake (identified with the interval [0,1]) and players with different tastes, the envy-free cake-cutting problem asks for a partition of the cake into connected pieces so that it is possible to assign the pieces to the players without making any of them jealous. The Stromquist-Woodall theorem ensures the existence of such an envy-free division under mild conditions. Recently, Segal-Halevi asked whether these conditions could be even further relaxed by allowing that some players dislike the cake (e.g., they know the cake has been poisoned). In the traditional setting, all players are "hungry", and always prefer to get something instead of nothing. We provide a partial answer to that question and propose also other extensions, e.g., when suddenly one player disappears.

Based on joint work with Florian Frick, Kelsey Houston-Edwards, Francis E. Su, Shira Zerbib.


  • Ha Minh Hoang, On some selected arc routing problems in dynamic environments

In this talk, I will present three arc routing problems in which travel and/or service times are not deterministic but variable. In the first problem called stochastic arc routing problem, the travel and service times are stochastic variables. The second problem is a robust arc routing problem in which data are missing and only lower and upper bounds on the travel and service times are known. The last problem deals with the case where travel and service times are time dependent, i.e. they depend on arrival times at an edge. For each problem, we introduce solution methods, experimental results and conclusions.


  • Vincent Chau, Weighted Throughput Maximization with Calibrations

The scheduling problem with calibrations was introduced by Bender et al. (SPAA 2013). In sensitive applications, machines need to be periodically calibrated to ensure that they run correctly. Formally, we are given a set of n jobs with release times, deadlines and weights. Calibrating a machine requires a cost and remains calibrated for a period of T time units, after which it must be recalibrated before it can resume running jobs. Moreover, we are given a budget of K calibrations. The objective is to schedule a maximum (weighted) number of jobs on m identical machines with at most K calibrations.

In this talk, we present constant approximation algorithms for unit processing time as well as for arbitrary processing time case.


  • Kevin Perrot, Complexity and Fixed Points in Boolean Networks

A Boolean network (BN) with n components is a discrete dynamical system described by the successive iterations of a function f : {0,1}^n → {0,1}^n . This model finds applications in biology, where fixed points play a central role. For example in genetic regulation they correspond to cell phenotypes. In this context, experiments reveal the existence of positive or negative influences among components: component i has a positive (resp. negative) influence on component j, meaning that j tends to mimic (resp. negate) i. The digraph of influences is called signed interaction digraph (SID), and one SID may correspond to multiple BNs. We propose a new perspective on the well-established study of fixed points in BNs. Biologists discover the SID of a BN they do not know, and may ask: given that SID, can it corresponds to a BN having at least k fixed points? Depending on the input, this problem is in P or complete for NP, NP^#P or NEXPTIME.


  • Nguyen Viet Hung, Fair combinatorial optimization: formulations and algorithms

In first part of this talk, the modeling the notion of "fairness" in combinatorial optimization is reviewed. As this results in rather non convex and non linear models, some linearization methods to derive MIP formulations are described in the second part. At last, special purpose algorithms for solving these MIPs are discussed and analyzed with numerical results.


  • Nguyen Kim Thang, Submodular Maximization

Submodular and diminishing-returns (DR) submodular optimization are important optimization problems with many real-world applications in machine learning, economics and communication systems. Moreover, DR-submodular optimization captures a subclass of non-convex optimization that provides both practical and theoretical guarantees.

In this talk, we present algorithms with performance guarantees for the fundamental problems of maximizing non-monotone submodular and DR-submodular functions over convex sets in offline, online and bandit settings.


  • Emtiyaz Khan, Bayesian deep learning

I will give an overview of the new area of Bayesian deep learning which combines ideas from optimization and Bayesian inference to improve deep learning. I will mostly focus on fundamental ideas from Bayesian inference first, and then discuss how optimization can be used to scale approximate Bayesian inference to deep learning applications. I will discuss some of my recent work on using information-geometry to improve existing methods. Overall, my hope is to demonstrate significance of the recent progress and motivate researchers to work on this new exciting area of Bayesian deep learning.


  • Yannis Manoussakis, Tropical subgraphs in vertex-colored graphs

In this talk we deal with tropical subgraphs in vertex-colored graphs, a concept with direct applications to the web graph and in bioinformatics (Multiple Sequence Alignment Pipeline or for multiple protein-protein Interaction networks). More precisely, given a vertex-colored graph, a tropical subgraph (induced or otherwise) is defined to be a subgraph where each color of the initial graph appears at least once. Notice that in a tropical subgraph, adjacent vertices can receive the same color, thus a tropical subgraph may not be properly colored. Potentially, many graph invariants, such as the domination number, the vertex cover number, maximum matchings, independent sets, connected components, shortest paths, etc. can be studied in their tropical version. This notion is close to, but somewhat different from the colorful concept (all colors of the subgraph are different) used for paths and elsewhere in vertex-colored graphs. It is also related to the concepts of color patterns (the subgraph has fixed color patterns) used in bio-informatics. Here we explain some results on our ongoing work on tropical dominating sets, vertex covers, connected subgraphs, maximum matchings and tropical homomorphisms.


  • Nguyen Ngoc Doanh, Hybrid Modeling for Optimization Problem of Municipal Solid Waste Transportation

The amount of municipal solid waste (MSW) has been increasing steadily over the last decade by reason of population rising and waste generation rate. In most of the urban areas, disposal sites are usually located outside of the urban areas due to the scarcity of land. There is no fixed route map for transporta- tion. The current waste collection and transportation are already overloaded arising from the lack of facil- ities and insufficient resources. In this paper, a model for optimizing municipal solid waste collection will be proposed. Firstly, the optimized plan is developed in a static context, and then it is integrated into a dynamic context using multi-agent based modelling and simulation. A case study related to Hagiang City, Vietnam, is presented to show the efficiency of the proposed model. From the optimized results, it has been found that the cost of the MSW collection is reduced by 11.3%.


  • Nguyen Thanh Tung, Predicting the quality of irrigation services in the red river delta with machine learning models

To predict a satisfaction of users who use the water services is very important for the fee exemption policy to water and agriculture services. This policy has positive impacts on the water exploited and management enterprises, the national budget and social security. In this talk, we present some regression machine learning models to predict the satisfaction of users related to the quality of irrigation service in the red river delta.

Experimental results showed that the non-linear regression models achieve lower regression errors than linear models. The diversity and feasibility of these regression models can be applied for dealing with economic problems in the domain of water resource management.


  • Bui Xuan Binh Minh, Temporal matching

When mining data collected from human activities, graph edges come ordered by the time instants where they are recorded, e.g. with web logs, phone calls, email exchanges, and so on. We call this kind of data a link stream: a sequence of elements of the form (i,uv), where i is an integer representing a time instant and uv a graph edge. We define a temporal edge --edge with duration-- as a set of timely consecutive links between the same vertices: (i,uv), (i+1,uv), ..., (i+j,uv). Such a temporal edge represents the fact that vertices u and v have been continuously linked from time instant i to time instant i+j.

Two temporal edges are dependent if there exist time instant i and vertex s such that each of the two temporal edges contains a link of the form (i,su), for some other vertex u. Roughly speaking, at time instant i, vertex s must choose between the two dependent temporal edges, and cannot be "available" in both. We introduce the notion of temporal matching to be a set of independent temporal edges. We note that a temporal matching in a link stream where the time dimension is reduced to one unique time instant is equivalent to a matching in classical graph theory.

In contrast to classical graph theory, we show that the problem of computing a temporal matching of maximum size in a link stream is in general NP-hard. We then depict a kernelization algorithm parameterized by the solution size for the problem, producing quadratic kernels. As a byproduct we also give a 2-approximation algorithm. Both algorithms are implemented and confronted to link streams collected from real world graph data:

https://github.com/antoinedimitriroux/Temporal-Matching-in-Link-Streams

We observe from the experiments that the kernelization algorithm can perform very well in practice, reducing the instance size downto 10-20% on realistic mining parameters. In contrast, the 2-approximation gives rather mixed results. We conjecture that the approximation factor can be improved.


  • Le Chi Ngoc, Hybrid Approach in Social Network Fake Accounts Detection

We propose a hybrid approach based on graph and features to detect fake account in social network FaceBook. The algorithm is tested on real data collected in Vietnam.


  • Bernard Lasserre, The Moment-SOS hierarchy

The Moment-SOS hierarchy initially introduced in optimization in 2000, is based on the theory of the K-moment problem and its dual counterpart, polynomials that are positive onK. It turns out that this methodology can be also applied to solve problems with positivity constraints "f(x) ≥ 0 for all x ∈ K" and/or linear constraints on Borel measures. Such problems can be viewed as specific instances of the "Generalized Problem of Moments" (GPM) whose list of important applications in various domains is endless. In these two lectures, I will describe this methodology and outline some of its applications in various domains.

More precisely, in the first lecture, I introduce the Moment-SOS hierarchy, positivity certificates, semidefinite relaxations, sparsity, etc. In the second lecture, I describe a few applications outside optimization (Optimal control, non-linear hyperbolic PDEs’, super-resolution, polynomial interpolation, etc.


  • Christoph Dürr, An adversarial model for Optimization under explorable uncertainty

One practical difficulty in computing a solution to some combinatorial optimization problem is that the data might be known only within some interval of uncertainty. In some cases it might be possible to tests specific variables of the input and obtain their exact value. A natural task in this model is to minimize the number of tests until it is possible to produce an optimal solution. This problem has been addressed in the context of computing a minimum spanning tree for a graph where edge weights are given within some uncertainty intervals, but also for the knapsack problem and a single-machine scheduling problem. In the later the processing time of a job can potentially be reduced (by an a priori unknown amount) by testing the job. Testing a job $j$ takes one unit of time and may reduce its processing time from the given upper limit $\bar{p}_j$ (which is the time taken to execute the job if it is not tested) to any value between $0$ and $\bar{p}_j$. This setting is motivated e.g. by applications where a code optimizer can be run on a job before executing it. This talk with be a gentle introduction into this new model, reveal key algorithmic ideas and present more in detail the later scheduling problem.


  • Bui Trong Kien, Second-order optimality conditions for multi-objective optimal control problems with mixed pointwise constraints and free right end points

In this report we present some new results on first-and second-order necessary optimality conditions of Karush–Kuhn–Tucker-type for H-locally weak solutions in the sense of Pareto of multi-objective optimal control problems (MOCP) with free right end points and mixed pointwise constraints.


  • Christophe Crespelle, On the effectiveness of the incremental approach to minimal chordal edge modification

Because edge modification problems are computationally difficult for most target graph classes, considerable attention has been devoted to inclusion-minimal edge modifications, which are usually polynomial-time computable and which can serve as an approximation of minimum cardinality edge modifications, albeit with no guarantee on the cardinality of the resulting modification set. Over the past fifteen years, the primary design approach used for inclusion-minimal edge modification algorithms is based on a specific incremental scheme. Unfortunately, nothing guarantees that the set $\mathcal{E}$ of edge modifications of a graph $G$ that can be obtained in this specific way spans all the inclusion-minimal edge modifications of $G$.

Here, we focus on edge modification problems into the class of chordal graphs and we show that for this the set $\mathcal{E}$ may not even contain any solution of minimum size and may not even contain a solution close to the minimum; in fact, we show that it may not contain a solution better than within an $\Omega(n)$ factor of the minimum. These results show strong limitations on the current favored algorithmic approach to inclusion-minimal edge modification and suggest that further developments might be better using other approaches.


  • Ho Tu Bao, Learning and Recommending Treatments Using Electronic Medical Records

The availability of electronic medical records (EMRs) has offered a great opportunity for developing and applying machine learning methods to address the learning and recommending treatments. Given a large set of heterogenous and longitudinal EMRs of patients for single or multiple diseases, the task is to learn and recommend treatment for a new patient of such diseases. Such an environment of healthcare is heavily dynamics and constantly evolving. In this work we present a novel method for learning and recommending treatments that overcomes the drawback of the previous work while maximizes the data utilization, incorporates domain knowledge, provides many more different kinds of treatment patterns and an interpretable treatment mechanism.

joint work with Hoang Khanh Hung


  • Phan Thi Ha Duong, Interaction over time and fixed-parameter tractable algorithm on (Bi-)sparse split problem of graph.

Interactions over time, such as phone calls, computer communications, physical proximity between individuals, shopping have been studied for a long time and have been captured in the link stream framework. Intuitively, a link stream is a sequence of pairs of the form (I; uv) where uv is an edge and I a time interval.

A link stream is (bi-)sparse split if it consists of a (two) clique(s) on an (two) interval times. Problem sparse split (resp. bi-sparse split) link stream edition asks to transform an arbitrary link stream into a sparse split (resp. bi-sparse split) link stream by performing at most some given number of modi cations on its timed edges.

We give a generic approach to devise fixed parameter tractable algorithms for link stream edition problems and exemplify on two particular problems: sparse split and bi-sparse split edition.