Publication

Algorithms For Clustering Problems

Related publications (107)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

A Bi-Criteria Approximation Algorithm for k-Means

Justin Dean Ward

We consider the classical k-means clustering problem in the setting of bi-criteria approximation, in which an algorithm is allowed to output beta*k > k clusters, and must produce a clustering with cost at most alpha times the to the cost of the optimal set ...

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik2016

An Efficient Streaming Algorithm for the Submodular Cover Problem

Volkan Cevher, Ilija Bogunovic, Ya-Ping Hsieh, Ashkan Norouzi Fard, Abbas Bazzi, Marwa El Halabi

We initiate the study of the classical Submodular Cover (SC) problem in the data streaming model which we refer to as the Streaming Submodular Cover (SSC). We show that any single pass streaming algorithm using sublinear memory in the size of the stream wi ...

2016

A New Framework for Distributed Submodular Maximization

Justin Dean Ward

A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. A lot of recent effort has been devoted to developing distributed algo ...

Ieee2016

Submodular Stochastic Probing on Matroids

Justin Dean Ward, Marek Adamczyk

In a stochastic probing problem we are given a universe E, and a probability that each element e in E is active. We determine if an element is active by probing it, and whenever a probed element is active, we must permanently include it in our solution. Mo ...

INFORMS2016

Fast K-Means with Accurate Bounds

François Fleuret, James Peter Newling

We propose a novel accelerated exact

k

-means algorithm, which outperforms the current state-of-the-art low-dimensional algorithm in 18 of 22 experiments, running up to 3

\times

faster. We also propose a general improvement of existing state-of-the-art a ...

Idiap2016

Centrality of trees for capacitated -center

Ola Nils Anders Svensson, Hyung Chan An, Aditya Bhaskara

We consider the capacitated -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) locations (called centers) and assign each ...

Springer Heidelberg2015

Comparing genomes with rearrangements and segmental duplications

Bernard Moret, Mingfu Shao

Motivation: Large-scale evolutionary events such as genomic rearrange. ments and segmental duplications form an important part of the evolution of genomes and are widely studied from both biological and computational perspectives. A basic computational pro ...

Oxford University Press2015

No Small Linear Program Approximates Vertex Cover within a Factor 2 - e

Ola Nils Anders Svensson, Abbas Bazzi

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regevproved that the problem is NP-hard to approximate within a factor2 - ∈, assuming the Unique Games Conjecture (UGC). This is tig ...

IEEE Computer Society2015

Maximizing Symmetric Submodular Functions

Moran Feldman

Symmetric submodular functions are an important family of submodular functions capturing many interesting cases including cut functions of graphs and hypergraphs. In this work, we identify submodular maximization problems for which one can get a better app ...

Springer Int Publishing Ag2015

Strong LP formulations for scheduling splittable jobs on unrelated machines

Ola Nils Anders Svensson

A natural extension of the makespan minimization problem on unrelated machines is to allow jobs to be partially processed by different machines while incurring an arbitrary setup time. In this paper we present increasingly stronger LP-relaxations for this ...