Publications de Igor Malinovic

On inequalities with bounded coefficients and pitch for the min knapsack polytope

Ola Nils Anders Svensson, Igor Malinovic

The min knapsack problem appears as a major component in the structure of capacitated covering problems. Its polyhedral relaxations have been extensively studied, leading to strong relaxations for networking, scheduling and facility location problems. ...

ELSEVIER2022

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

On Bounded Pitch Inequalities for the Min-Knapsack Polytope, Combinatorial Optimization

Ola Nils Anders Svensson, Yuri Faenza, Igor Malinovic

2018

A PTAS for the Time-Invariant Incremental Knapsack Problem, Combinatorial Optimization

Yuri Faenza, Igor Malinovic

2018

Clustered planarity testing revisited

Radoslav Fulek, Jan Kyncl, Igor Malinovic

The Hanani--Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generali ...

2015