Publications related to LP-Based Algorithms For Capacitated Facility Location

Maximizing Symmetric Submodular Functions

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

On the configuration LP for maximum budgeted allocation

Ola Nils Anders Svensson, Christos Kalaitzis, Lukas Polacek, Aleksander Madry

We study the maximum budgeted allocation problem, i.e., the problem of selling a set of m indivisible goods to n players, each with a separate budget, such that we maximize the collected revenue. Since the natural assignment LP is known to have an integral ...

Springer Heidelberg2015

MATHICSE Technical Report : Subspace acceleration for large-scale parameter-dependent Hermitian eigenproblems

Daniel Kressner, Petar Sirkovic

This work is concerned with approximating the smallest eigenvalue of a parameter-dependent Hermitian matrix A(μ) for many parameter values μ ∈ RP. The design of reliable and efficient algorithms for addressing this task is of importance in a variety of app ...

MATHICSE2015

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

LP-Based Algorithms for Capacitated Facility Location

Ola Nils Anders Svensson, Hyung Chan An

Linear programming 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 methodo ...

IEEE2014

Coding Structure and Replication Optimization for Interactive Multiview Video Streaming

Pascal Frossard

Multiview video refers to videos of the same dynamic 3-D scene captured simultaneously by multiple closely spaced cameras from different viewpoints. We study interactive streaming of pre-encoded multiview videos, where, at any time, a client can request an ...

Ieee-Inst Electrical Electronics Engineers Inc2014

Efficient Subnetwork Selection in Relay Networks

Christina Fragouli, Siddhartha Brahma, Ayan Sengupta

We consider a source that would like to communicate with a destination over a layered Gaussian relay network. We present a computationally efficient method that enables to select a near-optimal (in terms of throughput) subnetwork of a given size connecting ...

2014

Efficient Subnetwork Selection in Relay Networks

Christina Fragouli, Siddhartha Brahma, Ayan Sengupta

We consider a source that would like to communicate with a destination over a layered Gaussian relay network. We present a computationally efficient method that enables to select a near-optimal (in terms of throughput) subnetwork of a given size connecting ...

Ieee2014

Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines

Ola Nils Anders Svensson

We study a natural generalization of the problem of minimizing makespan on unrelated machines in which jobs may be split into parts. The different parts of a job can be (simultaneously) processed on different machines, but each part requires a setup time b ...

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

LP-Based Algorithms For Capacitated Facility Location

Graph Chatbot

Chat with Graph Search

Maximizing Symmetric Submodular Functions

On the configuration LP for maximum budgeted allocation

MATHICSE Technical Report : Subspace acceleration for large-scale parameter-dependent Hermitian eigenproblems

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

LP-Based Algorithms for Capacitated Facility Location

Coding Structure and Replication Optimization for Interactive Multiview Video Streaming

Efficient Subnetwork Selection in Relay Networks

Efficient Subnetwork Selection in Relay Networks

Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines

Node-weighted network design and maximum sub-determinants

On the configuration LP for maximum budgeted allocation

Coding Structure and Replication Optimization for Interactive Multiview Video Streaming

Node-weighted network design and maximum sub-determinants

Maximizing Symmetric Submodular Functions

Efficient Subnetwork Selection in Relay Networks

MATHICSE Technical Report : Subspace acceleration for large-scale parameter-dependent Hermitian eigenproblems

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

Efficient Subnetwork Selection in Relay Networks

Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines

LP-Based Algorithms for Capacitated Facility Location