Publication

An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem

Publications associées (33)

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

Trading Strategy: A Case Study on the Day-Ahead and Week-Ahead Electricity Prices

The study consists of two interrelated parts. In the first part, we aim to identify the best predictive model of day-ahead electricity prices. In particular, we verify the existence of a dependence of the spot price on power generation and variable costs o ...

2018

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

Autonomous, Vision-based Flight and Live Dense 3D Mapping with a Quadrotor Micro Aerial Vehicle

Davide Scaramuzza

The use of mobile robots in search-and-rescue and disaster-response missions has increased significantly in recent years. However, they are still remotely controlled by expert professionals on an actuator set-point level, and they would benefit, therefore, ...

John Wiley & Sons2015

Multi-Objective Quality-Driven Service Selection-A Fully Polynomial Time Approximation Scheme

Boi Faltings, Immanuel Trummer

The goal of multi-objective quality-driven service selection (QDSS) is to find service selections for a workflow whose quality-of-service (QoS) values are Pareto-optimal. We consider multiple QoS attributes such as response time, cost, and reliability. A s ...

Institute of Electrical and Electronics Engineers2014

MATHICSE Technical Report : A continuation multilevel Monte Carlo algorithm

Fabio Nobile, Erik Gustaf Bogislaw Von Schwerin

We propose a novel Continuation Multi Level Monte Carlo (CMLMC) algorithm for weak approximation of stochastic models that are described in terms of differential equations either driven by random measures or with random coefficients. The CMLMC algorithm so ...

MATHICSE2014

Approximation schemes for many-objective query optimization

Christoph Koch, Immanuel Trummer

The goal of multi-objective query optimization (MOQO) is to find query plans that realize a good compromise between conicting objectives such as minimizing execution time and minimizing monetary fees in a Cloud scenario. A previously proposed exhaustive MO ...

ACM Press2014

Constrained Binary Identification Problem

Amin Karbasi, Morteza Zadimoghaddam

We consider the problem of building a binary decision tree, to locate an object within a set by way of the least number of membership queries. This problem is equivalent to the “20 questions game” of information theory and is closely related to lossless so ...

2013

Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut

Ola Nils Anders Svensson

We consider the Minimum Linear Arrangement problem and the (Uniform) Sparsest Cut problem. So far, these two notorious NP-hard graph problems have resisted all attempts to prove inapproximability results. We show that they have no polynomial time approxima ...

Society for Industrial and Applied Mathematics2011

The VPN problem with concave costs

Laura Sanità

Only recently Goyal, Olver and Shepherd (Proc. STOC, 2008) proved that the symmetric Virtual Private Network Design (sVPN) problem has the tree routing property, namely, that there always exists an optimal solution to the problem whose support is a tree. C ...

2010

k-Edge-Connectivity: Approximation and LP Relaxation

David Pritchard

This paper's focus is the following family of problems, denoted k-ECSS, where k denotes a positive integer: given a graph (V, E) and costs for each edge, find a minimum-cost subset F of E such that (V, F) is k-edge-connected. For k=1 it is the spanning tre ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2010