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

DOI10.4036/IIS.2015.L.03zbMATH Open1478.68102OpenAlexW2184055362MaRDI QIDQ5135262FDOQ5135262

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

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

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)

Cites Work

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

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)