On linear programs with random costs

DOI10.1007/BF01589437zbMath0593.90061OpenAlexW2089514086WikidataQ56324153 ScholiaQ56324153MaRDI QIDQ3724096

Martin Dyer, Alan M. Frieze, Colin J. H. 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 complexityProbabilistic analysisbranch-and-bound algorithmsmutually 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)

Related Items

Graph-Based Equilibrium Metrics for Dynamic Supply–Demand Systems With Applications to Ride-sourcing Platforms, A lower bound on the expected optimal value of certain random linear programs and application to shortest paths in directed acyclic graphs and reliability, Asymptotic behavior of the quadratic knapsack problem, Probabilistische analyse von heuristiken der kombinatorischen optimierung – ein überbllck, Combinational optimization problems for which almost every algorithm is asymptotically optimal, Exploiting partial correlations in distributionally robust optimization, Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem, The ?(2) limit in the random assignment problem, Random assignment problems, Asymptotics in the random assignment problem, Selected topics on assignment problems, Efficient algorithms for three‐dimensional axial and planar random assignment problems, Constructive bounds and exact expectations for the random assignment problem, On the greedy algorithm with random costs

Cites Work

• Unnamed Item
• Unnamed Item
• On the quadratic assignment problem
• Complexity of a 3-dimensional assignment problem
• On the Expected Value of a Random Assignment Problem
• The asymptotic probabilistic behaviour of quadratic sum assignment problems
• On the greedy algorithm with random costs
• Probability Inequalities for Sums of Bounded Random Variables