Publications related to Knapsack problem

Fast multi-contact whole-body motion planning with limb dynamics

Auke Ijspeert, Jonathan Patrick Arreguit O'Neill, Salman Faraji

We present a new method for multi-contact motion planning which efficiently encodes internal dynamics of the robot without needing to use full models. Our approach is based on a five-mass model which is formulated by Cartesian points instead of joint angle ...

IEEE2018

Optimal Software Patching Plan for PMUs

Jean-Yves Le Boudec, Ola Nils Anders Svensson, Teklemariam Tsegay Tesfay

Phasor measurement units (PMUs) deployed to monitor the state of an electrical grid need to be patched from time to time to prevent attacks that exploit vulnerabilities in the software. Applying some of these patches requires a PMU reboot, which takes the ...

2017

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

A refined estimate for the topological degree

Hoài-Minh Nguyên

We sharpen an estimate of [4] for the topological degree of continuous maps from a sphere Sdinto itself in the case d >= 2. This provides the answer for d >= 2 to a question raised by Brezis. The problem is still open for d = 1. (C) 2017 Academie des scien ...

2017

The gene family-free median of three

Metin Balaban

Background: The gene family-free framework for comparative genomics aims at providing methods for gene order analysis that do not require prior gene family assignment, but work directly on a sequence similarity graph. We study two problems related to the b ...

2017

Optimization based methods for highly heterogeneous multiscale problems and multiscale methods for elastic waves

Multiscale or multiphysics partial differential equations are used to model a wide range of physical systems with various applications, e.g. from material and natural science to problems in biology or engineering. When the ratio between the smallest scale ...

EPFL2017

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

Distributed Rate Allocation in Switch-Based Multiparty Videoconferencing System

Pascal Frossard, Sergio Mena, Stefano D'Aronco

Multiparty videoconferences, or more generally multiparty video calls, are gaining a lot of popularity as they offer a rich communication experience. These applications have, however, large requirements in terms of both network and computational resources ...

2017

We get the algorithms of our ground truths: Designing referential databases in digital image processing

Florian Lucas Jaton

This article documents the practical efforts of a group of scientists designing an imageprocessing algorithm for saliency detection. By following the actors of this computer science project, the article shows that the problems often considered to be the st ...

SAGE Publications2017

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

Knapsack problem

Graph Chatbot

Chat with Graph Search

Fast multi-contact whole-body motion planning with limb dynamics

Optimal Software Patching Plan for PMUs

Dynamic Facility Location via Exponential Clocks

A refined estimate for the topological degree

The gene family-free median of three

Optimization based methods for highly heterogeneous multiscale problems and multiscale methods for elastic waves

Strengths and Limitations of Linear Programming Relaxations

Distributed Rate Allocation in Switch-Based Multiparty Videoconferencing System

We get the algorithms of our ground truths: Designing referential databases in digital image processing

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Optimization based methods for highly heterogeneous multiscale problems and multiscale methods for elastic waves

A refined estimate for the topological degree

Dynamic Facility Location via Exponential Clocks

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Distributed Rate Allocation in Switch-Based Multiparty Videoconferencing System

Fast multi-contact whole-body motion planning with limb dynamics

We get the algorithms of our ground truths: Designing referential databases in digital image processing

Strengths and Limitations of Linear Programming Relaxations

Optimal Software Patching Plan for PMUs

The gene family-free median of three