The quadratic M-convexity testing problem

DOI10.1016/J.DAM.2017.12.004MaRDI QIDQ1701120zbMATH OpenOpenAlexFDO

Authors Yuni Iwamasa

Publication date 22 February 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.02836

zbMATH Keywords

discrete convex analysisM-convextesting problem

Mathematics Subject Classification ID

Convex programming (90C25) Integer programming (90C10)

Abstract: M-convex functions, which are a generalization of valuated matroids, play a central role in discrete convex analysis. Quadratic M-convex functions constitute a basic and important subclass of M-convex functions, which has a close relationship with phylogenetics as well as valued constraint satisfaction problems. In this paper, we consider the quadratic M-convexity testing problem (QMCTP), which is the problem of deciding whether a given quadratic function on ${0,1}^n$ is M-convex. We show that QMCTP is co-NP-complete in general, but is polynomial-time solvable under a natural assumption. Furthermore, we propose an $O(n^2)$-time algorithm for solving QMCTP in the polynomial-time solvable case.

Recommendations

• Testing optimality for quadratic 0-1 problems
• Testing optimality for quadratic 0?1 unconstrained problems
• Remarks on solutions to a nonconvex quadratic programming test problem
• scientific article; zbMATH DE number 7758320
• scientific article; zbMATH DE number 2101525
• scientific article; zbMATH DE number 848086
• Construction of test problems in quadratic bivalent programming
• On quadratic and complete quadratic problems of convex programming
• Construction of large-scale global minimum concave quadratic test problems
• Hypothesis testing by convex optimization

Cites work

• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• A fast algorithm for constructing trees from distance matrices
• Convexity and Steinitz's exchange property
• Discrete Convex Analysis
• Discrete convexity in joint winner property
• Hybrid tractability of valued constraint problems
• Quadratic M-convex and L-convex functions
• Recent developments in discrete convex analysis
• Valuated matroids
• Valuated matroids: A new look at the greedy algorithm
• \(M\)-convex functions and tree metrics

Cited in

(7)

• \(M\)-convex functions and tree metrics
• Testing optimality for quadratic 0?1 unconstrained problems
• An efficient algorithm for minimizing M-convex functions under a color-induced budget constraint
• A tractable class of binary VCSPs via M-convex intersection
• Discrete convexity in joint winner property
• The minimax direction for the direct product of a convex cone with its application to testing problems
• Simple Tests for Classifying Critical Points of Quadratics with Linear Constraints

This page was built for publication: The quadratic M-convexity testing problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1701120)