Publications related to Group-Sparse Model Selection: Hardness and Relaxations

Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity

Friedrich Eisenbrand, Moritz Andreas Venzin, Jana Tabea Cslovjecsek

We consider the problem of solving integer programs of the form min {c^⊺ x : Ax = b, x ∈ ℤ_{⩾ 0}}, where A is a multistage stochastic matrix in the following sense: the primal treedepth of A is bounded by a parameter d, which means that the columns of A ca ...

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

A note on the integrality gap of the configuration LP for restricted Santa Claus

Klaus Jansen, Lars Rohwedder

In the restricted Santa Claus problem we are given resources R and players P. Every resource j is an element of R. has a value v(j) and every player i is an element of P desires a set of resources R(i). We are interested in distributing the resources to pl ...

ELSEVIER2020

Learning (from) the Electron Density: Transferability, Conformational and Chemical Diversity

Ksenia Briling, Alberto Fabrizio, Andrea Grisafi

Machine-learning in quantum chemistry is currently booming, with reported applications spanning all molecular properties from simple atomization energies to complex mathematical objects such as the many-body wavefunction. Due to its central role in density ...

2020

Machine learning models of the energy curvature vs particle number for optimal tuning of long-range corrected functionals

Alberto Fabrizio, Benjamin André René Meyer

The average energy curvature as a function of the particle number is a molecule-specific quantity, which measures the deviation of a given functional from the exact conditions of density functional theory. Related to the lack of derivative discontinuity in ...

AMER INST PHYSICS2020

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

Fitting Markovian binary trees using global and individual demographic data

Sophie Myriam Hautphenne, Katharine Felicity Turner

We consider a class of continuous-time branching processes called Markovian binary trees (MBTs), in which the individuals lifetime and reproduction epochs are modelled using a transient Markovian arrival process (TMAP). We develop methods for estimating th ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2019

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

Damian Mateusz Straszak

Optimization is a fundamental tool in modern science. Numerous important tasks in biology, economy, physics and computer science can be cast as optimization problems. Consider the example of machine learning: recent advances have shown that even the most s ...

EPFL2018

Group-Sparse Model Selection: Hardness and Relaxations

Graph Chatbot

Chat with Graph Search

Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity

New Results in Integer and Lattice Programming

A note on the integrality gap of the configuration LP for restricted Santa Claus

Learning (from) the Electron Density: Transferability, Conformational and Chemical Diversity

Machine learning models of the energy curvature vs particle number for optimal tuning of long-range corrected functionals

New Graph Algorithms via Polyhedral Techniques

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

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

Fitting Markovian binary trees using global and individual demographic data

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

New Results in Integer and Lattice Programming

Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity

A note on the integrality gap of the configuration LP for restricted Santa Claus

New Graph Algorithms via Polyhedral Techniques

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

Learning (from) the Electron Density: Transferability, Conformational and Chemical Diversity

Machine learning models of the energy curvature vs particle number for optimal tuning of long-range corrected functionals

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

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

Fitting Markovian binary trees using global and individual demographic data