Convex Relaxations for Permutation Problems
From MaRDI portal
Publication:3456867
DOI10.1137/130947362zbMath1338.90336arXiv1306.4805OpenAlexW1949523763MaRDI QIDQ3456867
Rodolphe Jenatton, Alexandre d'Aspremont, Fajwel Fogel, Francis Bach
Publication date: 9 December 2015
Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1306.4805
Convex programming (90C25) Combinatorics of partially ordered sets (06A07) Combinatorial optimization (90C27) Protein sequences, DNA sequences (92D20)
Related Items
Reconstruction of line-embeddings of graphons, Spectral graph matching and regularized quadratic relaxations. I: Algorithm and Gaussian analysis, Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition, Localization in 1D non-parametric latent space models from pairwise affinities, ADM-CLE Approach for Detecting Slow Variables in Continuous Time Markov Chains and Dynamic Data, Continuation methods for approximate large scale object sequencing, \texttt{PQser:} a Matlab package for spectral seriation, New special cases of the quadratic assignment problem with diagonally structured coefficient matrices, The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure, $L_p$-norm Regularization Algorithms for Optimization Over Permutation Matrices
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Moment inequalities for sums of random matrices and their applications in optimization
- Smallest compact formulation for the permutahedron
- An improved approximation ratio for the minimum linear arrangement problem
- \(\ell ^2_2\) spreading metrics for vertex ordering problems
- Approximating orthogonal matrices by permutation matrices
- Sums of random symmetric matrices and quadratic optimization under orthogonality constraints
- Quick approximation to matrices and applications
- Geometric algorithms and combinatorial optimization
- On the consecutive ones property
- Semidefinite programming relaxations for the quadratic assignment problem
- Introductory lectures on convex optimization. A basic course.
- Approximating the bandwidth via volume respecting embeddings
- The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure
- On complexity of matrix scaling
- Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
- Incidence matrices and interval graphs
- The Quadratic Assignment Problem
- Divide-and-conquer approximation algorithms via spreading metrics
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- A Spectral Algorithm for Seriation and the Consecutive Ones Problem
- An Analysis of Spectral Envelope Reduction via Quadratic Assignment Problems
- A New Value Iteration method for the Average Cost Dynamic Programming Problem
- New Approximation Techniques for Some Linear Ordering Problems
- A spectral algorithm for envelope reduction of sparse matrices
- An Investigation of Interior-Point Algorithms for the Linear Transportation Problem
- Seriation and matrix reordering methods: An historical overview
- Weak Recovery Conditions from Graph Partitioning Bounds and Order Statistics
- A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
- Elements of Information Theory
- Abundance matrices and seriation in archaeology
