On linear programs with random costs

DOI10.1007/BF01589437MaRDI QIDQ3724096zbMATH OpenOpenAlexWikidataFDO

Authors Martin Dyer, Alan Frieze, Colin McDiarmid

Publication date 1986

Published in Mathematical Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01589437

zbMATH Keywords

quadratic assignmentaverage complexitybranch-and-bound algorithmsProbabilistic analysismutually independent nonnegative random coefficients

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Stochastic programming (90C15) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Stochastic analysis (60H99)

Recommendations

• scientific article; zbMATH DE number 3945879
• The random linear bottleneck assignment problem
• Bounds for random binary quadratic programs
• scientific article; zbMATH DE number 59500
• Probabilistic analysis of optimization algorithms - some aspects from a practical point of view

Cites work

• scientific article; zbMATH DE number 4199950 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Complexity of a 3-dimensional assignment problem
• On the Expected Value of a Random Assignment Problem
• On the greedy algorithm with random costs
• On the quadratic assignment problem
• Probability Inequalities for Sums of Bounded Random Variables
• The asymptotic probabilistic behaviour of quadratic sum assignment problems

Cited in

(22)

• On the greedy algorithm with random costs
• The expected number of extreme points of a random linear program
• Selected topics on assignment problems
• Exploiting partial correlations in distributionally robust optimization
• Linear programming — Randomization and abstract frameworks
• Constructive bounds and exact expectations for the random assignment problem
• Probabilistische analyse von heuristiken der kombinatorischen optimierung – ein überbllck
• A lower bound on the expected optimal value of certain random linear programs and application to shortest paths in directed acyclic graphs and reliability
• Combinational optimization problems for which almost every algorithm is asymptotically optimal
• Asymptotics in the random assignment problem
• Random assignment problems
• Asymptotic behavior of the quadratic knapsack problem
• Perturbation analysis of linear programming problems with random parameters
• The (2) limit in the random assignment problem
• Random linear programs with many variables and few constraints
• scientific article; zbMATH DE number 5281650 (Why is no real title available?)
• scientific article; zbMATH DE number 59500 (Why is no real title available?)
• Graph-Based Equilibrium Metrics for Dynamic Supply–Demand Systems With Applications to Ride-sourcing Platforms
• Bounds for random binary quadratic programs
• On the average condition of random linear programs
• Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem
• Efficient algorithms for three‐dimensional axial and planar random assignment problems

This page was built for publication: On linear programs with random costs

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