Abdolhamid Ghodselahi
Albert-Ludwigs-Universität
Institut für Informatik
Georges-Köhler-Allee 106
D - 79110 Freiburg im Breisgau
Room:
Phone:
Fax:
106-00-004
+49 761 - 203 67416
+49 761 - 203 67412

Email: hghods@cs.uni-freiburg.de

Background
I am a PhD candidate in the Department of Computer Science at the University of Freiburg. I am advised by Prof. Dr. Fabian Kuhn . I have a M.Sc. in Algorithms and Computation from Tehran University. My main advisor was Prof. Dr. Mohammad Ali Safari . I received a Bachelor's degree in Software Engineering from Kharazmi University (previously known as Tarbiat Moallem University of Tehran).

Research Interests
I mainly study distributed and centralized algorithms for online problems (specifically resource allocation problems) in which the entire input is not fed into a system from the beginning. However it arrives as a sequence of input pieces and the system must react in response to each incoming piece without any knowledge of the future. In particular, I am interested to provide competitive analysis for these problems.

Teaching Assistance

Publications
Years: 2015 | show all Conference papers Mohamad Ahmadi, Abdolhamid Ghodselahi, Fabian Kuhn, Anisur Rahaman MollaThe Cost of Global Broadcast in Dynamic Radio Networks 2015 19th Int. Conf. on Principles of Distributed Systems (OPODIS), Rennes, France » show abstract « hide abstract Abstract We study the single-message broadcast problem in dynamic radio
networks. We show that the time complexity of the problem depends on
the amount of stability and connectivity of the dynamic network
topology and on the adaptiveness of the adversary providing the
dynamic topology. More formally, we model communication using the
standard graph-based radio network model. To model the dynamic
network, we use a variant of the synchronous dynamic graph model
introduced in [Kuhn et al., STOC 2010]. For integer parameters
$T\geq 1$ and $k\geq 1$, we call a dynamic graph $T$-interval
$k$-connected if for every interval of $T$ consecutive rounds, there
exists a $k$-vertex-connected stable subgraph. Further, for an
integer parameter $\tau\geq 0$, we say that the adversary providing
the dynamic network is $\tau$-oblivious if for constructing the
graph of some round $t$, the adversary has access to all the
randomness (and states) of the algorithm up to round $t-\tau$.
As our main result, we show that for any $T\geq 1$, any $k\geq 1$,
and any $\tau\geq 1$, for a $\tau$-oblivious adversary, there is a
distributed algorithm to broadcast a single message in time
$O\big(\big(1+\frac{n}{k\cdot \min \set{\tau,T}} \big ) \cdot n \log^3
n \big)$. We further show that even for large interval
$k$-connectivity, efficient broadcast is not possible for the usual
adaptive adversaries. For a $1$-oblivious adversary, we show that
even for any $T\leq (n/k)^{1-\eps}$ (for any constant $\eps > 0$) and for
any $k\geq 1$, global broadcast in $T$-interval $k$-connected
networks requires at least $\Omega(n^2/k^2\log n)$ time. Further,
for a $0$-oblivious adversary, broadcast cannot be solved in
$T$-interval $k$-connected networks as long as $T<n-k$. Abdolhamid Ghodselahi, Fabian KuhnServing Online Requests with Mobile Servers 2015 26th Int. Symp. on Algorithms and Computation (ISAAC), Nagoya, Japan » show abstract « hide abstract Abstract We study an online problem in which mobile servers have to be moved
in order to efficiently serve a set of online requests. More
formally, there is a set of $n$ nodes and a set of $k$ mobile
servers that are placed at some of the nodes. Each node can
potentially host several servers and the servers can be moved
between the nodes. There are requests $1,2, \ldots$ that are
adversarially issued at nodes one at a time, where a request issued
at time $t$ needs to be served at all times $t' \geq t$. The cost
for serving the requests is a function of the number of servers and
requests at the different nodes. The requirements on how to serve
the requests are governed by two parameters $\alpha\geq 1$ and
$\beta\geq 0$. An algorithm needs to guarantee that at all times,
the total service cost remains within a multiplicative factor
$\alpha$ and an additive term $\beta$ of the current optimal service
cost.
We consider online algorithms for two different minimization
objectives. We first consider the natural problem of minimizing the
total number of server movements. We show that in this case for
every $k$, the competitive ratio of every deterministic online
algorithm needs to be at least $\Omega(n)$. Given this negative
result, we then extend the minimization objective to also include
the current service cost. We give almost tight bounds on the
competitive ratio of the online problem where one needs to minimize
the sum of the total number of movements and the current service
cost. In particular, we show that at the cost of an additional
additive term which is roughly linear in $k$, it is possible to
achieve a multiplicative competitive ratio of $1+\eps$ for every
constant $\eps>0$.