Pathwidth, trees, and random embeddings (2009)
Lee, James R., Sidiropoulos, Anastasios
We prove that, for every $k=1,2,...,$ every shortest-path metric on a graph of pathwidth $k$ embeds into a distribution over random trees with distortion at most $c$ for some $c=c(k)$. A well-known...
Circular Partitions with Applications to Visualization and (2009)
Krzysztof Onak, Anastasios Sidiropoulos
We introduce a hierarchical partitioning scheme of the Euclidean plane, called circular partitions. Such a partition consists of a hierarchy of convex polygons, each having small aspect ratio, and...
Probabilistic embeddings of bounded genus graphs into planar graphs (2008)
Piotr Indyk, Anastasios Sidiropoulos
Ì��ÓÒ×Ø�ÒØC�×�ÐÐ��Ø����×ØÓÖØ�ÓÒÓ�Ø���Ñ�����Ò �...
On Distributing Symmetric Streaming Computations (2008)
Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein
A common approach for dealing with large data sets is to stream over the input in one pass, and perform computations using sublinear resources. For truly massive data sets, however, even making a...
Mihai Bădoiu, Julia Chuzhoy, Piotr Indyk, Anastasios Sidiropoulos
We study the problem of minimum-distortion embedding of ultrametrics into the plane and higher dimensional spaces. Ultrametrics are a natural class of metrics that frequently occur in applications...
Convergence and Approximation in Potential (2008)
George Christodoulou, Vahab S. Mirrokni, Anastasios Sidiropoulos
Abstract. We study the speed of convergence to approximately optimal states in two classes of potential games. We provide bounds in terms of the number of rounds, where a round consists of a sequence...
Convergence and Approximation in Potential (2008)
George Christodoulou, Vahab S. Mirrokni, Anastasios Sidiropoulos
1 Introduction The main tool for analyzing the performance of systems where selfish playersinteract without central coordination, is the notion of the price of anarchy in a game [16]; this is the...
On Distributing Symmetric Streaming Computations (2008)
Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein
A common approach for dealing with large data sets is to stream over the input in one pass, and perform computations using sublinear resources. For truly massive data sets, however, even making a...
Inapproximability for metric embeddings into R^d (2008)
Matousek, Jiri, Sidiropoulos, Anastasios
We consider the problem of computing the smallest possible distortion for embedding of a given n-point metric space into R^d, where d is fixed (and small). For d=1, it was known that approximating...
Computational metric embeddings (2008)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.
Computational metric embeddings (2008)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.
Ioannis Caragiannis, Christos Kaklamanis, Pino Persiano, Anastasios Sidiropoulos
Abstract. Motivated by the problem of allocating optical bandwidth in tree--shaped WDM networks, we study the fractional path coloring problem in trees. We consider the class of locally-symmetric...
• Fill out HKN Survey online. (2007)
Lecturer Madhu, Sudan Scribe, Alex Andoni, Anastasios Sidiropoulos
Topics for this lecture are: • Continue the discussion on Average-Case analysis (as opposed to Worst Case); • Present Impagliazzo’s five possible worldsl
On the Complexity of Processing Massive, Unordered, Distributed Data (2006)
Feldman, Jon, Muthukrishnan, S., Sidiropoulos, Anastasios, Stein, Cliff, Svitkina, Zoya
An existing approach for dealing with massive data sets is to stream over the input in few passes and perform computations with sublinear resources. This method does not work for truly massive data...
On the complexity of processing massive, unordered, distributed data (2006)
Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein, Zoya Svitkina
The popular model for processing massive data sets is the streaming model in which the processor makes a pass over the input with polylog(n)-space. However, with current data sets, even making a...
Convergence and approximation in potential games (2006)
George Christodoulou, Vahab S. Mirrokni, Anastasios Sidiropoulos
AMS subject classifications. 15A15 Abstract. We study the speed of convergence to approximately optimal states in two classes of potential games. We provide bounds in terms of the number of rounds,...
Approximation algorithms for low-distortion embeddings into low-dimensional spaces (2005)
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2005.
Approximation algorithms for low-distortion embeddings into low-dimensional spaces (2005)
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2005.
Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces (2005)
Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Anastasios Sidiropoulos
Abstract We present several approximation algorithms for theproblem of embedding metric spaces into a line, and into the two-dimensional plane. Among other results, wegive an O(pn)-approximation...
Ordinal embeddings of minimum relaxation: General properties, trees and ultrametrics (2005)
Noga Alon, Mihai Bădoiu, Erik D. Demaine, Martin Farach-colton, Mohammadtaghi Hajiaghayi, Anastasios Sidiropoulos
We introduce a new notion of embedding, called minimumrelaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the...
Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces (2005)
Mihai Bădoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, R. Ravi, ...
We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the two-dimensional plane. Among other results, we give an O ( √ n)-approximation...
Ordinal embeddings of minimum relaxation: General properties, trees and ultrametrics (2005)
Noga Alon, Mihai Bădoiu, Erik D. Demaine, Martin Farach-colton, Mohammadtaghi Hajiaghayi, Anastasios Sidiropoulos
We introduce a new notion of embedding, called minimumrelaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the...
Ordinal embeddings of minimum relaxation: General properties, trees and ultrametrics (2005)
Noga Alon, Mihai Bădoiu, Erik D. Demaine, Martin Farach-colton, Mohammadtaghi Hajiaghayi, Anastasios Sidiropoulos
We introduce a new notion of embedding, called minimum-relaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the...
Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces (2005)
Mihai Bădoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, R. Ravi, ...
We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the two-dimensional plane. Among other results, we give an O ( √ n)-approximation...
Ordinal embeddings of minimum relaxation: General properties, trees and ultrametrics (2005)
Noga Alon, Erik D. Demaine, Martin Farach-colton, Anastasios Sidiropoulos
Abstract. We introduce a new notion of embedding, called minimum-relaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is...
Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces (2005)
Mihai Bădoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, R. Ravi, ...
We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the two-dimensional plane. Among other results, we give an O ( √ n)-approximation...
Approximation Algorithms for Low-Distortion Embeddings Into (2005)
Mihai Bădoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, ...
We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the two-dimensional plane. Among other results, we give an O( # n)-approximation algorithm...
Ordinal embeddings of minimum relaxation: General properties, trees and ultrametrics (2005)
Noga Alon, Mihai Bădoiu, Erik D. Demaine, Martin Farach-colton, Mohammadtaghi Hajiaghayi, Anastasios Sidiropoulos
We introduce a new notion of embedding, called minimumrelaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the...
Into Low-Dimensional Spaces (2005)
Anastasios Sidiropoulos, Piotr Indyk, Anastasios Sidiropoulos
We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the two-dimensional plane. We give an O ( √ n)approximation algorithm for the problem of...
A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees (2004)
Badoiu, Mihai, Indyk, Piotr, Sidiropoulos, Anastasios
We present a constant-factor approximation algorithm for computing an embedding of the shortest path metric of an unweighted graph into a tree, that minimizes the multiplicative distortion.
A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees (2004)
Badoiu, Mihai, Indyk, Piotr, Sidiropoulos, Anastasios
We present a constant-factor approximation algorithm for computing anembedding of the shortest path metric of an unweighted graph into atree, that minimizes the multiplicative distortion.
A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees (2004)
Badoiu, Mihai, Indyk, Piotr, Sidiropoulos, Anastasios
We present a constant-factor approximation algorithm for computing anembedding of the shortest path metric of an unweighted graph into atree, that minimizes the multiplicative distortion.
A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees (2004)
Badoiu, Mihai, Indyk, Piotr, Sidiropoulos, Anastasios
We present a constant-factor approximation algorithm for computing an embedding of the shortest path metric of an unweighted graph into a tree, that minimizes the multiplicative distortion.