Publications related to Approximation algorithms for geometric dispersion

Indoor localization method and system

Martin Vetterli, Reza Parhizkar, Gilles Baechler

An indoor localization method for estimating the location of nodes (n1, n2), at least one node (n1) being connected to at least another node (n2) by at least two different channels (ch1, ch1′), comprising the following steps: measuring a distance between t ...

2015

A Tight Linear Time (1/2)-Approximation For Unconstrained Submodular Maximization

Moran Feldman

We consider the Unconstrained Submodular Maximization problem in which we are given a nonnegative submodular function f : 2(N) -> R+, and the objective is to find a subset S subset of N maximizing f(S). This is one of the most basic submodular optimization ...

Siam Publications2015

Approximation algorithms for regret minimization in vehicle routing problems

Adrian Aloysius Bock

In this thesis, we present new approximation algorithms as well as hardness of approximation results for NP-hard vehicle routing problems related to public transportation. We consider two different problem classes that also occur frequently in areas such a ...

EPFL2014

Centrality of Trees for Capacitated k-Center

Ola Nils Anders Svensson, Hyung Chan An, Aditya Bhaskara

We consider the capacitated k-center problem. In this problem we are given a finite set of locations in a metric space and each location has an associated non-negative integer capacity. The goal is to choose (open) k locations (called centers) and assign e ...

Springer2014

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

We consider the Node-weighted Steiner Forest problem on planar graphs. Demaine et al. showed that a generic primal-dual algorithm gives a 6-approximation. We present two different proofs of an approximation factor of~

3

. Then, we draw a connection to Goem ...

EPFL2014

Euclidean distance versus travel time in business location: A probabilistic mixture of hurdle-Poisson models

Matthieu Marie Cochon de Lapparent

While the question of the specification of spatial weight matrix is now largely discussed in the spatial econometrics literature, the definition of distance has attracted less attention. The choice of the distance measure is often glossed over, with the ul ...

2014

Right-Protected Data Publishing with Provable Distance-Based Mining

Michail Vlachos, Nikolaos Freris

Protection of one's intellectual property is a topic with important technological and legal facets. We provide mechanisms for establishing the ownership of a dataset consisting of multiple objects. The algorithms also preserve important properties of the d ...

Ieee Computer Soc2014

Theoretical Analysis of Euclidean Distance Matrix Completion for Ad hoc Microphone Array Calibration

Mohammadjavad Taghizadeh

We consider the problem of ad~hoc microphone array calibration where the distance matrix consisted of all microphones pairwise distances have entries missing corresponding to distances greater than

d_{\text{max}}

. Furthermore, the known entries are noisy ...

Idiap2014

On The Image Of The Almost Strict Morse N-Category Under Almost Strict N-Functors

In an earlier work, we constructed the almost strict Morse n-category X which extends Cohen Sz Jones Sz Segal's flow category. In this article, we define two other almost strict n-categories V and W where V is based on homomorphisms between real vector spa ...

Mount Allison University2014

Geometric Variational Models for Inverse Problems in Imaging

Virginia Estellers Casas

This dissertation develops geometric variational models for different inverse problems in imaging that are ill-posed, designing at the same time efficient numerical algorithms to compute their solutions. Variational methods solve inverse problems by the fo ...

EPFL2013

Approximation algorithms for geometric dispersion

Graph Chatbot

Chat with Graph Search

Indoor localization method and system

A Tight Linear Time (1/2)-Approximation For Unconstrained Submodular Maximization

Approximation algorithms for regret minimization in vehicle routing problems

Centrality of Trees for Capacitated k-Center

Node-weighted network design and maximum sub-determinants

Euclidean distance versus travel time in business location: A probabilistic mixture of hurdle-Poisson models

Right-Protected Data Publishing with Provable Distance-Based Mining

Theoretical Analysis of Euclidean Distance Matrix Completion for Ad hoc Microphone Array Calibration

On The Image Of The Almost Strict Morse N-Category Under Almost Strict N-Functors

Geometric Variational Models for Inverse Problems in Imaging

Euclidean distance versus travel time in business location: A probabilistic mixture of hurdle-Poisson models

Approximation algorithms for regret minimization in vehicle routing problems

A Tight Linear Time (1/2)-Approximation For Unconstrained Submodular Maximization

Geometric Variational Models for Inverse Problems in Imaging

Node-weighted network design and maximum sub-determinants

Indoor localization method and system

On The Image Of The Almost Strict Morse N-Category Under Almost Strict N-Functors

Centrality of Trees for Capacitated k-Center

Theoretical Analysis of Euclidean Distance Matrix Completion for Ad hoc Microphone Array Calibration

Right-Protected Data Publishing with Provable Distance-Based Mining