Approximation Algorithms for Allocation and Network Design
Publications associées (159)
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.
We present a technique for the approximation of a class of Hilbert space-valued maps which arise within the framework of Model Order Reduction for parametric partial differential equations, whose solution map has a meromorphic structure. Our MOR stategy co ...
In the multi-armed bandit literature, the multi-bandit best-arm identification problem consists of determining each best arm in a number of disjoint groups of arms, with as few total arm pulls as possible. In this paper, we introduce a variant of the multi ...
Initially developed for the min-knapsack problem, the knapsack cover inequalities are used in the current best relaxations for numerous combinatorial optimization problems of covering type. In spite of their widespread use, these inequalities yield linear ...
Clustering is a classic topic in combinatorial optimization and plays a central role in many areas, including data science and machine learning. In this thesis, we first focus on the dynamic facility location problem (i.e., the facility location problem in ...
Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function maximization. In this area, most algorithms are randomized, and in almost all c ...
In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...
A CUR approximation of a matrix A is a particular type of low-rank approximation where C and R consist of columns and rows of A, respectively. One way to obtain such an approximation is to apply column subset selection to A and its transpose. In this work, ...
Integer programs (IPs) are one of the fundamental tools used to solve combinatorial problems in theory and practice. Understanding the structure of solutions of IPs is thus helpful to argue about the existence of solutions with a certain simple structure, ...
Knapsack problems give a simple framework for decision making. A classical example is the min-knapsack problem (MinKnap): choose a subset of items with minimum total cost, whose total profit is above a given threshold. While this model successfully general ...
A key problem in emerging complex cyber-physical networks is the design of information and control topologies, including sensor and actuator selection and communication network design. These problems can be posed as combinatorial set function optimization ...