Panagiotis Patsilinakos

Dr. Panagiotis Patsilinakos


Research Focus & Metrics

Academic Career Length

7Years (2020-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
30 January 2024 in Algorithms
Verified
Journal Article
Open access
PDF file
Dimitris FotakisDimitris Fotakis
Dimitris Fotakis
PPPanagiotis Patsilinakos
Panagiotis Patsilinakos
EPEleni Psaroudaki
Eleni Psaroudaki
MXMichalis Xefteris
Michalis Xefteris
In this work, we consider the problem of shape-based time-series clustering with the widely used Dynamic Time Warping (DTW) distance. We present a novel two-stage framework based on Sparse Gaussian Modeling. In the first stage, we apply Sparse Gaussian Process Regression and obtain a sparse representation of each time series in the dataset with a logarithmic (in the original length T) number of inducing data points. In the second stage, we apply k-means with DTW Barycentric Averaging (DBA) to the sparsified dataset using a generalization of DTW, which accounts for the fact that each inducing point serves as a representative of many original data points. The asymptotic running time of our Sparse Time-Series Clustering framework is Ω(T2/log2T) times faster than the running time of applying k-means to the original dataset because sparsification reduces the running time of DTW from Θ(T2) to Θ(log2T). Moreover, sparsification tends to smoothen outliers and particularly noisy parts of the original time series. We conduct an extensive experimental evaluation using datasets from the UCR Time-Series Classification Archive, showing that the quality of clustering computed by our Sparse Time-Series Clustering framework is comparable to the clustering computed by the standard k-means algorithm.

11 April 2025 in Proceedings of the AAAI Conference on Artificial Intelligence
Verified
Journal Article
Open access
PDF file
Dimitris FotakisDimitris Fotakis
Dimitris Fotakis
LGLaurent Gourvès
Laurent Gourvès
PPPanagiotis Patsilinakos
Panagiotis Patsilinakos
We consider committee election of k >= 3 (out of m >= k + 1) candidates, where the voters and the candidates are associated with locations on the real line. Each voter’s cardinal preferences over candidates correspond to her distance to the candidate locations, and each voter’s cardinal preferences over committees is defined as her distance to the nearest candidate elected in the committee. We consider a setting where the true distances and the locations are unknown. We can nevertheless have access to degraded information which consists of an order of candidates for each voter. We investigate the best possible distortion (a worst-case performance criterion) w.r.t. the social cost achieved by deterministic committee election rules based on ordinal preferences submitted by n voters and few additional distance queries. We show that for any k >= 3, the best possible distortion of any deterministic rule that uses at most k−3 distance queries cannot be bounded by any function of n, m and k. We present deterministic rules for k-committee election with distortion of O(n) with O(k) distance queries and O(1) with O(k log(n)) distance queries.

3 March 2024 in arXiv
Verified
Preprint
Open access
PDF file
Dimitris FotakisDimitris Fotakis
Dimitris Fotakis
PPPanagiotis Patsilinakos
Panagiotis Patsilinakos
We consider $k$-Facility Location games, where $n$ strategic agents report their locations on the real line, and a mechanism maps them to $k\ge 2$ facilities. Each agent seeks to minimize her distance to the nearest facility. We are interested in (deterministic or randomized) strategyproof mechanisms without payments that achieve a reasonable approximation ratio to the optimal social cost of the agents. To circumvent the inapproximability of $k$-Facility Location by deterministic strategyproof mechanisms, we restrict our attention to perturbation stable instances. An instance of $k$-Facility Location on the line is $\gamma$-perturbation stable (or simply, $\gamma$-stable), for some $\gamma\ge 1$, if the optimal agent clustering is not affected by moving any subset of consecutive agent locations closer to each other by a factor at most $\gamma$. We show that the optimal solution is strategyproof in $(2+\sqrt{3})$-stable instances whose optimal solution does not include any singleton clusters, and that allocating the facility to the agent next to the rightmost one in each optimal cluster (or to the unique agent, for singleton clusters) is strategyproof and $(n-2)/2$-approximate for $5$-stable instances (even if their optimal solution includes singleton clusters). On the negative side, we show that for any $k\ge 3$ and any $\delta > 0$, there is no deterministic anonymous mechanism that achieves a bounded approximation ratio and is strategyproof in $(\sqrt{2}-\delta)$-stable instances. We also prove that allocating the facility to a random agent of each optimal cluster is strategyproof and $2$-approximate in $5$-stable instances. To the best of our knowledge, this is the first time that the existence of deterministic (resp. randomized) strategyproof mechanisms with a bounded (resp. constant) approximation ratio is shown for a large and natural class of $k$-Facility Location instances.

24 February 2020 in arXiv
Verified
Preprint
Open access
PDF file
DFDimitris Fotakis
Dimitris Fotakis
VKVardis Kandiros
Vardis Kandiros
TLThanasis Lianeas
Thanasis Lianeas
NMNikos Mouzakis
Nikos Mouzakis
PPPanagiotis Patsilinakos
Panagiotis Patsilinakos
SSStratis Skoulakis
Stratis Skoulakis
In this work, we seek a more refined understanding of the complexity of local optimum computation for Max-Cut and pure Nash equilibrium (PNE) computation for congestion games with weighted players and linear latency functions. We show that computing a PNE of linear weighted congestion games is PLS-complete either for very restricted strategy spaces, namely when player strategies are paths on a series-parallel network with a single origin and destination, or for very restricted latency functions, namely when the latency on each resource is equal to the congestion. Our results reveal a remarkable gap regarding the complexity of PNE in congestion games with weighted and unweighted players, since in case of unweighted players, a PNE can be easily computed by either a simple greedy algorithm (for series-parallel networks) or any better response dynamics (when the latency is equal to the congestion). For the latter of the results above, we need to show first that computing a local optimum of a natural restriction of Max-Cut, which we call \emph{Node-Max-Cut}, is PLS-complete. In Node-Max-Cut, the input graph is vertex-weighted and the weight of each edge is equal to the product of the weights of its endpoints. Due to the very restricted nature of Node-Max-Cut, the reduction requires a careful combination of new gadgets with ideas and techniques from previous work. We also show how to compute efficiently a $(1+\eps)$-approximate equilibrium for Node-Max-Cut, if the number of different vertex weights is constant.