Concept

Schéma d'approximation en temps polynomial

Publications associées (278)

Solving the Infinite-horizon Constrained LQR Problem using Accelerated Dual Proximal Methods

Colin Neil Jones, Milan Korda, Georgios Stathopoulos

This work presents an algorithmic scheme for solving the infinite-time constrained linear quadratic regulation problem. We employ an accelerated version of a popular proximal gradient scheme, commonly known as the Forward-Backward Splitting (FBS), and prov ...

Institute of Electrical and Electronics Engineers2017

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

Cooperative data exchange based on MDS codes

Michael Christoph Gastpar, Su Li

The coded cooperative data exchange problem is studied for the fully connected network. In this problem, each node initially only possesses a subset of the K packets making up the file. Nodes make broadcast transmissions that are received by all other node ...

2017

Cooperative Data Exchange with Weighted Cost based on d-Basis Construction

Michael Christoph Gastpar, Su Li, Abhin Shah

We consider the cooperative data exchange problem, in which nodes are fully connected with each other. Each node initially only has a subset of the K packets making up a file and wants to recover the whole file. Node i can make a broadcast transmission, wh ...

2017

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

Dynamic Facility Location via Exponential Clocks

Ola Nils Anders Svensson, Ashkan Norouzi Fard, Hyung Chan An

The dynamic facility location problem is a generalization of the classic facility location problem proposed by Eisenstat, Mathieu, and Schabanel to model the dynamics of evolving social/infrastructure networks. The generalization lies in that the distance ...

Association for Computing Machinery2017

On verifying causal consistency

Rachid Guerraoui, Jad Hamza

Causal consistency is one of the most adopted consistency criteria for distributed implementations of data structures. It ensures that operations are executed at all sites according to their causal precedence. We address the issue of verifying automaticall ...

Cybersecurity Solutions for Active Power Distribution Networks

Teklemariam Tsegay Tesfay

An active distribution network (ADN) is an electrical-power distribution network that implements a real-time monitoring and control of the electrical resources and the grid. Effective monitoring and control is realised by deploying a large number of sensin ...

EPFL2017

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

Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration

Nisheeth Vishnoi, Javad Ebrahimi Boroojeni, Damian Mateusz Straszak

Several fundamental problems that arise in optimization and computer science can be cast as follows: Given vectors v(1), ..., v(m) is an element of R-d and a constraint family B subset of 2([m]), find a set S. B that maximizes the squared volume of the sim ...

Ieee2017

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