Concept

Problème de bin packing

Publications associées (93)

On the Hardness of the Strongly Dependent Decision Problem

We present necessary and sufficient conditions for solving the strongly dependent decision (SDD) problem in various distributed systems. Our main contribution is a novel characterization of the SDD problem based on point-set topology. For partially synchro ...

ASSOC COMPUTING MACHINERY2019

Performance guarantees for greedy maximization of non-submodular controllability metrics

Maryam Kamgarpour, Tyler Summers

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 ...

IEEE2019

Bounding Inefficiency of Equilibria in Continuous Actions Games using Submodularity and Curvature

Maryam Kamgarpour, Andreas Krause

Games with continuous strategy sets arise in several machine learning problems (e.g. adversarial learning). For such games, simple no-regret learning algorithms exist in several cases and ensure convergence to coarse correlated equilibria (CCE). The effic ...

PMLR2019

Robust Maximization of Non-Submodular Objectives

Volkan Cevher, Ilija Bogunovic, Junyao Zhao

We study the problem of maximizing a monotone set function subject to a cardinality constraint k in the setting where some number of elements is deleted from the returned set. The focus of this work is on the worst-case adversarial setting. While there exi ...

2018

Using Structural Properties for Integer Programs

Kim-Manuel Klein

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, ...

SPRINGER INTERNATIONAL PUBLISHING AG2018

Optimal Load Sharing for Serial Compressors via Modifier Adaptation

Dominique Bonvin, Timm Faulwasser, René Uwe Schneider, Predrag Milosavljevic

This paper investigates the optimal load-sharing problem of serial gas compressors in the presence of plant-model mismatch. The problem is formulated as a static real-time optimization task that is solved via modifier adaptation for interconnected systems. ...

IEEE2018

Deterministic Algorithms for Submodular Maximization Problems

Moran Feldman

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 ...

ASSOC COMPUTING MACHINERY2018

Sharp sphere packings

Maryna Viazovska

In this talk we will speak about recent progress on the sphere packing problem. The packing problem can be formulated for a wide class of metric spaces equipped with a measure. An interesting feature of this optimization problem is that a slight change of ...

World Scientific Publishing2018

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Volkan Cevher, Jonathan Mark Scarlett, Ilija Bogunovic, Slobodan Mitrovic

We study the problem of maximizing a monotone submodular function subject to a cardinality constraint

k

, with the added twist that a number of items

\tau

from the returned set may be removed. We focus on the worst-case setting considered in Orlin et al ...

2017

Information Structure Design in Team Decision Problems

Maryam Kamgarpour, Tyler Summers

We consider a problem of information structure design in team decision problems and team games. We propose simple, scalable greedy algorithms for adding a set of extra information links to optimize team performance and resilience to non-cooperative and adv ...

2017

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

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Volkan Cevher, Jonathan Mark Scarlett, Ilija Bogunovic, Slobodan Mitrovic

We study the problem of maximizing a monotone submodular function subject to a cardinality constraint

k

, with the added twist that a number of items

\tau

from the returned set may be removed. We focus on the worst-case setting considered in Orlin et al ...

2017