dr. Mark Lochrie, University of Central Lancashire
Title: What role does technology play in inspiring social innovation?
Abstract:
After 4 years of researching, designing, developing and deploying solutions “in the wild” and completing his PhD in “Community Participation in Mobile Entertainment Services #CPiMES”, Mark now focuses his research around ‘gameful design’ solutions focused to enhance the user experience. Mark’s role as a Creative Technologist in the Media Innovation Studio, is to look at ways in which creative experiences, gameful design and technology can be used to generate data, encourage participation and educate. In his talk, Mark will review past projects released “in the wild” and present insights into ongoing work of relevance focusing on determining the role technology plays in inspiring social innovation.
dr. Vladimir Gurvich, Rutgers University
Title: Complexity of generating
Abstract:
I will briefly survey joint results with Leonid Khachiyan, Endre Boros, Khaled Elbassioni, and Kazuhisa Makino on the complexity of generation (also called enumeration) problems.
Several examples:
1. Generating all negative cycles of a graph is intractable.
Furthermore, it can be reduced from enumerating all vertices of a polyhedron given by linear inequalities. Thus, the latter problem is intractable too. Yet, in case of the bounded polyhedra the question remains open (so-called polytope-polyhedron problem).
2. Generating all maximal frequent sets in binary matrices is intractable, in contrast to generating all minimal infrequent sets, which is tractable.
3. Generating all minimal integer vectors $x$ satisfying $Ax geq b$, $0 leq x leq c$ is tractable whenever $A$ is a non-negative integer matrix. Note that without this restriction we obtain just Integer Programming and already verifying feasibility becomes NP-hard. Also generating all maximal infeasible integer vectors for the above system is not tractable.
4. Generating all minimal strongly connected arc subgraphs of a (strongly connected) digraph is tractable. In contrast, generating all maximal NOT strongly connected ones (or, in other words, all minimal directed cuts) is intractable.
5. Given a graph $G = (V,E)$ and an edge-cover $E = E_1 cup ... cup E_n$.
Generating all inclusion-minimal subsets $I' subseteq I = {1,...,n}$ such that the corresponding graph is connected on $V$ is tractable. In contrast, generating all such subsets connecting two given vertices $v', v'' in V$ is intractable; as well as generating all "maximal not connecting subsets" in both cases.
Many of the above cases are tractable, because they belong to an important class of the so-called dual-bounded problems. Such problems, in quasi-polynomial $n^{log n}$ time can be reduced to Boolean dualization, which, in its turn, is also solvable in quasi-polynomial time.
dr. Miklos Kresz, University of Szeged
Title: Vehicle scheduling with real-world constraints in public bus transportation
Abstract:
Public transportation services usually operate on previously determined bus – or other vehicle – lines, which connect a certain number of stations. The lines and their daily services are fixed in a timetable which provides the departure and arrival time of the trips for each line. In practice the timetable – based on travel demands and logistic decisions – is given in advance.
A central problem of public transportation companies is to optimize their operational process. Since the minimization of the overall operational cost is a very complex task, the arising subproblems are considered as separeted optimization problems. The vehicle scheduling problem in public tranportation consists of scheduling a fleet of vehicles to cover the timetabled trips with a minimum cost. Apart from the general cost determined by the scheduled vehicles, the transporation costs of the timetabled trips and that of the so-called deadhead trips (trips without passangers between two geolocations) contribute to the definition of an appropriate objective function.
There are several mathematical formulations that can be used to model the vehicle scheduling problem. Most of these formulations are based on network-flow approaches and quasi-assignment models. In real-world applications, however, numerous additional constraints are considered which are not covered by the above models. In daily operation the vehicle schedules need to satisfy vehicle-specific requirements such as fueling and maintenance constraints or different parking rules. In operational management it is also a frequent situation that some unexpected events (the most common of which are vehicle breakdown and lateness) render the pre-planned schedule infeasible, which requires a rescheduling process. Vehicle assignment with respect to the daily schedules in a long-term fashion (several weeks or months) is also a crucial question in order to plan those duties of the vehicles that are not related to the timetable. Finally, since driver scheduling is also an important part of operational transport management, the constructed vehicle schedules need to consider some soft constraints induced by the driver rules.
In this talk we present efficient models and solutions methods for the above mentioned real-world vehicle scheduling problems. The solutions were developed by an implementation-oriented approach, which will be demonstrated by real-world test cases. The results were achieved in a group work at the Discrete Optimization and Data Mining Laboratory in cooperation with a regional bus transportation company.
dr. Alexander Pott, Universität Magdeburg
Title: Bent functions, difference sets and strongly regular graphs
Boolean bent functions are a fascinating topic in Discrete Mathematics
because there are many connections with other fields of mathematics. For example, bent functions are related to the covering radius problem of the first order Reed Muller code, they give symmetric designs and Hadamard matrices as well as strongly regular graphs. Some of theses connections will be described in my talk. A little less known are p-ary bent functions where p is an odd prime. I will show that such p-ary bent functions are related to many different fields in Discrete Mathematics, too, in particular to strongly regular graphs.
dr. Jarosław Grytczuk, Jagiellonian University
"The entropy compression method in graph coloring and combinatorics on
words"
The "entropy compression" is a term coined by Terrence Tao to describe algorithmic version of the Lovasz Local Lemma discovered recently by Robin Moser and Gabor Tardos. A basic idea is surprisingly simple and can be described as a random greedy procedure: color a given structure randomly, fixing eventual local errors by random recoloring (of just a small part of the structure where the error occurs). This looks like a naive idea since recoloring may cause occurrence of new errors in neighboring substructures. Do not worry and keep on fixing these new errors in the same way. The surprising result of Moser and Tardos asserts that, under certain conditions, this procedure gives a desired coloring with non-zero probability in expected polynomial time. In the talk I will present some spectacular applications of the entropy compression method in graph coloring and combinatorics on words.
dr. Luis Martínez Fernández, University of the Basque Country
Title: Heuristic Approaches to Solve the Shortest Common Superstring Problem
The shortest common superstring problem has important applications in bioinformatics, and several approaches have been proposed in the literatur to find good approximations to its solutions. In this talk we survey some heuristic algorithms used to get such approximations, and present a new method based on the use of “estimation of distribution algorithms” (EDAs).
(Joint work with Iker Malaina, Martín Blas Pérez and Ildefonso Martínez de la Fuente).
