Elias Koutsoupias (UoA)
TBA.
On a generalized graph coloring/batch scheduling problem- Giorgio Lucarelli (AUEB)
We study a batch scheduling problem where jobs are no more independent but they are subject to (in)compatibility constraints described by an underlying graph. The problem is equivalent to a generalized weighted graph coloring problem. We study the frontier between polynomial and NP-variants of the problem as well as the approximability of NP-hard variants.
(Joint work with Ioannis Milis and Vangelis Th. Paschos)
Buy-at-bulk network design with protection- Spyridon Antonakopoulos (Columbia)
We consider approximation algorithms for buy-at-bulk network design, with the additional constraint that demand pairs be protected against edge or node failures in the network. In practice, the most popular model used in high speed telecommunication networks for protection against failures is the so-called 1+1 model. In this model, two edge or node-disjoint paths are provisioned for each demand pair. We obtain the first non-trivial approximation algorithms for buy-at-bulk network design in the 1+1 model for both edge and node-disjoint protection requirements. Our results are for the single-cable cost model, which is prevalent in optical networks. More specifically, we present a constant-factor approximation for the single-sink case and an $O(\log^3 n)$ approximation for the multi-commodity case. These results are of interest for practical applications and also suggest several new challenging theoretical problems.
(Joint work with Chandra Chekuri, Bruce Shepherd and Lisa Zhang)
Full abstraction for nominal general references- Nikos Tzevelekos (Oxford)
Game semantics has been used with considerable success in formulating fully abstract semantics for languages with higher-order procedures and a wide range of computational effects. Recently, nominal games have been proposed for modeling functional languages with names. These are ordinary games cast in the theory of nominal sets developed by Pitts and Gabbay. Here we take nominal games one step further, by developing a fully abstract semantics for a language with nominal general references.
A lower bound of $1+\phi$ for truthful scheduling mechanisms- Aggelina Vidali (UoA)
We give an improved lower bound for the approximation ratio of truthful mechanisms for the unrelated machines scheduling problem. The mechanism design version of the problem which was proposed and studied in a seminal paper of Nisan and Ronen is at the core of the emerging area of Algorithmic Game Theory. The new lower bound $1+\phi\approx 2.618$ is a step towards the final resolution of this important problem.
(Joint work with Elias Koutsoupias)
Locality and location awareness- Evangelos Kranakis (Carleton)
The nature of ad hoc networking imposes an additional requirement that algorithms should be {\em local} in the sense that messages propagate only a constant number of hops and each host makes decisions based solely on information obtained from hosts located a constant (independent of the size of the network) number of steps away from it. We will discuss the interaction between local computation and global communication in such systems and give an overview of methods that are more robust for dynamically changing ad hoc networks, including routing, simplifying the network infrastructure (spanners), channel alocation (coloring), and clustering (dominating sets).
Non-polynomial approximation? Why not?- Vangelis Paschos (Paris-Dauphine)
In this paper we address a somewhat non-conventional question. \textit{Does non-polynomial approximation make sense?} We discuss how the areas of polynomial approximation and of worst-case complexity of exact algorithms for \textbf{NP}-hard problems can be matched in order that approximation ratios, impossible to be achieved by polynomial algorithms, can be obtained by efficient (though exponential) algorithms with worst-case complexity considerably lower than the one of exact computation. We first give examples showing how basic methods from exact computation can be used in order to get ``good'' approximation ratios for \is{}, forbidden for polynomial algorithms, with non-trivial worst-case complexity-bounds. Next, we make a more systematic study of \is{} and of another paradigmatic problem, the \vc{}.
(Joint work with Nicolas Bourgeois and Bruno Escoffier)
On the semantic approaches to boolean grammars- Christos Nomikos (UoI)
Boolean grammars extend context-free grammars by allowing conjunction and negation in rule bodies. This new formalism appears to be quite expressive and still efficient from a parsing point of view. Therefore, it seems reasonable to hope that boolean grammars can lead to more expressive tools that can facilitate the compilation process of modern programming languages. One important aspect concerning the theory of boolean grammars is their semantics. More specifically, the existence of negation makes it difficult to define a simple derivation-style semantics (such as for example in the case of context-free grammars). There have already been proposed a number of different semantic approaches in the literature. The purpose of this paper is to present the basic ideas behind each method and identify certain interesting problems that can be the object of further study in this area.
(Joint work with Vassilis Kountouriotis and Panos Rondogiannis)
On the performance of congestion games for optimum satisfiability problems- Aristotelis Giannakos (Paris-Dauphine)
We introduce and study a congestion game having MAX SAT as an underlying structure and show that its price of anarchy is $1/2$. The main result is a redesign of the game leading to an improved price of anarchy of $2/3$ from which we derive a non oblivious local search algorithm for MAX SAT with locality gap $2/3$. A similar congestion MIN SAT game is also studied.
(Joint work with L. Gourvès, J. Monnot and V. Paschos)
Maximizing the guarded boundary of an art gallery is apx complete- Christodoulos Fragoudakis (NTUA)
In the Art Gallery problem, given is a polygonal gallery and the goal is to guard the gallery's interior or walls with a number of guards that must be placed strategically in the interior, on walls or on corners of the gallery. Here we consider a more realistic version: exhibits now have size and may have different costs. Moreover the meaning of guarding is relaxed: we use a new concept, that of watching an expensive art item, i.e. overseeing a part of the item. The main result of the paper is that the problem of maximizing the total value of a guarded weighted boundary is APX-complete. This is shown by an appropriate "gap-preserving" reduction from the Max-5-occurrence-3-Sat problem. We also show that this technique can be applied to a number of maximization variations of the art gallery problem. In particular we consider the following problems: given a polygon with or without holes and k available guards, maximize a) the length of walls guarded and b) the total cost of paintings watched or overseen. We prove that all the above problems are APX-complete.
(Joint work with Euripides Markou and Stathis Zachos)
Reliable routings in networks with generalized link failure events- Stamatis Stefanakos (Rome "La Sapienza")
We study routing problems in networks that require guaranteed reliability against multiple correlated link failures. We consider two different routing objectives: The first ensures "local reliability," i.e. the goal is to route so that each connection in the network is as reliable as possible. The second ensures "global reliability," i.e. the goal is to route so that as few as possible connections are affected by any possible failure. We exhibit a trade-off between the two objectives and resolve their complexity and approximability for several classes of networks. Furthermore, we propose approximation algorithms and heuristics. We perform experiments to evaluate the heuristics against optimal solutions that are obtained using an integer linear programming solver. We also investigate up to what degree the routing trade-offs occur in randomly generated instances.
On the complexity of Nash equilibria and other fixed point problems
- Mihalis Yannakakis (Columbia)
A wide variety of problems from various fields can be cast in the form of finding a solution to a fixed point equation. Examples include Nash equilibria in games, price equilibria, computing the value of stochastic games, probabilities of branching processes, stochastic grammars, recursive Markov chains, and others. In many of these situations, even though the input data are finite and discrete, the underlying models are continuous and the desired solutions are real-valued. What does it mean to compute a solution in such a case? We discuss this question, present a framework, and discuss the complexity of the associated computational problems.
(Joint work with Kousha Etessami)
Introduction to quantum information theory- Iordanis Kerenidis (CNRS)
Quantum computation and information studies how information is encoded in nature according to the laws of quantum mechanics and what this means for its computational power. Although, it is a rather new research area, there have been numerous surprising results, for example Shor's algorithm for factoring large numbers and the existence of unconditionally secure key distribution, that make quantum information a very exciting and fundamental research field.
In this talk, we give an introduction to the theory of quantum information by drawing comparisons to classical probability theory. We start by defining the carrier of quantum information, the quantum bit, and proceed to describe a notion of entropy for quantum states. Quantum information theory is a rich mathematical theory that can also be used as a powerful tool for the study of classical information.
Connectivity in ad-hoc networks with selfish nodes- Euripides Markou (McMaster)
In multihop wireless networks, the nodes are selfish, in that they try to maximize their own utility without any regards for the overall network-wide outcome. Since a successful transmission between a pair of nodes requires the cooperation of intermediate nodes in order for the transmitted packets to reach their destination, there have been protocols that offer cooperation incentives to nodes. One such family of incentive protocols are the so-called reputation-based protocols. The basic idea is to identify uncooperative behavior, and punish misbehaving nodes until they start cooperating.
Inspired by the CONFIDANT protocol~\cite{confidant}, we define and study a basic reputation-based protocol. Its reputation mechanism is implemented through the ability of any node to define a threshold of tolerance for any of its neighbors, and to cut the connection to any of these neighbors that refuse to forward an amount of flow above that threshold. The main question we would like to address is whether one can set the initial conditions so that the system reaches an equilibrium state where a non-zero amount of every commodity is routed. This could be important in emergency situations, where all nodes need to be able to communicate even with a small bandwidth. Following a standard approach, we model this protocol as a game, and we give necessary and sufficient conditions for the existence of non-trivial Nash equilibria and for the existence of connected Nash equilibria. We note that it is not always necessary for all the flow originating at a node to reach its destination at equilibrium. For example, a node may be using unsuccessful flow in order to effect changes in a distant part of the network that will prove quite beneficial to it. We show that we can decide in polynomial time whether there exists a connected Nash equilibrium without unsuccessful flows. In that case we calculate (in polynomial time) initial values that impose such an equilibrium on the network. On the negative side, we prove that it is NP-hard to decide whether a connected Nash equilibrium exists in general (i.e., with some nodes using unsuccessful flows at the equilibrium).
(Joint work with George Karakostas)
Integrality gaps of 2-o(1) for vertex cover SDPs in the Lovasz-Schrijver hierarchy- Costis Georgiou (Toronto)
Linear and semidefinite programming are highly successful approaches for obtaining good approximations for NP-hard optimization problems. For example, breakthrough approximation algorithms for MAX CUT and SPARSEST CUT use semidefinite programming.
Perhaps the most prominent NP-hard problem whose exact approximation factor is still unresolved is VERTEX COVER. PCP-based techniques of Dinur and Safra show that it is not possible to achieve a factor better than 1.36; on the other hand no known algorithm does better than the factor of 2 achieved by the simple greedy algorithm. Furthermore, there is a widespread belief that SDP techniques are the most promising methods available for improving upon this factor of 2.
Following a line of study initiated by Arora et al., our aim is to show that a large family of LP and SDP based algorithms fail to produce an approximation for VERTEX COVER better than 2. Lovász and Schrijver introduced the systems $LS_0$, $LS$, and $LS_+$ that naturally capture large classes of LP and SDP relaxations. The strongest of these systems, $LS_+$, captures the celebrated SDP-based algorithms for MAX CUT and SPARSEST CUT mentioned above.
We prove an integrality gap of $2-o(1)$ for VERTEX COVER SDPs resulting from tightening the standard LP relaxation with $\Omega(\sqrt{\log n/\log\log n})$ rounds of $LS_+$. While tight integrality gaps for VERTEX COVER were known for the weaker $LS$ system, previous results did not preclude a polynomial-time $2-\Omega(1)$ approximation algorithm based on $LS_+$, even when restricted to only two rounds of $LS_+$ tightenings.
(Joint work with Avner Magen, Toniann Pitassi and Iannis Tourlakis)
New algorithms for approximate Nash equilibria in bimatrix games- Vangelis Markakis (CWI)
We consider the problem of computing additively approximate Nash equilibria in non- cooperative two-player games. We provide a new polynomial time algorithm that achieves an approximation guarantee of 0.36392. Our work improves the previously best known (0.38197 + \epsilon)-approximation algorithm of Daskalakis, Mehta and Papadimitriou.
First, we provide a simpler algorithm, which also achieves 0.38197. This algorithm is then tuned, improving the approximation error to 0.36392. Our method is relatively fast, as it requires solving only one linear program and it is based on using the solution of an auxiliary zero-sum game as a starting point.
(Joint work with Hartwig Bosse and Jaroslaw Byrka)
Randomized and approximation algorithms for blue-red matching- Aris Pagourtzis (NTUA)
We introduce the BLUE-RED MATCHING problem: given a graph with red and blue edges, and a bound $w$, find a maximum matching consisting of at most $w$ edges of each color. We show that BLUE-RED MATCHING is at least as hard as the problem EXACT MATCHING (Papadimitriou and Yannakakis, 1982), for which it is still open whether it can be solved in polynomial time. We present an RNC algorithm for this problem as well as two fast approximation algorithms. We finally show the applicability of our results to the problem of routing and assigning wavelengths to a maximum number of requests in all-optical rings.
(Joint work with Christos Nomikos and Stathis Zachos)
Graph searching in a crime wave- David Richerby (UoA)
We define helicopter cop and robber games with multiple robbers, extending previous research, which only considered the pursuit of a single robber. We show that the game with many robbers is non-monotone: that is, fewer cops are needed if the robbers are allowed to reoccupy positions that were previously unavailable to them. We prove that the main parameter emerging from the game, which we denote ${\bf sn}(G,r)$, captures a hierarchy of parameters between proper pathwidth and proper treewidth. We characterize the parameter completely for trees and give an upper bound for general graphs.
(Joint work with Dimitrios M. Thilikos)
Proof-infused streams: enabling authentication of sliding window queries on streams- George Kollios (Boston)
As computer systems are essential components of many critical commercial services, the need for secure online transac- tions is now becoming evident. The demand for such applications, as the market grows, exceeds the capacity of individual businesses to provide fast and reliable services, making outsourcing technologies a key player in alleviating issues of scale. Consider a stock broker that needs to provide a real-time stock trading monitoring service to clients. Since the cost of multicasting this information to a large audience might become prohibitive, the broker could outsource the stock feed to third-party providers, who are in turn responsible for forwarding the appropriate sub-feed to clients. Evidently, in critical applications the integrity of the third-party should not be taken for granted. In this work we study a variety of authentication algorithms for selection and aggregation queries over sliding windows. Our algorithms enable the end-users to prove that the results provided by the third-party are correct, i.e., equal to the results that would have been computed by the original provider. Our solutions are based on Merkle hash trees over a forest of space partitioning data structures, and try to leverage key features, like update, query, signing, and authentication costs. We present detailed theoretical analysis for our solutions and empirically evaluate the proposed techniques.
(Joint work with Feifei Li, Ke Yi and Marios Hadjieleftheriou)
On the complexity of real solving bivariate polynomial systems- Elias Tsigaridas (INRIA-LORIA Lorraine)
We consider the problem of exact real solving of well-constrained, bivariate systems of relatively prime polynomials. The main problem is to compute all common real roots in isolating interval representation, and to determine their intersection multiplicities. We present three algorithms and their asymptotic bit complexity, obtaining a bound of $O~(N^{14})$ for the purely projection-based method, and $O~(N^{12})$ for two subresultants-based methods: these ignore polylogarithmic factors, and $N$ bounds the degree and the bitsize of the polynomials. The previous record bound was $O~(N^{14})$.
(Joint work with Dimitris Diochnos and Ioannis Emiris)
Mechanism design for fractional scheduling on unrelated machines- Giorgos Christodoulou (Max-Planck)
TBA.
(Joint work with Elias Koutsoupias and Annamária Kovács)
Selfish data replication on clustered network hierarchies- Orestis Telelis (U d' Evry)
We study implications of selfish behavior on total bandwidth consumption over a network, where each user chooses autonomously to replicate locally frequently accessed information objects, up to constrained local storage capacity, so as to minimize its individual bandwidth consumption. We formulate a related strategic game for which we motivate and prove existence of pure strategy Nash equilibria on balanced hierarchically clustered networks. We prove tight bounds on the Prices of Anarchy and Stability, comment on preliminary experiments, and discuss related open problems.
(Joint work with Gerasimos G. Pollatos and Vassilis Zissimopoulos)
Approximate cycle bases- Dimitris Michail (Max-Planck-Institute für Informatik)
TBA.
The densest k-subgraph problem on chordal graphs- Maria Liazi (UoA)
The Densest k-Subgraph (DkS) problem asks for a k-vertex subgraph of a given graph with the maximum number of edges. The DkS problem is NP-hard even for special graph classes including bipartite, planar, comparability and chordal graphs, while no constant approximation algorithm is known for any of these classes. In this paper we present a 3-approximation algorithm for the class of chordal graphs. The analysis of our algorithm is based on a graph theoretic lemma of independent interest.
(Joint work with Ioannis Milis and Vassilis Zissimopoulos)