• Evripidis Bampis
Sorbonne Universitéhttp://www-desir.lip6.fr/~bampise/
  • Xujin Chen
Academy of Mathematics and Systems Science, Chinese Academy of Sciences http://people.ucas.ac.cn/~0011018?language=en
  • Kazuhisa Makino
Kyoto Universityhttp://www.kurims.

Evripidis Bampis

Title. Algorithmic multistage optimization

Abstract. Many systems have to be maintained while the underlying constraints, costs and/or profits change over time. Although the state of a system may evolve during time, a non-negligible transition cost is incurred for transitioning from one state to another. In order to model such situations, Gupta et al. (ICALP 2014) and Eisenstat et al. (ICALP 2014) introduced a multistage model where the input is a sequence of instances (one for each time step), and the goal is to find a sequence of solutions (one for each time step) that are both (i) near optimal for each time step and (ii) as stable as possible. In this talk, we will give a survey of recent results in algorithmic multistage optimization, both in the offline and the online contexts and we will discuss connections with other models taking into account the evolution of data during time.

Xujin Chen

Title. Bounding Residence Times for Atomic Dynamic Routing

Abstract. With a long history as well as diverse applications, models of dynamic routing are recently drawing increasing research attention. These models are generally more realistic and, at the same time, more challenging than the static ones. Compared with its non-atomic counterpart, atomic dynamic routing is typically even more difficult to study. The difficulty stems from the fact that interactions among atomic agents could be formidably complicated due to their dynamic and combinatorial nature and hard-to-predict chain effects. In this talk, we discuss the problem of bounding agents’ residence times for a broad class of atomic dynamic routing problems. We explore novel token techniques, which help circumvent direct analysis of complicated chain effects. Even though agents may enter the network over time for an infinite number of periods, we prove that under a mild condition, the residence time of every agent is upper bounded by a network constant plus the total number of agents inside the network at the entry time of the agent. Applying our result to three game models of atomic dynamic routing proposed in the recent literature, we establish that residence times of selfish agents at an equilibrium are upper bounded by a constant that is dependent only on the network, provided the network is series-parallel and the number of incoming agents at each time point does not exceed the network capacity. (Joint work with Zhigang Cao, Bo Chen, and Changjun Wang)

Kazuhisa Makino

Title: Monotone Dualization and Related Topics

Abstract: Monotone dualization is the problem to compute a prime disjunctive normal form of a monotone Boolean function f from a conjunctive normal form (CNF) of f. Monotone dualization is a problem which, in different disguise, is ubiquitous in many areas including computer science, artificial intelligence, and Game Theory. It is also one of the few problems whose precise tractability status (in terms of polynomial-time solvability) is still unknown, and now open for more than 35 years. The corresponding decision problem is known to be solvable in quasi-polynomial time (and thus most likely not co-NP-hard), due to Fredman and Khachiyan. However, it is still open if it can be solved in polynomial time.

In this talk, we discuss recent progress on monotone dualization and related topics.