Monday, June 10, 2013
Humboldt-Universität zu Berlin
Institut für Informatik
Erwin Schroedinger-Zentrum
Rudower Chaussee 26
12489 Berlin
room 1.308
Lecture - 14:15
Abstract:
Complementary pivot algorithms, in the style of the simplex
algorithm, tend to work well in practice despite having an exponential
worst case behavior -- a case in point being the classic Lemke-Howson
algorithm (1964) for 2-player Nash equilibrium. This algorithm also gives a direct proof of membership of the problem in the class PPAD and
yields deep structural insights, such as oddness of the number of
equilibria.
Our first result accomplishes all of the above for the problem of
finding an equilibrium for an Arrow-Debreu market under separable,
piecewise linear concave utilities. Our second result extends this to
markets with production.
Based on the following paper, and a recent joint work with Jugal Garg
and Ruta Mehta: www.cc.gatech.edu/~vazirani/SPLC.pdf
Colloquium - 16:00
Abstract:
Feasibility tests for sporadic real-time systems answer the question whether all possible realization of a certain set of sporadically recurring computational tasks can be executed in time on a given processor platform. The computational tasks consist of different subtasks some of which can be executed in parallel while others are in a precedence relation. Real-time systems increasingly contain processing units with multiple cores. To use this additional power of parallel computation in hard deadline environments, one needs schedulability tests for task models that represent the possibilities of parallel execution of jobs of a task. A standard model is to represent a (sporadically) recurrent task by a directed acyclic graph (DAG). The nodes of the DAG correspond to the jobs of the task. All such jobs are released simultaneously, have to be completed within some common relative deadline, and some pairs of jobs are linked by a precedence constraint, i.e., an arc of the DAG. This poses new challenges for analyzing whether a task system is feasible, in particular for the commonly used online algorithms Earliest Deadline First (EDF) and Deadline Monotonic (DM). While for ordinary sporadic tasks the required algorithmic techniques are well-understood, despite recent research much remains open in this model.
In this work, we completely close the gap between the algorithmic understanding of feasibility analysis for the usual sporadic task model and the case where each sporadic task is a DAG. We show for DAG tasks that EDF has a tight speedup bound of 2 - 1/m, where m is the number of processors, while DM has a speedup bound of at most 3 - 1/m. Moreover, we present polynomial and pseudopolynomial time tests, of differing effectiveness, for determining whether a set of sporadic DAG tasks can be scheduled by EDF or DM to meet all deadlines on a specified number of processors. We remark that the effectiveness of some of our tests matches the best known algorithms for ordinary sporadic task sets, thus closing the gap.
Joint work with Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, and Andreas Wiese.