ICE-TCS Theory Day
Open for everyone
ICE-TCS Theory Day 2016
Date/Time: Friday, 27 May 2016, 13:30-15:30
Location: M102 - Reykjavík University
13:30-13:35 Welcome by Magnús
13:35-14:25 Tamás Fleiner (Budapest University of Technology and Economics, Hungary). Pareto optimality in many-to-many matching problems.
14:25-14:45 Coffee break
14:45-15:05 Álvaro Garcia-Pérez. No solvable lambda-value term left behind.
15:05-15:25 Christian Konrad. The Triangle Scheduling Problem.
Abstracts of the talks
Tamás Fleiner (Budapest University of Technology and Economics, Hungary). Pareto optimality in many-to-many matching problems.
Consider a many-to-many matching market that involves two finite disjoint sets, a set of applicants A and a set of courses C. Each applicant has preferences on the different sets of courses she can attend, while each course has a quota of applicants that it can admit. In this paper, we examine Pareto optimal matchings (briefly POM) in the context of such markets, that can also incorporate additional constraints, e.g., each course bearing some cost and each applicant having an available budget. We provide necessary and sufficient conditions for a many-to-many matching to be Pareto optimal and indicate that checking whether a given matching is Pareto optimal requires polynomial time. Moreover, we provide a generalized version of serial dictatorship, which can be used to obtain any many-to-many POM. We mention certain variants of the above problem that turn out to be intractable.
This is joint work with Katarina Cechlarova, Pavlos Eirinakis, Dimitrios Magos, Ioannis Mourtos and Eva Potpinkova.
Álvaro García Pérez (Reykjavik University). No solvable lambda-value term left behind
What's solvability? For some terms (i.e. programs) of the pure lambda calculus reduction does not terminate. But these non-terminating terms do not all represent the same useless computation. If we equate them we obtain an inconsistent proof theory that equates every term of the lambda calculus with each other. Indeed, some non-terminating terms are nevertheless useful if used as functions. More precisely, when applying these non-terminating terms to suitable operands we get back terminating results.
The set of solvables is made of terminating terms (i.e. terms that reduce to a definite result) and those useful non-terminating terms. The rest are unsolvables which are useless: equating them gives rise to a consistent proof theory that models usefulness of terms.
Solvability has also been studied in the lambda-value calculus that (broadly speaking) models call-by-value evaluation. The problem is that the resulting proof theory is not 'quite' consistent and some normal forms are unsolvable.
We did some exegetical work and found out the problem was with the adaptation of a definition from the pure lambda calculus that was unsuited for the lambda-value calculus. We fixed this and got not only a consistent proof theory that models usefulness, but some extra results about the sequential character of lambda-value terms. Modelling usefulness accurately in this calculus has been an open problem since the seventies, only partially solved in the nineties.
This is joint work with Pablo Nogueira from the IMDEA Software Institute in
Christian Konrad (Reykjavik University). The Triangle Scheduling Problem.
In a multi-criticality system, jobs with different criticality levels coexist and need to share common resources, such as processing time on a processor. If the actual runtime of a highly critical job (e.g. a job that controls the breaks of a car) exceeds its predicted runtime, the execution of such a job may nevertheless continue and cancel the execution of lower critical jobs (e.g. a job that displays the temperature in the car). We are therefore interested in the following one processor scheduling problem: Given a set of unit length jobs with different criticality levels, find a schedule of minimal length such that the execution time of every job with criticality level i may be prolonged to i (consecutive) time slots without canceling other jobs of equal or larger criticality.
This problem has a natural representation as a one-dimensional triangle alignment problem. We show that it is NP-hard in the strong sense and that it has a QPTAS. We analyze a Greedy algorithm for the problem and show that its approximation factor is between 1.05 and 1.5.