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...
A unified access bound on comparison-based dynamic dictionaries (2008)
Mihai Bădoiu, Richard Cole, Erik D. Demaine, John Iacono
We present a dynamic comparison-based search structure that supports insertions, deletions, and searches within the unified bound. The unified bound specifies that it is quick to access an element...
ABSTRACT Low-Dimensional Embedding with Extra Information (2008)
Mihai Bădoiu, Erik D. Demaine, Mohammadtaghi Hajiaghayi, Piotr Indyk
A frequently arising problem in computational geometry is when a physical structure, such as an ad-hoc wireless sensor network or a protein backbone, can measure local information about its geometry...
A unified access bound on comparison-based dynamic dictionaries (2008)
Mihai Bădoiu, Richard Cole, Erik D. Demaine, John Iacono
We present a dynamic comparison-based search structure that supports insert, delete, and search within the unified bound. The unified bound specifies that it is quick to access an element that is...
Low-Dimensional Embedding with Extra (2008)
Mihai Bădoiu, Erik D. Demaine, Mohammadtaghi Hajiaghayi, Piotr Indyk
(will be inserted by the editor)
A low-distortion embedding between two metric spaces is a mapping which preserves the distances between each pair of points, up to a small factor called distortion. Low-distortion embeddings have...
ABSTRACT Low-Dimensional Embedding with Extra Information (2008)
Mihai Bădoiu, Erik D. Demaine, Mohammad Taghi, Hajiaghayi Piotr Indyk
A frequently arising problem in computational geometry is when a physical structure, such as an ad-hoc wireless sensor network or a protein backbone, can measure local information about its geometry...
Certified by.......................................................... (2006)
Mihai Bădoiu, Piotr Indyk, Arthur C. Smith, Mihai Bădoiu
We present several computationally efficient algorithms, and complexity results on low distortion mappings between metric spaces. An embedding between two metric spaces is a mapping between the two...
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...
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...
Facility location in sublinear time (2005)
Mihai Bădoiu, Artur Czumaj, Piotr Indyk, Christian Sohler
Abstract. In this paper we present a randomized constant factor approximation algorithm for the problem of computing the optimal cost of the metric Minimum Facility Location problem, in the case of...
A simplified and dynamic unified structure (2004)
Abstract. The unified property specifies that a comparison-based search structure can quickly find an element nearby a recently accessed element. Iacono [Iac01] introduced this property and developed...
Low-dimensional embedding with extra information (2004)
Mihai Bădoiu, Erik D. Demaine, Mohammadtaghi Hajiaghayi, Piotr Indyk
A frequently arising problem in computational geometry is when a physical structure, such as an ad-hoc wireless sensor network or a protein backbone, can measure local information about its geometry...
Clustering in High Dimensions (2003)
In this thesis we show that, for several clustering problems, we can extract a small set of points, so that, using these core-sets, we can approximate clustering efficiently. The cardinality of these...
Approximate clustering via core-sets (2002)
Mihai Bădoiu, Sariel Har-peled, Piotr Indyk
In this paper, we show that for several clustering problems one can extract a small set of points, so that using those core-sets enable us to perform approximate clustering efficiently. The...
Approximate clustering via core-sets (2002)
Mihai Bădoiu, Sariel Har-peled, Piotr Indyk
In this paper, we show that for several clustering problems one can extract a small set of points, so that using those core-sets enable us to perform approximate clustering efficiently. The...
Approximate clustering via core-sets (2002)
Mihai Bădoiu, Sariel Har-peled, Piotr Indyk
In this paper, we show that for several clustering problems one can extract a small set of points, so that using those core-sets enable us to perform approximate clustering efficiently. The...
Approximate clustering via core-sets (2002)
Mihai Bădoiu, Sariel Har-peled, Piotr Indyk
In this paper, we show that for several clustering problems one can extract a small set of points, so that using those core-sets enable us to perform approximate clustering efficiently. The...