Publications associées à Matrice unimodulaire

A Spatial Branch and Bound Algorithm for Continuous Pricing with Advanced Discrete Choice Demand Modeling

In this paper, we present a spatial branch and bound algorithm to tackle the continuous pricing problem, where demand is captured by an advanced discrete choice model (DCM). Advanced DCMs, like mixed logit or latent class models, are capable of modeling de ...

2023

Vehicle-to-Grid for Reliable Frequency Regulation

Dirk Lauinger

Future low-carbon societies will need to store vast amounts of electricity to stabilize electricity grids and to power electric vehicles. Vehicle-to-grid allows vehicle owners and grid operators to share the costs of electricity storage by making the batte ...

EPFL2022

Faster Algorithms for Integer Programs with Block Structure

Friedrich Eisenbrand, Kim-Manuel Klein, Christoph Hunkenschröder

We consider integer programming problems max {c^Tx : A x = b, l

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik2018

Network Flow Integer Programming to Track Elliptical Cells in Time-Lapse Sequences

Pascal Fua, Engin Türetken, Xinchao Wang, Carlos Joaquin Becker

We propose a novel approach to automatically tracking elliptical cell populations in time-lapse image sequences. Given an initial segmentation, we account for partial occlusions and overlaps by generating an over-complete set of competing detection hypothe ...

Institute of Electrical and Electronics Engineers2017

Group-Sparse Model Selection: Hardness and Relaxations

Volkan Cevher, Anastasios Kyrillidis, Luca Baldassarre, Nirav Bhan

Group-based sparsity models are proven instrumental in linear regression problems for recovering signals from much fewer measurements than standard compressive sensing. The main promise of these models is the recovery of ``interpretable" signals along with ...

Institute of Electrical and Electronics Engineers2016

ALS Scheme using Extent-based Constraints for the Analysis of Chemical Reaction Systems

Dominique Bonvin, Julien Léo Billeter, Michael Amrhein

Multivariate curve resolution via alternating least squares (ALS) is used to resolve the concentration profiles C and the pure component spectra E of S species from the multivariate absorbance data A, assuming the bilinear model ...

2016

A totally unimodular view of structured sparsity

Volkan Cevher, Marwa El Halabi

This paper describes a simple framework for structured sparse recovery based on convex optimization. We show that many interesting structured sparsity models can be naturally represented by linear matrix inequalities on the support of the unknown parameter ...

2015

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

Efficient Subnetwork Selection in Relay Networks

Christina Fragouli, Siddhartha Brahma, Ayan Sengupta

We consider a source that would like to communicate with a destination over a layered Gaussian relay network. We present a computationally efficient method that enables to select a near-optimal (in terms of throughput) subnetwork of a given size connecting ...

Ieee2014

On Sub-determinants and the Diameter of Polyhedra

Friedrich Eisenbrand, Martin Niemeier, Nicolai Hähnle, Marco Di Summa, Nicolas Bonifas

We derive a new upper bound on the diameter of a polyhedron , where . The bound is polynomial in and the largest absolute value of a sub-determinant of , denoted by . More precisely, we show that the diameter of is bounded by . If is bounded, then we show ...

Springer2014

Tractability of interpretability via selection of group-sparse models

Volkan Cevher, Luca Baldassarre, Nirav Bhan

Group-based sparsity models are proven instrumental in linear regression problems for recovering signals from much fewer measurements than standard compressive sensing. A promise of these models is to lead to “interpretable” signals for which we identify i ...

2013

New Results in the Theory of Linear and Integer Programming

Nicolai Hähnle

The polynomial Hirsch conjecture states that the vertex-edge diameter of a d-dimensional polyhedron with n facets is bounded by a polynomial in d and n. For the special case where the polyhedron is defined as the set of points satisfying a system Ax ≤ b of ...

EPFL2012

Recognition of generalized network matrices

Antoine Musitelli

In this thesis, we deal with binet matrices, an extension of network matrices. The main result of this thesis is the following. A rational matrix A of size n×m can be tested for being binet in time O(n6m). If A is binet, our algorithm outputs a nonsingular ...

EPFL2007