Invited speakers
Prof. Bo Chen University of Warwick, UK
Capacity Auctions:
VCG Mechanism vs. Submodularity
Abstract: We study a form of capacity mechanism that combines capacity and supply auctions. We characterize how participants bid in this auction and show that, on a pay-as-bid basis, an equilibrium behavior gives Vickrey-Clarke-Groves (VCG) profits and achieves efficient outcomes when there is submodularity, which is in stark contrast with what in the existing literature — at equilibrium VCG payments achieve truthful bids and efficiency. We also provide some necessary and sufficient conditions for submodularity.
Prof. Alexander Kostochka University of Illinois at Chicago, USA
Long cycles in graph and hypergraphs
Abstract: Finding long cycles in graphs is an NP-hard problem. Cycles in hypergraphs can be defined in several natural ways. Since finding long cycles in hypergraphs is hard for all kinds of cycles, it makes sense to consider approximate algorithms and extremal problems on long cycles in hypergraphs. We discuss several such extremal problems, recent progress on them and possible algorithms based on the proofs.
VIDEO (mp4.fail 191 Mb)
Abstract: Finding long cycles in graphs is an NP-hard problem. Cycles in hypergraphs can be defined in several natural ways. Since finding long cycles in hypergraphs is hard for all kinds of cycles, it makes sense to consider approximate algorithms and extremal problems on long cycles in hypergraphs. We discuss several such extremal problems, recent progress on them and possible algorithms based on the proofs.
VIDEO (mp4.fail 191 Mb)
Prof. Sergei Chubanov Bosch Research, Germany
Convex geometry in the context of artificial intelligence
Abstract: Applications of convex optimization in machine learning include support vector machines, polyhedral classifiers, deduction of disjunctive and conjunctive normal forms, time-series clustering, image segmentation, different models based on information theory, e.g., those involving Shannon entropy and Kullback-Leibler divergence. Virtually the whole spectrum of standard methods of convex optimization such as the gradient descent, the Frank-Wolfe algorithm, and interior-point methods is used for training deep neural networks. At the same time, some new results in the area of linear programming and convex optimization indicate that there are methodologies beyond the classical approaches which can lead to substantially more efficient machine learning algorithms and better interpretable machine learning models. So in this lecture we will address recent developments in convex optimization and convex analysis, in particular in the context of machine learning.
VIDEO (mp4.file 86 Mb)
Abstract: Applications of convex optimization in machine learning include support vector machines, polyhedral classifiers, deduction of disjunctive and conjunctive normal forms, time-series clustering, image segmentation, different models based on information theory, e.g., those involving Shannon entropy and Kullback-Leibler divergence. Virtually the whole spectrum of standard methods of convex optimization such as the gradient descent, the Frank-Wolfe algorithm, and interior-point methods is used for training deep neural networks. At the same time, some new results in the area of linear programming and convex optimization indicate that there are methodologies beyond the classical approaches which can lead to substantially more efficient machine learning algorithms and better interpretable machine learning models. So in this lecture we will address recent developments in convex optimization and convex analysis, in particular in the context of machine learning.
VIDEO (mp4.file 86 Mb)
Professor Aida Abiad Eindhoven University of Technology and Ghent University, The Netherlands
On graph invariants and their application to the graph isomorphism problem
Abstract: Graphs invariants have proven to be one of the most important and fruitful concepts in modern Combinatorics and Theoretical Computer Science. Besides being a fascinating study subject for their own sake, they play an important role in the famous graph isomorphism problem. Their success serves as a natural motivation for the following natural question: what are the graph properties that can be deduced from a certain graph invariant? In this talk we will give an overview and will report on recent results concerning two graph invariants: the status sequence of a graph and the graph spectrum.
VIDEO (mp4.file 120Mb)
VIDEO (mp4.file 120Mb)
Professor Soumyendu Raha Indian Institute of Science, Bangalore, India
Partitioning a Reaction-Diffusion Ecological Network for Dynamic Stability
Abstract: The loss of dispersal connections between habitat patches may destabilize the populations in a patched ecological network. This work studies the stability of the populations when one or more communication links get removed. An example is finding the alignment of a highway through a patched forest containing a network of metapopulations in the patches. This problem is modeled as that of finding a stable cut of the graph induced by the metapopulations network, where nodes represent the habitat patches and the weighted edges model the dispersal between the habitat patches. A reaction-diffusion system on the graph models the dynamics of the predator-prey system over the patched ecological network. The graph Laplacian’s Fiedler value which indicates the well-connectedness of the graph, is shown to affect the stability of the metapopulations. We show that when the Fiedler value is sufficiently large, the removal of edges without destabilizing the dynamics of the network is possible. We give an exhaustive graph partitioning procedure, which is suitable for smaller networks and uses as criterion both the local and global stability of populations in the partitioned networks. An heuristic graph bisection algorithm that preserves the preassigned lower bound for the Fiedler value is proposed for larger networks and illustrated with examples.
Joint work with W. Vikram Bhatt and Dinesh Kumar
Professor Igor Konnov Kazan Federal University, Russia
Equilibrium Formulations of Relative Optimization Problems
Abstract: We consider relative or subjective optimization problems where
the goal function and feasible set are dependent of the current state
of the system under consideration. We propose equilibrium formulations of
the corresponding problems that lead to general (quasi-)equilibrium problems.
We propose to apply a regularized version of the penalty method for the
general quasi-equilibrium problem, which enables us to establish
existence results under weak coercivity conditions and replace the
quasi-equilibrium problem with a sequence of the usual equilibrium problems.
We describe several examples of applications and show that
the subjective approach can be extended to non-cooperative game problems.
Professor Evripidis Bampis Sorbonne Universite, Paris, France
Multistage Optimization Problems
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.
Professor Yakov Zinder University of Technology, Sydney, Australia
Two-stage Scheduling Models with Limited Storage
Abstract: Publications on the two-stage scheduling systems such as two-machine flow shops, job shops and open shops, single machine with coupled tasks, and their various generalisations constitute a significant part of the scheduling literature. Many of these publications consider a limited storage (buffer) or an additional limited resource. The majority of publications on scheduling with a buffer consider the buffer as storage that limits the number of jobs that have completed their first operation and are waiting for the commencement of the second one. The majority of scheduling models with an additional resource assume that the resource is used only during the processing on a machine. Despite numerous possible applications that include, for example, supply chains, multimedia systems and data gathering networks, much less research has been done on the models where the resource (storage space, buffer) is allocated to a job from the start of its first operation till the end of its second operation and where the storage requirement varies from job to job. The talk presents a survey of recent publications on this type of scheduling problems, which includes NP-hardness proofs, particular cases amenable for polynomial-time algorithms, polynomial approximation schemes, and integer programming based algorithms, including for example Lagrangian relaxation.
Professor Panos M. Pardalos University Florida, USA
Inverse Combinatorial Optimization Problems
Abstract: Given an optimization problem and a feasible solution to it, the corresponding inverse optimization problem is to find a minimal adjustment of the cost vector under some norm such that the given solution becomes optimum. Inverse optimization problems have been applied in diverse areas, ranging from geophysical sciences, traffic networks, communication networks, facility location problems, finance, electricity markets, and medical decision-making. It has been studied in various optimization frameworks including linear programming, combinatorial optimization, conic, integer and mixed-integer programming, variational inequalities, and countably infinite linear problems and robust optimization. In this talk, we mainly concentrate on inverse combinatorial optimization problems (ICOP). We will introduce some classes of ICOP as well as general methods to solve them. Some open problems are proposed. We also discuss some generalized inverse optimization problems. We introduce inverse optimization problems on spanning trees and mainly concentrate on the inverse max+sum spanning tree problems in which the original problem aims to minimize the sum of a maximum weight and a sum cost of a spanning tree.