Publications related to Semidefinite programming

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your 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

Semidefinite programming

Graph Chatbot

Chat with 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

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

Approximating ATSP by Relaxing Connectivity

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

A simple relaying strategy for diamond networks

Centrality of trees for capacitated -center

Pliable Index Coding

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

A Primal-Dual Algorithmic Framework for Constrained Convex Minimization

FETI-DP Domain Decomposition Method

Upper bounds for the reach-avoid probability via robust optimization