Publications related to Algorithms For Clustering Problems

Applications of Strong Convex Relaxations to Allocation Problems

Approximation algorithms are a commonly used tool for designing efficient algorithmic solutions for intractable problems, at the expense of the quality of the output solution. A prominent technique for designing such algorithms is the use of Linear Program ...

EPFL2017

LP-Based Algorithms For Capacitated Facility Location

Ola Nils Anders Svensson, Hyung Chan An

Linear programming (LP) has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic me ...

Society for Industrial and Applied Mathematics2017

Dynamic clustering and propagation of congestion in heterogeneously congested urban traffic networks

Nikolaos Geroliminis, Mohammadreza Saeedmanesh

The problem of clustering in urban traffic networks has been mainly studied in static framework by considering traffic conditions at a given time. Nevertheless, it is important to underline that traffic is a strongly time-variant process and it needs to be ...

2017

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Volkan Cevher, Jonathan Mark Scarlett, Ilija Bogunovic, Slobodan Mitrovic

We study the problem of maximizing a monotone submodular function subject to a cardinality constraint

k

, with the added twist that a number of items

\tau

from the returned set may be removed. We focus on the worst-case setting considered in Orlin et al ...

2017

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. Maximization of such functions subject to various constraints receives little attention by c ...

Association for Computing Machinery2017

An integer programming approach to scheduling the transshipment of products at cross-docks in less-than-truckload industries

Mohammad Yousef Maknoon

This paper introduces an exact method to schedule the internal transshipment process at cross-docks in less-than-truckload industries. An integer programming formulation is presented to minimize the cost of double handling by synchronizing two types of dec ...

Pergamon-Elsevier Science Ltd2017

Efficient Linear Programming for Dense CRFs

Mathieu Salzmann

The fully connected conditional random field (CRF) with Gaussian pairwise potentials has proven popular and effective for multi-class semantic segmentation. While the energy of a dense CRF can be minimized accurately using a linear programming (LP) relaxat ...

2017

A Distributed Algorithm for Partitioned Robust Submodular Maximization

Volkan Cevher, Jonathan Mark Scarlett, Ilija Bogunovic, Slobodan Mitrovic

Abstract—In this paper, we consider the problem of maximizing a monotone submodular function subject to a cardinality constraint, with two added twists: The computation is distributed across a number of machines, and we require the solution to be robust ag ...

2017

Approximation algorithms for geometric dispersion

Alfonso Bolívar Cevallos Manzano

The most basic form of the max-sum dispersion problem (MSD) is as follows: given n points in R^q and an integer k, select a set of k points such that the sum of the pairwise distances within the set is maximal. This is a prominent diversity problem, with w ...

EPFL2016

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

Ola Nils Anders Svensson, Lukas Polacek

The restricted max-min fair allocation problem (also known as the restricted Santa Claus problem) is one of few problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, Asadpour et al. [2012] ...

Assoc Computing Machinery2016

Algorithms For Clustering Problems

Graph Chatbot

Chat with Graph Search

Applications of Strong Convex Relaxations to Allocation Problems

LP-Based Algorithms For Capacitated Facility Location

Dynamic clustering and propagation of congestion in heterogeneously congested urban traffic networks

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Maximizing Symmetric Submodular Functions

An integer programming approach to scheduling the transshipment of products at cross-docks in less-than-truckload industries

Efficient Linear Programming for Dense CRFs

A Distributed Algorithm for Partitioned Robust Submodular Maximization

Approximation algorithms for geometric dispersion

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

Approximation algorithms for geometric dispersion

An integer programming approach to scheduling the transshipment of products at cross-docks in less-than-truckload industries

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Efficient Linear Programming for Dense CRFs

A Distributed Algorithm for Partitioned Robust Submodular Maximization

Applications of Strong Convex Relaxations to Allocation Problems

Dynamic clustering and propagation of congestion in heterogeneously congested urban traffic networks

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

LP-Based Algorithms For Capacitated Facility Location

Maximizing Symmetric Submodular Functions