#	Pagina
attuale pagina	/open-h2020/projects/203276/results.html

Report

Teaser, summary, work performed and final results

Periodic Reporting for period 2 - APEG (Algorithmic Performance Guarantees: Foundations and Applications)

Teaser

Summary

Optimization problems are ubiquitous in computer science and, as such, omnipresent in modern society. However, a major part of these problems cannot be solved to optimality. Consequently, algorithms that achieve provably good performance guarantees are of immense importance. The goal of this project is to significantly advance the state of the art on algorithmic performance guarantees, breaking new grounds in the areas of online algorithms, approximations algorithms and algorithmic game theory. The project develops new algorithmic techniques. These novel approaches are applied to solve fundamental algorithmic problems. Specifically, the project attacks long-standing open problems and explores new algorithmic settings arising in modern applications. The research agenda encompasses a wide spectrum of classical and urgent topics including (a) resource allocation in computer systems, (b) data structuring, (c) graph problems, with relations to Internet advertising, (d) complex networks and (e) massively parallel systems. The contributions advance modern algorithmics, with a focus on problems of high theoretical or practical relevance.

Work performed

During the first funding period we have made significant progress in each of the four work packages of the project.

1 For classical resource management and data structuring, we have bridged the gap between theory and practice. Standard algorithmic analysis gives overly pessimistic results as it ignores the fact that real-world input exhibits locality of reference. We have developed suitable and simple locality models, capturing phenomena that are observed in practice. Our theoretical investigations are complemented by experimental studies. For the first time, the theoretically proven bounds match the experimentally observed ones. For fundamental processor scheduling problems, we have explored relaxed service models, such as job migration, which are relevant in practice. We demonstrate that, thereby, considerably improved performance guarantees are attained.

2 As for energy conservation, we have initiated the algorithmic study of energy minimization in data centers. Specifically, we have introduced and studied novel optimization problems that rightsize the pool of active servers with the objective of energy conservation. We have developed fast combinatorial algorithms that are applicable in practice. Moreover, we have conducted the first comprehensive algorithmic study of speed-scaling in massively parallel platforms with heterogeneous architectures. Again we have devised fast algorithms that are relevant in practical environments.

3 In the area of complex networks, as a main contribution, have investigated time-inconsistent planning, a modern and timely problem at the interface of computer science and behavioral economics. We have settled the computational complexity and approximability of basic problems. Moreover, we have introduced novel performance measures and related their expressiveness.

4 We have explored basic graph problems with relations to Internet advertising. Specifically, we have resolved long-standing open problems in online graph coloring. Our research establishes tight lower bounds on the performance of deterministic and randomizedalgorithms for fundamental graph classes, including trees, planar, bipartite, chordal, inductive, bounded-treewidth and disk graphs. Additionally, we have investigated storyboarding, an advanced ad format, where advertisers wish to present sequences of ads (stories) uninterruptedly on a major ad position of a web page. We have devised simplified and significantly improved online algorithms that also reduce the number of story preemptions.

Final results

In the first funding period, we have developed techniques in the modern research direction entitled â€œBeyond Worst-Case Analysisâ€. Classical worst-case analysis of algorithms is sometimes overly pessimistic as the performance of a strategy is evaluated in terms of worst-case inputs that might not occur in practice. We have presented new approaches for modeling real-world inputs. For fundamental online problems, these frameworks allow us to obtain results where, for the first time, the theoretically proven and experimentally observed performance guarantees match. Moreover, we have explored the power of relaxed service models, where an algorithm is given some extra power or resources to handle input. We demonstrate that significantly improved performance guarantees can be attained. In the second funding period we will further investigate these research directions, considering in particular the celebrated random-order model. We will focus on classical secretary problems, a basic setting in stopping theory, as well as packing and scheduling problems.

We have modeled fundamental optimization problems in energy conservation so that they are amenable to algorithmic investigations. We have focused on massively parallel systems with heterogeneous architectures and in particular on data centers. During the second project period we will continue this line of research and explore avenues towards a rightsizing of server farms and workload shifting.

We have explored problems at the interface of computer science and behavioral economics. Specifically, we have studied time-inconsistent planning and introduced an array of new concepts towards a computational understanding of present-biased behavior. In the next two years we intend to further study algorithmic problems from a game-theoretic perspective, considering in particular optimization problems in large networks.

We have developed refined analysis techniques that allow us to prove tight bounds for classical online graph coloring. During the second project period we will study a spectrum of online matching problems, which are at the forefront of international algorithms research these day. Thsee problems are also highly relevant in Internet advertising.