Publication

Faster Algorithms for Integer Programs with Block Structure

Related publications (39)

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.

Fast hierarchical solvers for symmetric eigenvalue problems

Ana Susnjara

In this thesis we address the computation of a spectral decomposition for symmetric banded matrices. In light of dealing with large-scale matrices, where classical dense linear algebra routines are not applicable, it is essential to design alternative tech ...

EPFL2018

Practical Sketching Algorithms For Low-Rank Matrix Approximation

Volkan Cevher, Alp Yurtsever

This paper describes a suite of algorithms for constructing low-rank approximations of an input matrix from a random linear image, or sketch, of the matrix. These methods can preserve structural properties of the input matrix, such as positive-semidefinite ...

Society for Industrial and Applied Mathematics2017

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 ...

2017

Converse Bounds for Noisy Group Testing with Arbitrary Measurement Matrices

Volkan Cevher, Jonathan Mark Scarlett

We consider the group testing problem, in which one seeks to identify a subset of defective items within a larger set of items based on a number of noisy tests. While matching achievability and converse bounds are known in several cases of interest for i.i ...

Ieee2016

Parallel algorithms for tensor completion in the CP format

Daniel Kressner, André Uschmajew

Low-rank tensor completion addresses the task of filling in missing entries in multidimensional data. It has proven its versatility in numerous applications, including context aware recommender systems and multivariate function learning. To handle large-sc ...

Elsevier Science Bv2016

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 ...

2014

Efficient Subnetwork Selection in Relay Networks

Christina Fragouli, Siddhartha Brahma, Ayan Sengupta

Ieee2014

On Generalized Weighted Hilbert Matrices

Olivier Lévêque

We study spectral properties of generalized weighted Hilbert matrices. In particular, we establish results on the spectral norm, the determinant, and various relations between the eigenvalues and eigenvectors of such matrices. We also study the asymptotic ...

Pacific Journal Mathematics2013

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

A survey and comparison of contemporary algorithms for computing the matrix geometric mean

In this paper we present a survey of various algorithms for computing matrix geometric means and derive new second-order optimization algorithms to compute the Karcher mean. These new algorithms are constructed using the standard definition of the Riemanni ...

2012