Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Paul Spirakis:

TR09-096 | 7th October 2009
Haralampos Tsaknakis, Paul Spirakis

A Graph Spectral Approach for Computing Approximate Nash Equilibria

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 >>>

TR07-067 | 22nd May 2007
Paul Spirakis, haralampos tsaknakis

Computing 1/3-approximate Nash equilibria of bimatrix games in polynomial time.

Revisions: 2

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 >>>

TR06-081 | 19th May 2006
Spyros Kontogiannis, Panagiota Panagopoulou, Paul Spirakis

Polynomial Algorithms for Approximating Nash Equilibria of Bimatrix Games

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 >>>

TR05-056 | 25th April 2005
Alexis Kaporis, Efpraxia Politopoulou, Paul Spirakis

The Price of Optimum in Stackelberg Games

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 >>>

TR03-016 | 15th January 2003
Dimitrios Koukopoulos, Marios Mavronicolas, Paul Spirakis

FIFO is Unstable at Arbitrarily Low Rates

Revisions: 1

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 >>>

TR01-099 | 1st October 2001
Dimitrios Koukopoulos, Sotiris Nikoletseas, Paul Spirakis

The Range of Stability for Heterogeneous and FIFO Queueing Networks

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 >>>

TR00-011 | 27th January 2000
Sotiris Nikoletseas, Paul Spirakis

Efficient Communication Establishment in Extremely Unreliable Large Networks

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 >>>

TR00-007 | 14th December 1999
Pavlos S. Efraimidis, Paul Spirakis

Randomized Approximation Schemes for Scheduling Unrelated Parallel Machines

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 >>>

TR98-049 | 10th July 1998
Dimitris Fotakis, Paul Spirakis

Random Walks, Conditional Hitting Sets and Partial Derandomization

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 >>>

TR98-031 | 4th May 1998
Dimitris Fotakis, Paul Spirakis

Graph Properties that Facilitate Travelling

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 >>>

ISSN 1433-8092 | Imprint