Skip to main content
main-content

Über dieses Buch

This Festschrift volume is published in honor of Professor Paul G. Spirakis on the occasion of his 60th birthday. It celebrates his significant contributions to computer science as an eminent, talented, and influential researcher and most visionary thought leader, with a great talent in inspiring and guiding young researchers.

The book is a reflection of his main research activities in the fields of algorithms, probability, networks, and games, and contains a biographical sketch as well as essays and research contributions from close collaborators and former PhD students.

Inhaltsverzeichnis

Frontmatter

Part I

Frontmatter

A Glimpse at Paul G. Spirakis

Abstract
Paul Spirakis is an eminent, talented, and influential researcher that contributed significantly to computer science. This article is a modest attempt of a biographical sketch of Paul, which we drafted with extreme love and honor.
Ioannis Chatzigiannakis, Dimitris Fotakis, Spyros Kontogiannis, Othon Michail, Sotiris Nikoletseas, Grammati Pantziou, Christos Zaroliagis

The Reality Game Theory Imposes (Short Summary)

Abstract
I was lucky to be exposed to game theory by Paul Spirakis, moreover to have my first PhD student, Elad Schiller staying with Paul as his PostDoc. It was a great opportunity to examine and think about the combination of philosophical and social considerations when examining the rigorous mathematical settings, results and implications of Game Theory. Implications, that should reflect our real life situations. Especially when searching for game theory tools to be used automatically by societies of (users connected to) computers that form a distributed system.
Shlomi Dolev

On Neural Networks and Paul Spirakis

Abstract
“We are our connectome,” this is the tautology du jour. Everything we do, think, remember, say (or write), is merely a projection of our current neural configuration. So, here goes.
Christos H. Papadimitriou

Concurrency, Parallelism, Asynchrony and Life

Abstract
This is a brief essay in honor of Paul Spirakis on the occasion of his 60th birthday, and a prologue for the articles of this volume titled “Of concurrent data structures and iterations” and “Data-streaming and concurrent data-object co-design: overview and algorithmic challenges”.
Marina Papatriantafilou

Invited Talks

Frontmatter

Rationality Authority for Provable Rational Behavior

Abstract
Players in a game are assumed to be totally rational and absolutely smart. However, in reality all players may act in non-rational ways and may fail to understand and find their best actions. In particular, participants in social interactions, such as lotteries and auctions, cannot be expected to always find by themselves the “best-reply” to any situation. Indeed, agents may consult with others about the possible outcome of their actions. It is then up to the counselee to assure the rationality of the consultant’s advice. We present a distributed computer system infrastructure, named rationality authority, that allows safe consultation among (possibly biased) parties. The parties’ advices are adapted only after verifying their feasibility and optimality by standard formal proof checkers. The rationality authority design considers computational constraints, as well as privacy and security issues, such as verification methods that do not reveal private preferences. Some of the techniques resembles zero-knowledge proofs. A non-cooperative game is presented by the game inventor along with its (possibly intractable) equilibrium. The game inventor advises playing by this equilibrium and offers a checkable proof for the equilibrium feasibility and optimality. Standard verification procedures, provided by trusted (according to their reputation) verification procedures, are used to verify the proof. Thus, the proposed rationality authority infrastructure facilitates the applications of game theory in several important real-life scenarios by the use of computing systems.
Shlomi Dolev, Panagiota N. Panagopoulou, Mikaël Rabie, Elad M. Schiller, Paul G. Spirakis

Weighted Boolean Formula Games

Abstract
We introduce weighted boolean formula games (WBFG) as a new class of succinct games. Each player has a set of boolean formulas she wants to get satisfied; the formulas involve a ground set of boolean variables each of which is controlled by some player. The payoff of a player is a weighted sum of the values of her formulas. We consider both pure equilibria and their refinement of payoff-dominant equilibria [34], where every player is no worse-off than in any other pure equilibrium. We present both structural and complexity results:
  • We consider mutual weighted boolean formula games (MWBFG), a subclass of WBFG making a natural mutuality assumption on the formulas of players. We present a very simple exact potential for MWBFG. We establish a polynomial monomorphism from certain classes of weighted congestion games to subclasses of WBFG and MWBFG, respectively, indicating their rich structure.
  • We present a collection of complexity results about decision (and search) problems for both pure and payoff-dominant equilibria in WBFG. The precise complexities depend crucially on five parameters: (i) the number of players; (ii) the number of variables per player; (iii) the number of formulas per player; (iv) the weights in the payoff functions (whether identical or not), and (v) the syntax of the formulas. These results imply that, unless the polynomial hierarchy collapses, decision (and search) problems for payoff-dominant equilibria are harder than for pure equilibria.
Marios Mavronicolas, Burkhard Monien, Klaus W. Wagner

On the Implementation of Combinatorial Algorithms for the Linear Exchange Market

Abstract
Duan and Mehlhorn and Duan, Garg, and Mehlhorn presented polynomial time combinatorial algorithms [DM13, DGM15] for the computation of equilibrium prices in linear exchange markets. I am currently implementing these algorithms. I discuss the questions that I hope to answer through the implementation.
Kurt Mehlhorn

Regular Contributions

Frontmatter

On Radiocoloring Hierarchically Specified Planar Graphs: $\mathcal{PSPACE}$ -completeness and Approximations

Abstract
Hierarchical specifications of graphs have been widely used in many important applications, such as VLSI design, parallel programming and software engineering. A well known hierarchical specification model, considered in this work, is that of Lengauer [21, 22], referred to as L-specifications. In this paper we discuss a restriction on the L-specifications resulting to graphs which we call Well-Separated (WS). This class is recognized in polynomial time.
In this work we study the Radiocoloring Problem (RCP) on WS L-specified hierarchical planar graphs. The optimization version of RCP studied here, consists in assigning colors to the vertices of a graph, such that any two vertices of distance at most two get different colors. The objective here is to minimize the number of colors used.
We first show that RCP is \(\mathcal{PSPACE}\)-complete for WS L-specified hierarchical planar graphs. Second, we present a polynomial time 3-approximation algorithm as well as a more efficient asymptotic 10/3-approximation algorithm for RCP on graphs of this class. We note that, the best currently known approximation ratio for the RCP on ordinary (non-hierarchical) planar graphs of general degree is 5 / 3 asymptotically ([27, 28]).
Maria Andreou, Dimitris Fotakis, Vicky Papadopoulou Lesta, Sotiris Nikoletseas, Paul Spirakis

Performance Evaluation of Routing Mechanisms for VANETs in Urban Areas

Abstract
Mobile Ad hoc Networks (MANETs) and especially Vehicular Ad hoc Networks (VANETs) have recently gained large interest and their performance is heavily studied. A great challenge in VANETs, especially in an urban setting, is the routing scheme used and the subsequent performance obtained. This work presents an experimental performance evaluation of routing mechanisms in VANETs, using simulation, within an urban Manhattan grid like environment. It also describes and evaluates an enhancement of the Greedy Perimeter Stateless Routing (GPSR) protocol that takes into account the motion of the vehicles and the nature of the urban environment. The simulation results demonstrate that the proposed enhancement to the GPSR protocol manages to significantly increase the delivery ratio without increasing the power consumption; nevertheless, in some cases the improvement on delivery ratio is achieved at the expense of slightly increased end-to-end delay.
Christos Bouras, Vaggelis Kapoulas, Enea Tsanai

Pioneering the Establishment of the Foundations of the Internet of Things

Abstract
In the Internet of Things era, every one of over a trillion everyday items will include at least some ability to store and process information. And, more important, to share that information over the global Internet with the other trillion items. In order to support this technological evolution, among the first problems that were addressed by the research community was that of basic network communication as existing, conventional (Internet-like) networking approaches were either unworkable or impractical. One of the solutions proposed is the so-called “Support Approach” that was proposed in 2000 and rigorously studied using a combination of theoretical and practical research. In this paper we present the main findings and we comment on the research methodology that led to these results.
Ioannis Chatzigiannakis

An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs

Abstract
We present an optimal deterministic O(n)-work parallel algorithm for finding a minimum spanning tree on an n-vertex planar graph. The algorithm runs in \(O(\log n)\) time on a CRCW PRAM and in \(O(\log n\log ^*n)\) time on an EREW PRAM. Our results hold for any sparse graph that is closed under taking of minors, as well as for a class of graphs with non-bounded genus.
Ka Wong Chong, Christos Zaroliagis

Weighted Random Sampling over Data Streams

Abstract
In this work, we present a comprehensive treatment of weighted random sampling (WRS) over data streams. More precisely, we examine two natural interpretations of the item weights, describe an existing algorithm for each case [3, 8], discuss sampling with and without replacement and show adaptations of the algorithms for several WRS problems and evolving data streams.
Pavlos S. Efraimidis

Random Instances of Problems in NP - Algorithms and Statistical Physics

Abstract
One of the most intriguing discoveries made by Erdös and Rényi in the course of their investigating random graphs is the so-called phase transition phenomenona, like the sudden emergence of the giant component. Since then, this kind of phenomena have been observed in many, diverse, areas of combinatorics and discrete mathematics in general. Typically, the notion of phase transition in combinatorics is related to a sudden change in the structural properties of a combinatorial construction, e.g. a (hyper)graph, arithmetic progressions e.t.c. However, it seems that the study of phase transitions goes much further. There is an empirical evidence that certain phase transition phenomena play a prominent role in the performance of algorithms for a lot of natural computational problems. That is, phase transitions are related to the, somehow elusive, notion of computational intractability. The last fifteen-twenty years, there has been serious attempts to put this relation on a mathematically rigorous basis. Our aim is to highlight some of the most central problems that arise in this endeavor.
Charilaos Efthymiou

A Selective Tour Through Congestion Games

Abstract
We give a sketchy and mostly informal overview of research on algorithmic properties of congestion games in the last ten years. We discuss existence of potential functions and pure Nash equilibria in games with weighted players, simple and fast algorithms that reach a pure Nash equilibrium, and efficient approaches to improving the Price of Anarchy.
Dimitris Fotakis

Data-Streaming and Concurrent Data-Object Co-design: Overview and Algorithmic Challenges

Abstract
Processing big volumes of data generated on-line, implies needs to carry out computations on-the-fly, in the streams of data. In parallel data-stream computing, the underlying data objects can provide the means for exchanging the data so that the communication and the work imbalance between the concurrent threads performing the computation are reduced, while the pipeline parallelism is enhanced. By shedding light on the concurrent data objects and their role as articulation points in data-stream processing, we place some cornerstones to analyze the problems, propose appropriate new data structures suitable for a set of functions and identify new key challenges to improve data-stream processing through co-design with fine-grain efficient synchronization combined with the data exchange.
It is interesting to point out that research in distributed computing on multiprocessor efficient and consistent data sharing through fine-grain synchronization emerged from questions in concurrent database-related research; approximately three decades since then, it is interesting to see several returns of the fruits of this expedition, helping with the new problems in the massive-data research domain, with applications in e.g. cyberphysical systems.
Vincenzo Gulisano, Yiannis Nikolakopoulos, Marina Papatriantafilou, Philippas Tsigas

Stability in Heterogeneous Dynamic Multimedia Networks

Abstract
Internet and other multimedia packet-switched networks are heterogeneous due to the simultaneous running (composition) of different contention-resolution protocols over different network hosts and the existence of various types of network links. Also, real networks are dynamic in their nature due to intentional or unintentional changes on network link service rates or tra nsient link failures. Our interest is focused on FIFO compositions with other contention-resolution protocols due to the FIFO popularity for offering best-effort services in packet-switched networks. A packet-switched network is stable, if the number of packets in the network remains bounded at all times against any adversary. We use an enhanced adversarial framework that is based on an adversary that controls packet injection rates, along with packet paths, and manipulates link slowdowns or capacities. Within this framework, we study the impact of specific compositions of FIFO with other protocols on the network stability using as a test-bed specific network topologies which have been proved forbidden for stability for a single protocol, fixed link slowdowns/capacities and packet paths without repeated links/edges. Our results suggest that the instability behavior of a network using FIFO compositions under adversarial attacks, that dynamically change link slowdowns/capacities, is not only maintained, but, also, may become worse than in the case of attacks that do not change slowdowns/capacities or when a single protocol, like FIFO, is employed on all network queues for contention-resolution. We believe that this study can advance the research for the provision of trustworthy heterogeneous networks.
Dimitrios Koukopoulos

Advances in the Parallelization of the Simplex Method

Abstract
The simplex method has been successfully used in solving linear programming problems for many years. Parallel approaches for the simplex method have been extensively studied in the literature due to the intensive computations required, especially for the solution of large linear problems (LPs). In this paper, first a detailed overview is given of the parallelization attempts concerning the standard and the revised simplex method made to date. Next, some of the most recent and significant relevant attempts are selected and presented in more detail along with experimental results. The latter include some impressive results obtained for the revised simplex method over a modern supercomputer, as well as the recent advances in GPU-based related attempts.
Basilis Mamalis, Grammati Pantziou

An Introduction to Temporal Graphs: An Algorithmic Perspective

Abstract
A temporal graph is, informally speaking, a graph that changes with time. When time is discrete and only the relationships between the participating entities may change and not the entities themselves, a temporal graph may be viewed as a sequence \(G_1,G_2\ldots ,G_l\) of static graphs over the same (static) set of nodes V. Though static graphs have been extensively studied, for their temporal generalization we are still far from having a concrete set of structural and algorithmic principles. Recent research shows that many graph properties and problems become radically different and usually substantially more difficult when an extra time dimension in added to them. Moreover, there is already a rich and rapidly growing set of modern systems and applications that can be naturally modeled and studied via temporal graphs. This, further motivates the need for the development of a temporal extension of graph theory. We survey here recent results on temporal graphs and temporal graph problems that have appeared in the Computer Science community.
Othon Michail

Random Surfing Without Teleportation

Abstract
In the standard Random Surfer Model, the teleportation matrix is necessary to ensure that the final PageRank vector is well-defined. The introduction of this matrix, however, results in serious problems and imposes fundamental limitations to the quality of the ranking vectors. In this work, building on the recently proposed NCDawareRank framework, we exploit the decomposition of the underlying space into blocks, and we derive easy to check necessary and sufficient conditions for random surfing without teleportation.
Athanasios N. Nikolakopoulos, John D. Garofalakis

Of Concurrent Data Structures and Iterations

Abstract
Bulk operations on data structures are widely used both on user-level but also on programming language level. Iterations are a good example of such bulk operations. In the sequential setting iterations are easy to design on top of an algorithmic construction of a data structure and is not considered as a challenge. In a concurrent environment, such as a multicore system, the situation is completely different and the issue of extending concurrent data structure designs to support iteration operations opens new research challenges in concurrent algorithmic data structure implementations, with respect to consistency and efficiency. In this paper we take a journey through this young and evolving research topic. More precisely we describe recent advances in the area together with an overview of iteration implementations that have appeared in the research literature as well as in widely-used programming environments and we outline a range of application targets and challenging future directions.
Yiannis Nikolakopoulos, Anders Gidenstam, Marina Papatriantafilou, Philippas Tsigas

On Some Combinatorial Properties of Random Intersection Graphs

Abstract
In this paper, we consider a simple, yet general family of random graph models, namely Random Intersection Graphs (RIGs), which are motivated by applications in secure sensor networks, social networks and many more. In such models there is a universe \(\mathcal{M}\) of labels and each one of n vertices selects a random subset of \(\mathcal{M}\). Two vertices are connected if and only if their corresponding subsets of labels intersect. In particular, we briefly review the state of the art and we present key results from our research on the field, that highlight and take advantage of the intricacies and special structure of random intersection graphs. Finally, we present in more detail a particular result from our research, which concerns maximum cliques in the uniform random intersection graphs model (in which every vertex selects each label independently with some probability p), namely the Single Label Clique Theorem.
Sotiris E. Nikoletseas, Christoforos L. Raptopoulos

Efficient Equilibrium Concepts in Non-cooperative Network Formation

Abstract
We review here some recently proposed models of non-cooperative network creation games where the nodes of a network perform edge swaps in order to improve their communication costs. Our focus is on examining the structure of stable (equilibrium) networks that correspond to efficient notions of equilibria, in the sense that the nodes of the network are able to decide which links to add and which to remove in order to achieve a minimal cost, given the strategies of the other nodes. We also review results on the capability of the network nodes of converging into an equilibrium network by performing local selfish improvement steps.
Panagiota N. Panagopoulou

Simple Parallel Algorithms for Dynamic Range Products

Abstract
We consider here the problem of answering range product queries on an n-node unrooted tree labelled with elements of a semigroup provided with an associative operator only. We present simple parallel dynamic algorithms for one of the weakest models of parallel computation (EREW PRAM). Our main result is an algorithm which answers a query in \(O(\alpha (n))\) time using a single processor after \(O(\log n)\)-time and O(n)-work preprocessing, where \(\alpha (n)\) is the inverse of Ackermann’s function. The data structures set up during preprocessing are updated in \(O(\log n)\) time and \(O(n^\beta )\) work, for any (arbitrarily small) constant \(0<\beta <1\), after a dynamic change in the label of a tree node.
Christos Zaroliagis

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise