Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Recherche

Afficher tous les résultats pour

Accueil

Personne

Igor Malinovic

Cette personne a quitté l’EPFL

À propos
Confidentialité
Mentions légales

Graph Chatbot

Publications associées (5)

Page 1 sur 1

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

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

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

Yuri Faenza, Igor Malinovic

2018

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 Bounded Pitch Inequalities for the Min-Knapsack Polytope, Combinatorial Optimization

Ola Nils Anders Svensson, Yuri Faenza, Igor Malinovic

2018