Monique Laurent

  • Tilburg University, The Netherlands
  • Centrum Wiskunde & Informatica

According to our database1, Monique Laurent authored at least 92 papers between 1984 and 2021.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.



In proceedings 
PhD thesis 


Online presence:



Near-optimal analysis of Lasserre's univariate measure-based bounds for multivariate polynomial optimization.
Math. Program., 2021

Sum-of-Squares Hierarchies for Binary Polynomial Optimization.
Proceedings of the Integer Programming and Combinatorial Optimization, 2021

Perfect elimination orderings for symmetric matrices.
Optim. Lett., 2020

Worst-Case Examples for Lasserre's Measure-Based Hierarchy for Polynomial Optimization on the Hypercube.
Math. Oper. Res., 2020

Lower Bounds on Matrix Factorization Ranks via Noncommutative Polynomial Optimization.
Found. Comput. Math., 2019

On the linear extension complexity of stable set polytopes for perfect graphs.
Eur. J. Comb., 2019

Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization.
Math. Program., 2018

Comparison of Lasserre's Measure-Based Bounds for Polynomial Optimization to Bounds Obtained by Simulated Annealing.
Math. Oper. Res., 2018

Improved Convergence Rates for Lasserre-Type Hierarchies of Upper Bounds for Box-Constrained Polynomial Optimization.
SIAM J. Optim., 2017

Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition.
SIAM J. Discret. Math., 2017

On the convergence rate of grid search for polynomial optimization over the simplex.
Optim. Lett., 2017

Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization.
Math. Program., 2017

Bound-Constrained Polynomial Optimization Using Only Elementary Calculations.
Math. Oper. Res., 2017

A Lex-BFS-based recognition algorithm for Robinsonian matrices.
Discret. Appl. Math., 2017

A Structural Characterization for Certifying Robinsonian Matrices.
Electron. J. Comb., 2017

Entanglement-Assisted Zero-Error Source-Channel Coding.
IEEE Trans. Inf. Theory, 2015

Conic Approach to Quantum Graph Parameters Using Linear Optimization Over the Completely Positive Semidefinite Cone.
SIAM J. Optim., 2015

An Error Analysis for Polynomial Optimization over the Simplex Based on the Multivariate Hypergeometric Distribution.
SIAM J. Optim., 2015

The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure.
Oper. Res. Lett., 2015

An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex.
Math. Program., 2015

On the Closure of the Completely Positive Semidefinite Cone and Linear Approximations to Quantum Colorings.
Proceedings of the 10th Conference on the Theory of Quantum Computation, 2015

A new graph parameter related to bounded rank positive semidefinite matrix completions.
Math. Program., 2014

Handelman's hierarchy for the maximum stable set problem.
J. Glob. Optim., 2014

Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope.
J. Comb. Theory, Ser. B, 2014

The Quadratic Assignment Problem is easy for Robinsonian Matrices.
CoRR, 2014

Moment matrices, border bases and real radical computation.
J. Symb. Comput., 2013

A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs.
Math. Program., 2012

On bounded rank positive semidefinite matrix completions of extreme partial correlation matrices
CoRR, 2012

The Gram Dimension of a Graph.
Proceedings of the Combinatorial Optimization - Second International Symposium, 2012

On the Lasserre Hierarchy of Semidefinite Programming Relaxations of Convex Polynomial Optimization Problems.
SIAM J. Optim., 2011

Computing the Grothendieck constant of some graph classes.
Oper. Res. Lett., 2011

On Leonid Gurvits's Proof for Permanents.
Am. Math. Mon., 2010

Error Bounds for Some Semidefinite Programming Approaches to Polynomial Minimization on the Hypercube.
SIAM J. Optim., 2010

Matrix Completion Problems.
Proceedings of the Encyclopedia of Optimization, Second Edition, 2009

A prolongation-projection algorithm for computing the finite real variety of an ideal.
Theor. Comput. Sci., 2009

Block-diagonal semidefinite programming hierarchies for 0/1 programming.
Oper. Res. Lett., 2009

Computing Semidefinite Programming Lower Bounds for the (Fractional) Chromatic Number Via Block-Diagonalization.
SIAM J. Optim., 2008

The Operator Psi for the Chromatic Number of a Graph.
SIAM J. Optim., 2008

Semidefinite Characterization and Computation of Zero-Dimensional Real Radical Ideals.
Found. Comput. Math., 2008

A Sparse Flat Extension Theorem for Moment Matrices
CoRR, 2008

Computing the real variety of an ideal: a real algebraic and symbolic-numeric algorithm.
Proceedings of the 2008 ACM Symposium on Applied Computing (SAC), 2008

Strengthened semidefinite programming bounds for codes.
Math. Program., 2007

Semidefinite representations for finite varieties.
Math. Program., 2007

Semidefinite bounds for the stability number of a graph via sums of squares of polynomials.
Math. Program., 2007

A PTAS for the minimization of polynomials of fixed degree over the simplex.
Theor. Comput. Sci., 2006

New Limits on Fault-Tolerant Quantum Computation.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Semidefinite Approximations for Global Unconstrained Polynomial Optimization.
SIAM J. Optim., 2005

Semidefinite Relaxations for Max-Cut.
Proceedings of the Sharpest Cut, 2004

Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope.
Math. Oper. Res., 2003

A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0-1 Programming.
Math. Oper. Res., 2003

Tighter Linear and Semidefinite Relaxations for Max-Cut Based on the Lov[a-acute]sz--Schrijver Lift-and-Project Procedure.
SIAM J. Optim., 2002

Polynomial Instances of the Positive Semidefinite and Euclidean Distance Matrix Completion Problems.
SIAM J. Matrix Anal. Appl., 2001

On the Sparsity Order of a Graph and Its Deficiency in Chordality.
Comb., 2001

Equilateral Dimension of the Rectilinear Space.
Des. Codes Cryptogr., 2000

Cycle Bases for Lattices of Binary Matroids with No Fano Dual Minor and Their One-Element Extensions.
J. Comb. Theory, Ser. B, 1999

Embedding into Rectilinear Spaces.
Discret. Comput. Geom., 1998

Connections between semidefinite relaxations of the max-cut and stable set problems.
Math. Program., 1997

Cuts, matrix completions and graph rigidity.
Math. Program., 1997

A minor-monotone graph parameter based on oriented matroids.
Discret. Math., 1997

Geometry of cuts and metrics.
Algorithms and combinatorics 15, Springer, ISBN: 978-3-540-61611-5, 1997

On the Facial Structure of the Set of Correlation Matrices.
SIAM J. Matrix Anal. Appl., 1996

Gap Inequalities for the Cut Polytope.
Eur. J. Comb., 1996

Graphic vertices of the metric polytope.
Discret. Math., 1996

Hilbert bases of cuts.
Discret. Math., 1996

One-third-integrality in the max-cut problem.
Math. Program., 1995

On a Minor-Monotone Graph Invariant.
J. Comb. Theory, Ser. B, 1995

A Characterization of Box 1/d-Integral Binary Clutters.
J. Comb. Theory, Ser. B, 1995

Some New Classes of Facets for the Equicut Polytope.
Discret. Appl. Math., 1995

Hypercube Embedding of Generalized Bipartite Metrics.
Discret. Appl. Math., 1995

Collapsing and lifting for the cut cone.
Discret. Math., 1994

The cut cone III: On the role of triangle facets.
Graphs Comb., 1993

(s, r; mu)-nets and alternating forms graphs.
Discret. Math., 1993

The even and odd cut polytopes.
Discret. Math., 1993

The inequicut cone.
Discret. Math., 1993

The hypermetric cone is polydedral.
Comb., 1993

Hypermetrics in geometry of numbers.
Proceedings of the Combinatorial Optimization, 1993

A characterization of knapsacks with the max-flow- - min-cut property.
Oper. Res. Lett., 1992

Facets for the cut cone II: Clique-web inequalities.
Math. Program., 1992

Facets for the cut cone I.
Math. Program., 1992

Clique-Web Facets for Multicut Polytopes.
Math. Oper. Res., 1992

Extension operations for cuts.
Discret. Math., 1992

The Metric Polytope.
Proceedings of the 2nd Integer Programming and Combinatorial Optimization Conference, 1992

New Results on Facets of the Cut Cone.
Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference, 1990

Complete Descriptions of Small Multicut Polytopes.
Proceedings of the Applied Geometry And Discrete Mathematics, 1990

The Symmetries of the Cut Polytope and of Some Relatives.
Proceedings of the Applied Geometry And Discrete Mathematics, 1990

A generalization of antiwebs to independence systems and their canonical facets.
Math. Program., 1989

On the geometric structure of independence systems.
Math. Program., 1989

Bouquets of geometric lattices: some algebraic and topological aspects.
Discret. Math., 1989

On the Facial Structure of Independence System Polyhedra.
Math. Oper. Res., 1988

A characterization of matroidal systems of inequalities.
Discret. Math., 1988

Upper Bounds for the Cardinality of s-Distances Codes.
Eur. J. Comb., 1986

Possible DNA modification in GC dinucleotides of Trypanosoma brucei telomeric sequences; relationship with antigen gene transcription.
Nucleic Acids Res., 1984