The complexity of optimization on grids
From MaRDI portal
Publication:2319631
DOI10.1007/s00453-019-00587-4zbMath1429.68172OpenAlexW2947440460MaRDI QIDQ2319631
Malte Milatz, Luis Barba, Xiaoming Sun, Antonis Thomas, Zhijie Zhang, Jerri Nummenpalo, Jia-Lin Zhang
Publication date: 20 August 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-019-00587-4
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Unnamed Item
- Unnamed Item
- Unique sink orientations of grids
- Violator spaces: Structure and algorithms
- Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)
- Geometric applications of a matrix-searching algorithm
- Dynamic programming with convexity, concavity and sparsity
- Finding the sink takes some time: An almost quadratic lower bound for finding the sink of unique sink oriented cubes
- A subexponential bound for linear programming
- Random edge can be exponential on abstract cubes
- Grid orientations, \((d,d+2)\)-polytopes, and arrangements of pseudolines
- Deterministic Algorithms for Unique Sink Orientations of Grids
- Jumping Doesn’t Help in Abstract Cubes
- On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
- One line and n points
- Improved Deterministic Algorithms for Linear Programming in Low Dimensions
- Oriented Matroids
- Improved upper bounds for Random-Edge and Random-Jump on abstract cubes
- Algorithms – ESA 2005
This page was built for publication: The complexity of optimization on grids
