Publications related to A polynomial case of inconstrained zero-one queadratic optimization

On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices

Daniel Kressner, Stefano Massei, Alice Cortinovis

The problem of finding a k x k submatrix of maximum volume of a matrix A is of interest in a variety of applications. For example, it yields a quasi-best low-rank approximation constructed from the rows and columns of A. We show that such a submatrix can a ...

ELSEVIER SCIENCE 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

MATHICSE Technical Report : On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices

Daniel Kressner, Stefano Massei, Alice Cortinovis

The problem of finding a

k\times k

submatrix of maximum volume of a matrix A is of interest in a variety of applications. For example, it yields a quasi-best low-rank approximation constructed from the rows and columns of A. We show that such a submatrix ...

MATHICSE2019

Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

Ola Nils Anders Svensson, Abbas Bazzi, Sangxia Huang

Initially developed for the min-knapsack problem, the knapsack cover inequalities are used in the current best relaxations for numerous combinatorial optimization problems of covering type. In spite of their widespread use, these inequalities yield linear ...

UNIV CHICAGO, DEPT COMPUTER SCIENCE2018

Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization

Sebastian Urban Stich

We present the first accelerated randomized algorithm for solving linear systems in Euclidean spaces. One essential problem of this type is the matrix inversion problem. In particular, our algorithm can be specialized to invert positive definite matrices i ...

2018

Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization

Sebastian Urban Stich

We present the first accelerated randomized algorithm for solving linear systems in Euclidean spaces. One essential problem of this type is the matrix inversion problem. In particular, our algorithm can be specialized to invert positive definite matrices i ...

NEURAL INFORMATION PROCESSING SYSTEMS (NIPS)2018

Geometry-aware Tracking of Manipulability Ellipsoids

Sylvain Calinon, Noémie Laure Gwendoline Jaquier

Body posture can greatly influence human performance when carrying out manipulation tasks. Adopting an appropriate pose helps us regulate our motion and strengthen our capability to achieve a given task. This effect is also observed in robotic manipulation ...

2018

Strengths and Limitations of Linear Programming Relaxations

Abbas Bazzi

Many of the currently best-known approximation algorithms for NP-hard optimization problems are based on Linear Programming (LP) and Semi-definite Programming (SDP) relaxations. Given its power, this class of algorithms seems to contain the most favourable ...

EPFL2017

Combinatorial Algorithm for Restricted Max-Min Fair Allocation

Ola Nils Anders Svensson, Christos Kalaitzis, Chidambaram Annamalai

We study the basic allocation problem of assigning resources to players to maximize fairness. This is one of the few natural problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, a certain ...

Association for Computing Machinery2017

MATHICSE Technical Report : Bounds for the decay of the entries in inverses and Cauchy- Stieltjes functions of sparse, normal matrices

Marcel Schweitzer

It is known that in many functions of banded, and more generally, sparse Hermitian positive definite matrices, the entries exhibit a rapid decay away from the sparsity pattern. This is in particular true for the inverse, and based on results for the invers ...

MATHICSE2017

A polynomial case of inconstrained zero-one queadratic optimization

Graph Chatbot

Chat with Graph Search

On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices

New Graph Algorithms via Polyhedral Techniques

MATHICSE Technical Report : On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices

Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization

Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization

Geometry-aware Tracking of Manipulability Ellipsoids

Strengths and Limitations of Linear Programming Relaxations

Combinatorial Algorithm for Restricted Max-Min Fair Allocation

MATHICSE Technical Report : Bounds for the decay of the entries in inverses and Cauchy- Stieltjes functions of sparse, normal matrices

Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

New Graph Algorithms via Polyhedral Techniques

Strengths and Limitations of Linear Programming Relaxations

On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices

MATHICSE Technical Report : On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices

Geometry-aware Tracking of Manipulability Ellipsoids

Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization

Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization

MATHICSE Technical Report : Bounds for the decay of the entries in inverses and Cauchy- Stieltjes functions of sparse, normal matrices

Combinatorial Algorithm for Restricted Max-Min Fair Allocation