Publications related to Sparse Group Covers and Greedy Tree Approximations

Efficient Allocations in Constant Time: Towards Scalable Solutions in the Era of Large Scale Intelligent Systems

The next technological revolution will be interwoven to the proliferation of intelligent systems. As we bridge the gap between physical and cyber worlds, we will give rise to large-scale, multi-agent based technologies. A key challenge that cities of the f ...

IOS PRESS2020

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

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

EPFL2019

Actuator Placement for Optimizing Network Performance under Controllability Constraints

Maryam Kamgarpour, Tyler Summers, Baiwei Guo, Orcun Karaca

With the rising importance of large-scale network control, the problem of actuator placement has received increasing attention. Our goal in this paper is to find a set of actuators minimizing the metric that measures the average energy consumption of the c ...

IEEE2019

Approximating Steiner trees and forests with minimum number of Steiner points

Nachshon Cohen

Let R be a finite set of terminals in a convex metric space (M, d). We give approximation algorithms for problems of finding a minimum size set S subset of M of additional points such that the unit-disc graph G[R boolean OR S] of R boolean OR S satisfies s ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2018

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

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

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

Efficient greedy algorithms for high-dimensional parameter spaces with applications to empirical interpolation and reduced basis methods

Jan Sickmann Hesthaven, Benjamin Stamm

We propose two new and enhanced algorithms for greedy sampling of high- dimensional functions. While the techniques have a substantial degree of generality, we frame the discussion in the context of methods for empirical interpolation and the devel- opment ...

EDP Sciences2014

Right-Protected Data Publishing with Provable Distance-Based Mining

Michail Vlachos, Nikolaos Freris

Protection of one's intellectual property is a topic with important technological and legal facets. We provide mechanisms for establishing the ownership of a dataset consisting of multiple objects. The algorithms also preserve important properties of the d ...

Ieee Computer Soc2014

Steiner Tree Approximation via Iterative Randomized Rounding

Thomas Rothvoss, Laura Sanità

The Steiner tree problem is one of the most fundamental NP-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem w ...

Assoc Computing Machinery2013

Sparse Group Covers and Greedy Tree Approximations

Graph Chatbot

Chat with Graph Search

Efficient Allocations in Constant Time: Towards Scalable Solutions in the Era of Large Scale Intelligent Systems

New Graph Algorithms via Polyhedral Techniques

Actuator Placement for Optimizing Network Performance under Controllability Constraints

Approximating Steiner trees and forests with minimum number of Steiner points

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Strengths and Limitations of Linear Programming Relaxations

Optimal Software Patching Plan for PMUs

Efficient greedy algorithms for high-dimensional parameter spaces with applications to empirical interpolation and reduced basis methods

Right-Protected Data Publishing with Provable Distance-Based Mining

Steiner Tree Approximation via Iterative Randomized Rounding

New Graph Algorithms via Polyhedral Techniques

Strengths and Limitations of Linear Programming Relaxations

Efficient Allocations in Constant Time: Towards Scalable Solutions in the Era of Large Scale Intelligent Systems

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Actuator Placement for Optimizing Network Performance under Controllability Constraints

Approximating Steiner trees and forests with minimum number of Steiner points

Steiner Tree Approximation via Iterative Randomized Rounding

Right-Protected Data Publishing with Provable Distance-Based Mining

Optimal Software Patching Plan for PMUs

Efficient greedy algorithms for high-dimensional parameter spaces with applications to empirical interpolation and reduced basis methods