All reports by Author Paul Spirakis:

__
TR09-096
| 7th October 2009
__

Haralampos Tsaknakis, Paul Spirakis#### A Graph Spectral Approach for Computing Approximate Nash Equilibria

__
TR07-067
| 22nd May 2007
__

Paul Spirakis, haralampos tsaknakis#### Computing 1/3-approximate Nash equilibria of bimatrix games in polynomial time.

Revisions: 2

__
TR06-081
| 19th May 2006
__

Spyros Kontogiannis, Panagiota Panagopoulou, Paul Spirakis#### Polynomial Algorithms for Approximating Nash Equilibria of Bimatrix Games

__
TR05-056
| 25th April 2005
__

Alexis Kaporis, Efpraxia Politopoulou, Paul Spirakis#### The Price of Optimum in Stackelberg Games

__
TR03-016
| 15th January 2003
__

Dimitrios Koukopoulos, Marios Mavronicolas, Paul Spirakis#### FIFO is Unstable at Arbitrarily Low Rates

Revisions: 1

__
TR01-099
| 1st October 2001
__

Dimitrios Koukopoulos, Sotiris Nikoletseas, Paul Spirakis#### The Range of Stability for Heterogeneous and FIFO Queueing Networks

__
TR00-011
| 27th January 2000
__

Sotiris Nikoletseas, Paul Spirakis#### Efficient Communication Establishment in Extremely Unreliable Large Networks

__
TR00-007
| 14th December 1999
__

Pavlos S. Efraimidis, Paul Spirakis#### Randomized Approximation Schemes for Scheduling Unrelated Parallel Machines

__
TR98-049
| 10th July 1998
__

Dimitris Fotakis, Paul Spirakis#### Random Walks, Conditional Hitting Sets and Partial Derandomization

__
TR98-031
| 4th May 1998
__

Dimitris Fotakis, Paul Spirakis#### Graph Properties that Facilitate Travelling

Haralampos Tsaknakis, Paul Spirakis

We present a new methodology for computing approximate Nash equilibria for two-person non-cooperative games based

upon certain extensions and specializations of an existing optimization approach previously used for the derivation of fixed approximations for this problem. In particular, the general two-person problem is reduced to an indefinite quadratic programming problem ...
more >>>

Paul Spirakis, haralampos tsaknakis

In this paper we propose a methodology for determining approximate Nash equilibria of non-cooperative bimatrix games and, based on that, we provide a polynomial time algorithm that computes $\frac{1}{3} + \frac{1}{p(n)} $ -approximate equilibria, where $p(n)$ is a polynomial controlled by our algorithm and proportional to its running time. The ... more >>>

Spyros Kontogiannis, Panagiota Panagopoulou, Paul Spirakis

We focus on the problem of computing an $\epsilon$-Nash equilibrium of a bimatrix game, when $\epsilon$ is an absolute constant.

We present a simple algorithm for computing a $\frac{3}{4}$-Nash equilibrium for any bimatrix game in strongly polynomial time and

we next show how to extend this algorithm so as to ...
more >>>

Alexis Kaporis, Efpraxia Politopoulou, Paul Spirakis

Consider a system M of parallel machines, each with a strictly increasing and differentiable load dependent latency function. The users of such a system are of infinite number and act selfishly, routing their infinitesimally small portion of the total flow r they control, to machines of currently minimum delay. It ... more >>>

Dimitrios Koukopoulos, Marios Mavronicolas, Paul Spirakis

In this work, we study the stability of the {\sf FIFO} ({\sf

First-In-First-Out}) protocol in the context of Adversarial

Queueing Theory. As an important intermediate step, we consider

{\em dynamic capacities}, where each network link capacity may

arbitrarily take on values in the two-valued set of integers

$\{1,C\}$ for $C>1$ ...
more >>>

Dimitrios Koukopoulos, Sotiris Nikoletseas, Paul Spirakis

In this paper, we investigate and analyze for the first time the

stability properties of heterogeneous networks, which use a

combination of different universally stable queueing policies for

packet routing, in the Adversarial Queueing model. We

interestingly prove that the combination of SIS and LIS policies,

LIS and NTS policies, ...
more >>>

Sotiris Nikoletseas, Paul Spirakis

We consider here a large network of $n$ nodes which supports

only the following unreliable basic communication primitive:

when a node requests communication then this request

{\em may fail}, independently of other requests, with probability

$f<1$. Even if it succeeds, the request is answered by returning

a stable link to ...
more >>>

Pavlos S. Efraimidis, Paul Spirakis

The problem of Scheduling $n$ Independent Jobs

on $m$ Unrelated Parallel Machines, when $m$

is fixed, is considered. The standard problem

of minimizing the makespan of the schedule

(SUM) and the bicriteria problem of scheduling

with bounded makespan and cost (SUMC), are

addressed, and randomized fully linear time

more >>>

Dimitris Fotakis, Paul Spirakis

In this work we use random walks on expanders in order to

relax the properties of hitting sets required for partially

derandomizing one-side error algorithms. Building on a well-known

probability amplification technique [AKS87,CW89,IZ89], we use

random walks on expander graphs of subexponential (in the

random bit complexity) size so as ...
more >>>

Dimitris Fotakis, Paul Spirakis

In this work, we study two special cases of the metric Travelling Salesman

Problem, Graph TSP and TSP(1,2). At first, we show that dense instances of

TSP(1,2) and Graph TSP are essentially as hard to approximate as general

instances of TSP(1,2).

Next, we present an NC algorithm for TSP(1,2) that ... more >>>