Exploring the limits of subadditive approaches: parallels between optimization and complexity theory

DOI10.4036/IIS.2015.L.03MaRDI QIDQ5135262zbMATH OpenOpenAlexFDO

Authors Kenya Ueno

Publication date 19 November 2020

Published in Interdisciplinary Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4036/iis.2015.l.03

zbMATH Keywords

linear programminginteger programmingformula complexity

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Integer programming (90C10)

Recommendations

• Subadditive approaches in integer programming
• scientific article; zbMATH DE number 2086935
• scientific article; zbMATH DE number 3922389
• Publication:4725744
• On the complexity of nonlinear mixed-integer optimization

Cites work

• scientific article; zbMATH DE number 5485488 (Why is no real title available?)
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3664742 (Why is no real title available?)
• scientific article; zbMATH DE number 176877 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 1929951 (Why is no real title available?)
• scientific article; zbMATH DE number 780788 (Why is no real title available?)
• scientific article; zbMATH DE number 3431974 (Why is no real title available?)
• scientific article; zbMATH DE number 2223038 (Why is no real title available?)
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A New Rank Technique for Formula Size Lower Bounds
• A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• A note on the quasi-additive bound for Boolean functions
• A strong dual for conic mixed-integer programs
• A stronger LP bound for formula size lower bounds via clique constraints
• Better lower bounds for monotone threshold formulas
• Boolean function complexity. Advances and frontiers.
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Breaking the rectangle bound barrier against formula size lower bounds
• Complexity of the realization of a linear function in the class of -circuits
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Duality for mixed-integer linear programs
• Explicit lower bound of 4.5n - o(n) for boolena circuits
• Fractional Covers and Communication Complexity
• Geometric algorithms and combinatorial optimization
• Global optimization with polynomials and the problem of moments
• Improvements on Khrapchenko's theorem
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Natural proofs
• On convex complexity measures
• Paths, Trees, and Flowers
• Polynomial degree vs. quantum query complexity
• Short monotone formulae for the majority function
• Subadditive approaches in integer programming
• The Shrinkage Exponent of de Morgan Formulas is 2
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• The quantum adversary method and classical formula size power bounds
• Tighter representations for set partitioning problems

This page was built for publication: Exploring the limits of subadditive approaches: parallels between optimization and complexity theory

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