Publication

Single machine scheduling with scenarios

Related publications (101)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Knapsack and Subset Sum with Small Items

Adam Teodor Polak, Lars Rohwedder

Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomial running times for these problems with respect to various parameters. In t ...

Schloss Dagstuhl -- Leibniz-Zentrum für Informatik2021

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

Scalable Stochastic Optimization: Scenario Reduction with Guarantees

Kilian Schindler

Stochastic optimization is a popular modeling paradigm for decision-making under uncertainty and has a wide spectrum of applications in management science, economics and engineering. However, the stochastic optimization models one faces in practice are int ...

EPFL2020

Design of a quality control network for an international food company

Philippe Wieser, Nicolas Zufferey, Simone Lydia Voldrich

In this article, the design of a quality control network is considered in an entire supply chain, in the context of an international food and beverage company, denoted as ABC. For each possible control point of the network, two decisions have to be made: ( ...

TAYLOR & FRANCIS INC2020

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

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

No Small Linear Program Approximates Vertex Cover Within a Factor 2-epsilon

Ola Nils Anders Svensson, Abbas Bazzi

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349 ...

INFORMS2019

On Separable Quadratic Lyapunov Functions for Convex Design of Distributed Controllers

Maryam Kamgarpour, Luca Furieri

We consider the problem of designing a stabilizing and optimal static controller with a pre-specified sparsity pattern. Since this problem is NP-hard in general, it is necessary to resort to approximation approaches. In this paper, we characterize a class ...

IEEE2019

Modeling Superlattices of Dipolar and Polarizable Semiconducting Nanoparticles

Federico Giberti

We present an analytical model to describe the stability of arbitrary semiconducting nanoparticle (NP) superlattices as a function of the dipole and polarizability of their constituents. We first validate our model by comparison with density functional the ...

AMER CHEMICAL SOC2019

Safe Convex Learning under Uncertain Constraints

Maryam Kamgarpour, Andreas Krause, Ilnura Usmanova

We address the problem of minimizing a convex smooth function f(x) over a compact polyhedral set D given a stochastic zeroth-order constraint feedback model. This problem arises in safety-critical machine learning applications, such as personalized medicin ...

PMLR2019

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