Publications associées à 2D-TUCKER Is PPAD-Complete

Approximation Algorithms for Allocation and Network Design

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

EPFL2023

Adaptive majority problems for restricted query graphs and for weighted sets

Abhishek Methuku, Balázs Keszegh

Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study th ...

ELSEVIER2021

New Results in Integer and Lattice Programming

Christoph Hunkenschröder

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

,

b \in \Z^m

,

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

is a separable convex objective function. The problem o ...

EPFL2020

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

Mikhail Kapralov, Slobodan Mitrovic, Ashkan Norouzi Fard, Jakab Tardos

Given a source of iid samples of edges of an input graph G with n vertices and m edges, how many samples does one need to compute a constant factor approximation to the maximum matching size in G? Moreover, is it possible to obtain such an estimate in a sm ...

ASSOC COMPUTING MACHINERY2020

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

Adaptive Majority Problems For Restricted Query Graphs And For Weighted Sets

Abhishek Methuku, Balázs Keszegh

Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study th ...

COMENIUS UNIV2019

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Igor Malinovic

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

EPFL2019

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

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

We consider the Node-weighted Steiner Forest problem on planar graphs. Demaine et al. showed that a generic primal-dual algorithm gives a 6-approximation. We present two different proofs of an approximation factor of~

3

. Then, we draw a connection to Goem ...

EPFL2014

How to display data by color schemes compatible with red-green color perception deficiencies

Theo Lasser

Visualization of data concerns most scientists. The use of color is required in order to display multidimensional information. In addition, color encoding a univariate image can improve the interpretation significantly. However up to 10% of the adult male ...

Optical Society of America2013

2D-TUCKER Is PPAD-Complete

Graph Chatbot

Chattez avec Graph Search

Approximation Algorithms for Allocation and Network Design

Adaptive majority problems for restricted query graphs and for weighted sets

New Results in Integer and Lattice Programming

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

New Graph Algorithms via Polyhedral Techniques

Adaptive Majority Problems For Restricted Query Graphs And For Weighted Sets

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Optimal Software Patching Plan for PMUs

Node-weighted network design and maximum sub-determinants

How to display data by color schemes compatible with red-green color perception deficiencies

Optimal Software Patching Plan for PMUs

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

New Graph Algorithms via Polyhedral Techniques

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

New Results in Integer and Lattice Programming

Approximation Algorithms for Allocation and Network Design

Node-weighted network design and maximum sub-determinants

How to display data by color schemes compatible with red-green color perception deficiencies

Adaptive Majority Problems For Restricted Query Graphs And For Weighted Sets

Adaptive majority problems for restricted query graphs and for weighted sets