2022 May 2015
Europe/Ljubljana timezone
dr. Mark Lochrie, University of Central LancashireTitle: 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 UniversityTitle: 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 (socalled polytopepolyhedron 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 nonnegative integer matrix. Note that without this restriction we obtain just Integer Programming and already verifying feasibility becomes NPhard. 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 edgecover $E = E_1 cup ... cup E_n$. Generating all inclusionminimal 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 socalled dualbounded problems. Such problems, in quasipolynomial $n^{log n}$ time can be reduced to Boolean dualization, which, in its turn, is also solvable in quasipolynomial time. dr. Miklos Kresz, University of SzegedTitle: Vehicle scheduling with realworld 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 socalled 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 networkflow approaches and quasiassignment models. In realworld applications, however, numerous additional constraints are considered which are not covered by the above models. In daily operation the vehicle schedules need to satisfy vehiclespecific 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 preplanned schedule infeasible, which requires a rescheduling process. Vehicle assignment with respect to the daily schedules in a longterm 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 realworld vehicle scheduling problems. The solutions were developed by an implementationoriented approach, which will be demonstrated by realworld 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 MagdeburgTitle: Bent functions, difference sets and strongly regular graphsBoolean 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 pary bent functions where p is an odd prime. I will show that such pary 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 nonzero 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 CountryTitle: 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).
