Publications related to Dynamic Facility Location via Exponential Clocks

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

Optimization is a fundamental tool in modern science. Numerous important tasks in biology, economy, physics and computer science can be cast as optimization problems. Consider the example of machine learning: recent advances have shown that even the most s ...

EPFL2018

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

Ola Nils Anders Svensson, Jakub Tarnawski

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of th ...

ASSOC COMPUTING MACHINERY2018

Robust auction design under multiple priors by linear and integer programming

Cagil Kocyigit

It is commonly assumed in the optimal auction design literature that valuations of buyers are independently drawn from a unique distribution. In this paper we study auctions under ambiguity, that is, in an environment where valuation distribution is uncert ...

2018

Using Structural Properties for Integer Programs

Kim-Manuel Klein

Integer programs (IPs) are one of the fundamental tools used to solve combinatorial problems in theory and practice. Understanding the structure of solutions of IPs is thus helpful to argue about the existence of solutions with a certain simple structure, ...

SPRINGER INTERNATIONAL PUBLISHING AG2018

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

Strengths and Limitations of Linear Programming Relaxations

Abbas Bazzi

Many of the currently best-known approximation algorithms for NP-hard optimization problems are based on Linear Programming (LP) and Semi-definite Programming (SDP) relaxations. Given its power, this class of algorithms seems to contain the most favourable ...

EPFL2017

Applications of Strong Convex Relaxations to Allocation Problems

Christos Kalaitzis

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

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

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

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

Dynamic Facility Location via Exponential Clocks

Graph Chatbot

Chat with Graph Search

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

Robust auction design under multiple priors by linear and integer programming

Using Structural Properties for Integer Programs

LP-Based Algorithms For Capacitated Facility Location

Strengths and Limitations of Linear Programming Relaxations

Applications of Strong Convex Relaxations to Allocation Problems

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

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

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

Strengths and Limitations of Linear Programming Relaxations

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

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

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

Robust auction design under multiple priors by linear and integer programming

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Using Structural Properties for Integer Programs

Applications of Strong Convex Relaxations to Allocation Problems

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

LP-Based Algorithms For Capacitated Facility Location