On linear programs with random costs
From MaRDI portal
Publication:3724096
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
quadratic assignmentaverage complexityProbabilistic analysisbranch-and-bound algorithmsmutually independent nonnegative random coefficients
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
