Publications associées à Optimisation SDP

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.

An optimal first-order primal-dual gap reduction framework for constrained convex optimization

Volkan Cevher, Quoc Tran Dinh

We introduce an analysis framework for constructing optimal first-order primal-dual methods for the prototypical constrained convex optimization template. While this class of methods offers scalability advantages in obtaining numerical solutions, they have ...

Tech. Report. LIONS-EPFL (2015)2015

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

Upper bounds for the reach-avoid probability via robust optimization

Maryam Kamgarpour, John Lygeros, Tyler Summers

We consider finite horizon reach-avoid problems for discrete time stochastic systems. Our goal is to construct upper bound functions for the reach-avoid probability by means of tractable convex optimization problems. We achieve this by restricting attentio ...

2015

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ_1

Nisheeth Vishnoi

In this article, we disprove a conjecture of Goemans and Linial; namely, that every negative type metric embeds into ℓ1 with constant distortion. We show that for an arbitrarily small constant δ > 0, for all large enough n, there is an n-point negative ...

Association for Computing Machinery2015

Approximating ATSP by Relaxing Connectivity

Ola Nils Anders Svensson

The standard LP relaxation of the asymmetric traveling salesman problem has been conjectured to have a constant integrality gap in the metric case. We prove this conjecture when restricted to shortest path metrics of node-weighted digraphs. Our arguments a ...

IEEE Computer Society2015

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

Pliable Index Coding

Christina Fragouli, Siddhartha Brahma

We formulate a new variant of the index coding problem, where instead of demanding a specific message, clients are pliable, and are interested in receiving any t messages that they do not have. We term this problem pliable index coding or PICOD(t). We prov ...

Ieee-Inst Electrical Electronics Engineers Inc2015

A simple relaying strategy for diamond networks

Christina Fragouli, Siddhartha Brahma

We consider a Gaussian diamond network where a source communicates with the destination through n non-interfering half-duplex relays. Using simple approximations to the capacity of the network, we show that simple relaying strategies involving two relays a ...

Ieee2014

Optimisation SDP

Graph Chatbot

Chattez avec Graph Search

An optimal first-order primal-dual gap reduction framework for constrained convex optimization

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

Upper bounds for the reach-avoid probability via robust optimization

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ_1

Approximating ATSP by Relaxing Connectivity

Centrality of trees for capacitated -center

Pliable Index Coding

A simple relaying strategy for diamond networks

A Primal-Dual Algorithmic Framework for Constrained Convex Minimization

FETI-DP Domain Decomposition Method

Upper bounds for the reach-avoid probability via robust optimization

An optimal first-order primal-dual gap reduction framework for constrained convex optimization

Centrality of trees for capacitated -center

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

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ_1

Approximating ATSP by Relaxing Connectivity

A Primal-Dual Algorithmic Framework for Constrained Convex Minimization

A simple relaying strategy for diamond networks

FETI-DP Domain Decomposition Method

Pliable Index Coding