Publication

Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity

Publications associées (45)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

Santa Claus schedules jobs on unrelated machines

Ola Nils Anders Svensson

One of the classic results in scheduling theory is the 2-approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines, i.e., job j requires time p ij if processed on machine i. More th ...

ACM2011

Approximability of Sparse Integer Programs

David Pritchard

The main focus of this paper is a pair of new approximation algorithms for certain integer programs. First, for covering integer programs {min cx:Ax≥b,0≤x≤d} where A has at most k nonzeroes per row, we give a k-approximation algorithm. (We assume A,b,c,d a ...

Springer-Verlag2011

New Algorithms for Approximate Nash Equilibria in Bimatrix Games

We consider the problem of computing additively approximate Nash equilibria in noncooperative two-player games. We provide a new polynomial time algorithm that achieves an approximation guarantee of 0.36392. We first provide a simpler algorithm, that achie ...

2010

Optimal selection of customers for a last-minute offer

Thomas Rothvoss

We analyze a short-term revenue optimization problem that involves the optimal targeting of customers for a promotion in which a finite number of perishable items are sold on a last-minute offer. The goal is to select the subset of customers to whom the of ...

Informs2010

Approximating Parameterized Convex Optimization Problems.

Martin Jaggi

We extend Clarkson's framework by considering parameterized convex optimization problems over the unit simplex, that depend on one parameter. We provide a simple and efficient scheme for maintaining an ε-approximate solution (and a corresponding ε-coreset) ...

2010

Parametric integer programming in fixed dimension

Friedrich Eisenbrand, Gennady Shmonin

We consider the following problem: Given a rational matrix

A \in \mathbb{Q}^{m \times n}

and a rational polyhedron

Q \subseteq \mathbb{R}^{m+p}

, decide if for all vectors

b \in \mathbb{R}^m

, for which there exists an integral

z \in \mathbb{Z}^p

suc ...

2008

New Algorithms for Approximate Nash Equilibria in Bimatrix Games

We consider the problem of computing additively approximate Nash equilibria in non-cooperative two-player games. We provide a new polynomial time algorithm that achieves an approximation guarantee of 0.36392. Our work improves the previously best known (0. ...

Springer2007

Average case analysis of multichannel sparse approximations using p- thresholding

Pierre Vandergheynst, Rémi Gribonval, Karin Schnass

This paper introduces

p

-thresholding, an algorithm to compute simultaneous sparse approximations of multichannel signals over redundant dictionaries. We work out both worst case and average case recovery analyses of this algorithm and show that the latte ...

2007

Average case analysis of multichannel sparse approximations using p-thresholding - art. no. 67011X

Pierre Vandergheynst, Rémi Gribonval, Karin Schnass

This paper introduces p-thresholding, an algorithm to compute simultaneous sparse approximations of multichannel signals over redundant dictionaries. We work out both worst case and average case recovery analyses of this algorithm and show that the latter ...

Spie-Int Soc Optical Engineering, Po Box 10, Bellingham, Wa 98227-0010 Usa2007