About Workshop

The workshop is organized as a part of the project Efficient algorithms, automata and data structures (APVV-15-0091). The mail goal of the workshop is to present current research results of the project team and to learn about the newest trends in research areas related to the project thanks to invited international speakers.

The main topics of the workshop EAADS 2019:

  • Algorithms on graphs (matchings, networks, colorings)
  • State and descriptional complexity
  • Indoor navigation and localization

About Project

The aim of the project is the research in the area of efficient algorithms for finite state automata, graph invariants and data analysis. More precisely, the goals are to obtain tighter bound for the state complexity of the conversion between various types of automata and devices with bounded stack, precise complexity of regular operations in binary and unary case, a detailed description of various complexity aspects of generalized graph invariants like vertex cover, independent set, maximum matching, that have applications in cryptography, medicine, organization of education and health care, image analysis and segmentation etc., better understanding of concept hierarchy in formal concept analysis and efficient algorithms for finding bonds between fuzzy contexts.

The project is supported by The Slovak Research and Development Agency.

3 days

Košice
Slovakia

30+
Participants

5
Invited Speakers

Invited Speakers

Péter Biró

Péter Biró

Institute of Economics
Hungarian Academy of Sciences
Budapest, Hungary

Ágnes Cseh

Ágnes Cseh

Institute of Economics
Hungarian Academy of Sciences
Budapest, Hungary

Tamás Fleiner

Tamás Fleiner

Department of Operations Research
Eötvös Loránd University
Budapest, Hungary

Zsuzsanna Jankó

Zsuzsanna Jankó

Department of Mathematics
University of Hamburg
Hamburg, Germany

Department of Operations Research and Actuarial Sciences
Corvinus University of Budapest
Budapest, Hungary

Gyorgy Vaszil

György Vaszil

Department of Computer Science
University of Debrecen
Debrecen, Hungary

Discussions and Collaboration

During the workshop there will be plenty of space for active collaboration and discussions about research topics and problems related to topics of the project.

Schedule

Tuesday - morning session

09:30-10:20 (room: SJ2S07/LIDA)

Katarína Cechlárová, Lukáš Miňo: How to find a fair schedule: work in progress

The young physicists tournament is an international competition of teams, where the participating teams not only present their solutions of the problems published by the international jury, but also learn how to oppose and evaluate solutions of other teams.
According to the rules valid for Slovak regional rounds, each team in their application indicate 3 problems chosen among the 17 published. These will be the problems they are going to present. The competition takes part in scientific discussions of three or four teams, called Fights. In each Fight, 3 problems are presented and teams alternate in the roles of Presenter, Opponent and Reviewer. The task of the organisers is to choose the composition of Fights in such a way that each team present all their chosen problems, no problem is presented more than once in one Fight and if one school nominates more than one team, one Fight does not involve two teams from the same school. We formulated the problem of a feasible schedule as an integer program. We also added several fairness conditions, like: "no team is allowed to see a presentation of a problem that they will present later", or "no team can see the same problem more than once in either role".
The designed integer program was tested on real as well as randomly generated data. While for the real sets of applications fair schedules were found within a few seconds, the proportion of solved random instances was decreasing with the strenght of the fairness conditions. As a future research topic we propose a change in the rules of applications to allow teams to apply with more problems and to state preferences among them.

10:30-11:20 (room: SJ2S07/LIDA)

Zsuzsanna Jankó, Tamás Fleiner: Complexity of Stability in Trading Networks

Efficient computability is an important property of solution concepts in matching markets. We consider the computational complexity of finding and verifying various solution concepts in trading networks—multi-sided matching markets with bilateral contracts—under the assumption of full substitutability of agents’ preferences. It is known that outcomes that satisfy trail stability always exist and can be found in linear time. Here we consider a slightly stronger solution concept in which agents can simultaneously offer an upstream and a downstream contract. We show that deciding the existence of outcomes satisfying this solution concept is an NP-complete problem even in a special (flow network) case of our model. It follows that the existence of stable outcomes—immune to deviations by arbitrary sets of agents—is also an NP-hard problem in trading networks (and in flow networks). Finally, we show that even verifying whether a given outcome is stable is NP-complete in trading networks

11:30-12:20 (room: SJ2S07/LIDA)

Péter Biró: College admissions with ties and common quotas: Integer programming approach

Admission to universities is organised in a centralised scheme in Hungary. In this paper we investigate two major specialities of this application: ties and common quotas. A tie occur when some students have the same score at a programme. If not enough seats are available for the last tied group of applicants at a programme then there are three reasonable policies used in practice: 1. all must be rejected, as in Hungary 2. all can be accepted, as in Chile 3. a lottery decides which students are accepted from this group, as in Ireland. Student-optimal stable matchings can be computed efficiently for each of the above three cases, but we also develop integer programming (IP) formulations for solving these problems, and we compare the solutions obtained by the three policies for a real instance of the Hungarian application from 2008. Common quotas are arising in Hungary from the faculty quotas on their programmes and from the national quotas over state-financed students in each subject. The overlapping structure of common quotas makes the computational problem of finding a stable solution NP-hard, even for strict rankings. In the case of ties and common quotas there are several possible stable solution concepts that one may consider. We develop various IP formulations for solving these stable matching problems, starting with the simpler, classical problems, and finally for the realistic case when both special features are present. We test the IP formulations on the large scale real instance from 2008, and we demonstrate that the most general case is also solvable in practice with our IP technique.

Tuesday - afternoon session

14:00-15:00 (room: SJ1Z17T/VKM)

Ágnes Cseh: Optimal Kidney Exchange with Immunosuppressants

The deployment of centralized matching algorithms for efficient exchange of donated kidneys is a major success story of market design. In the standard kidney exchange problem, blood- or tissue-type incompatibility between a patient and a donor makes a transplant impossible. However, novel technological advances on potent immunosuppressant drugs can lift this barrier. We present a general computational framework to study kidney exchange with immunosuppressants. In contrast to the standard kidney exchange problem, our problem also involves the decision about which patients get immunosuppressants to make them compatible with originally incompatible kidneys. Our main contribution is a set of general algorithms that provide flexibility in terms of satisfying meaningful purposes.

Wednesday - morning session

10:00-12:00 (room: SJ1Z17T/VKM)

Open problem session

Wednesday - afternoon session

14:00-16:00 (room: SJ1Z17T/VKM)

Open problem session

Thursday - morning session

09:00-09:50 (room: SJ1Z17T/VKM)

Juraj Šebej: Note on partitioning a symmetric rational relation into two asymmetric rational relations

We consider the problem of partitioning effectively a given symmetric (and irreflexive) rational relation R into two asymmetric ra- tional relations. This problem is motivated by a recent method of embed- ding an R-independent language into one that is maximal R-independent, where the method requires to use an asymmetric partition of R. We solve the problem when R is realized by a zero-avoiding transducer (with some bound k): if the absolute value of the input-output length discrepancy of a computation exceeds k then the length discrepancy of the compu- tation cannot become zero. This class of relations properly contains all recognizable, all left synchronous, and all right synchronous relations. We leave the asymmetric partition problem open when R is not realized by a zero-avoiding transducer. We also show examples of total word- orderings for which there is a relation R that cannot be partitioned into two asymmetric rational relations such that one of them is decreasing with respect to the given word-ordering.

10:00-10:50 (room: SJ1Z17T/VKM)

Gyorgy Vaszil: Languages characterized by P automata and P colony automata: On the descriptional and computational complexity of some bio-inspired computational models

We review the different approaches to the description of formal languages by automaton-like variants of P systems. P systems or membrane systems are so called unconventional computing models inspired by the functioning of the living cell. The main component of these systems is a membrane structure with membranes enclosing regions as multisets of objects. Each membrane has an associated set of operators working on the objects contained by the region which can be of different types: they can change the objects or they can move the objects between the regions and/or the "environment" of the system. Automaton-like variants of membrane systems are designed to be able to "read" and "accept" strings of symbols, so in this sense they resemble traditional automata, although their structure, and their way of operation is bio-inspired and unconventional. In the talk we examine properties of P automata and P colony automata, and present some results focusing on their computational power and their descriptional complexity.

11:00-11:50 (room: SJ1Z17T/VKM)

Alenader Szabari: Conjuctive grammars and alternating pushdown automata.

Properties of Languages generated by conjuctive grammars. Structure the pushdown in alternating pushdown automata. Comparing the languages generated by conjuctive grammars with languages accepted by altenratig pushdown automata.

Thursday - afternoon session

13:00-16:30 (room: SJ1Z17T/VKM)

Workgroup meetings

Research discussions in workgroups together with invited speakers.

Location

Institute of Computer Science
Faculty of Science
P. J. Šafárik University in Košice

Jesenná 5
040 01 Košice
Slovakia

Photos