The complexity of optimization on grids

DOI10.1007/S00453-019-00587-4MaRDI QIDQ2319631zbMATH OpenOpenAlexFDO

Authors Luis Barba, Malte Milatz, Jerri Nummenpalo, Xiaoming Sun, Antonis Thomas, Zhi-Jie Zhang, Jialin 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

zbMATH Keywords

optimizationlinear programmingunique-sink orientation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Deterministic algorithms for unique sink orientations of grids
• Unique Sink Orientations of Grids
• Unique sink orientations of grids
• Mathematical Foundations of Computer Science 2004
• scientific article; zbMATH DE number 1947444

Cites work

• scientific article; zbMATH DE number 1962814 (Why is no real title available?)
• scientific article; zbMATH DE number 3244470 (Why is no real title available?)
• A subexponential bound for linear programming
• Algorithms – ESA 2005
• Deterministic algorithms for unique sink orientations of grids
• 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
• Geometric applications of a matrix-searching algorithm
• Grid orientations, \((d,d+2)\)-polytopes, and arrangements of pseudolines
• Improved deterministic algorithms for linear programming in low dimensions
• Improved upper bounds for Random-Edge and Random-Jump on abstract cubes
• Jumping Doesn’t Help in Abstract Cubes
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• One line and n points
• Oriented Matroids
• Random edge can be exponential on abstract cubes
• Unique sink orientations of grids
• Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)
• Violator spaces: Structure and algorithms

Cited in

(5)

• Unique sink orientations of grids
• Unique Sink Orientations of Grids
• The hardness of the grid problemGi Under the Routine Resolution Method
• On Nonconservative Algorithms for Grid Interfaces
• Deterministic algorithms for unique sink orientations of grids

This page was built for publication: The complexity of optimization on grids

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