Home
Aims & Objectives
Important Dates
Committees
Plenary Speakers
Registration
Accepted Papers
Conference Venue
Scientific Program
Social Program
Travel & Accommodation
Contact

Plenary Speakers
Confirmed Speakers

Yves Crama
HEC Liège
Reformulations of nonlinear binary optimization problems
A pseudoBoolean function is a realvalued function
f(x)=f(x_{1},x_{2},...,x_{n}) of n binary
variables. It is wellknown that every pseudoBoolean function can be uniquely
represented as a multilinear polynomial in its variables. Nonlinear binary
optimization problems, or pseudoBoolean optimization (PBO) problems, of the
form min{ f(x) : x ∈ {0,1}^{n} } where f(x) is a
pseudoBoolean polynomial, have attracted the attention of numerous researchers
for more than 50 years. These problems are notoriously difficult, as they
naturally encompass a broad variety of models such as maximum satisfiability,
max cut, graph coloring, or image restoration. In this talk, I present recent
results (obtained in collaboration with Martin Anthony, Endre Boros, Christoph
Buchheim, Aritanan Gruber, and Elisabeth RodriguezHeck) regarding
reformulations of nonlinear PBO problems either as linear integer programming
problems or as quadratic PBO problems.


John B. Gauci
University of Malta
Superconnectivity and superedgeconnectivity of graphs
Network design focuses on determining how to best connect nodes such that
the resulting network is, among other considerations, efficient, resistant to
threats, costeffective and fault tolerant. A topological optimisation question
that addresses the requirement of faulttolerance asks for the connectivity of
the graph (or digraph) underlying the network. The property of a graph being
connected depends only on whether the graph contains a path for every pair of
vertices. However, besides the classical connectivity measures that study the
minimum number of vertices or edges that need to be deleted to disconnect the
graph, other types of connectivity have recently received much attention. These
include connectivity parameters that impose some restrictions on the components
of the remaining graph; a notion proposed by Harary (1983) and known as
conditional connectivity. Given a graph G and some graph theoretical
property P, the size of the smallest set S of vertices (or
edges), if such a set exists, such that the graph GS is disconnected
and every remaining component has property P is the conditional
connectivity (or conditional edgeconnectivity) of G. Although,
theoretically, any property P can be chosen, the most popular choices of
P are those having practical applications.
In this talk we restrict our attention to the superconnectivity and the
superedgeconnectivity of a graph. These notions respectively study the least
number of vertices and edges that need to be deleted from a graph to disconnect
the graph such that each remaining component is not trivial. In other words,
the property that each component must possess is that of not being an isolated
vertex, or equivalently, that of containing at least one edge. We will present
wellknown bounds for these parameters and discuss sufficient conditions for
the bounds to be attained in terms of vertexdegrees, diameter and girth.
Finally we review the superconnectivity and the superedgeconnectivity of
some families of graphs, including circulant graphs, hypercubes, generalized
Petersen graphs, Kneser graphs and Johnson graphs.


Christos H. Papadimitriou
University of California at Berkeley
A computer scientist thinks about the brain
How does the Brain beget the Mind? How do neurons and synapses, molecules
and genes, give rise to behavior and cognition, love and sadness, language and
intelligence? Despite lightning progress in recording and molecular technology
and a deluge of experimental data, we do not seem to get closer to an answer.
This is a talk about admiring and appreciating the problem, and proposing a new
approach based on a recognized but little studied intermediate level of Brain
computation carried out by the synchronous firing of large and highly
interconnected sets of neurons called assemblies. We show that assemblies give
rise to a novel algebra and calculus, and we speculate that they instrument our
higher cognitive functions, such as language and math.


Daniel Kuhn
École polytechnique fédérale de Lausanne
From Data to Less Data to Decisions
The proliferation of “big data" created by mobile devices, social media,
sensor networks, satellites etc. offers the potential to make more informed
decisions, but it also poses a significant challenge to the scalability of the
current optimization methods and decision support tools. This raises a number
of fundamental questions: How should uncertain parameters in the big data
regime be represented so that they lend themselves to integration into
optimization problems? Which observations and features of a highdimensional
parameter set are most relevant for a particular optimization problem? How can
these relevant observations and features be identified efficiently? How can one
maintain the computational tractability of the emerging optimization problems?
In the first part of the talk I will introduce tractable approaches for
reducing large datasets to smaller ones at minimal loss of information. In the
second part I will describe tractable methods for recognizing balanced clusters
of similar datapoints in large unstructured datasets. Both methods come with
rigorous performance guarantees. Implications for practical decisionmaking
will be highlighted.

