On the expected optimal value of random assignment problems: Experimental results and open questions
type: Item
instance of: scholarly article
title: On the expected optimal value of random assignment problems: Experimental results and open questions
zbMATH Open document ID: 0804.90108
DOI: 10.1007/BF01299451
author: K. Ramakrishnan
author: Panos M. Pardalos
published in: Computational Optimization and Applications
publication date: 1994-03-10T00:00:00Z
review text: An interior point algorithm is used to solve large-scale assignment problems whose data are random variables with the uniform and the exponential distributions. The computational results indicate the behaviour of the expected optimal value. Some open problems are discussed.
reviewed by: J.Mitev
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C06
zbMATH DE Number: 513313
zbMATH Keywords: random variables
zbMATH Keywords: interior point algorithm
zbMATH Keywords: large-scale assignment
MaRDI profile type: Publication
cites work: An implementation of Karmarkar's algorithm for linear programming
cites work: The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
cites work: Algorithm and Average-value Bounds for Assignment Problems
cites work: Order statistics and the linear assignment problem
cites work: A new polynomial-time algorithm for linear programming
cites work: Computational results of an interior point algorithm for large scale linear programming
cites work: Q3780760
cites work: Q3677509
cites work: Computational experience with a primal-dual interior point method for linear programming
cites work: Q4283454
cites work: A More Portable Fortran Random Number Generator
cites work: Probabilistic analysis of combinatorial algorithms: A bibliography with selected annotations
cites work: On the Expected Value of a Random Assignment Problem
Recommended article: Asymptotic behavior of the expected optimal value of the multidimensional assignment problem
Recommended article: Constructive bounds and exact expectations for the random assignment problem
Recommended article: Q3780760
Recommended article: Q3147236
Recommended article: A probabilistic feasibility and value analysis of the generalized assignment problem
Recommended article: A Lower Bound on the Expected Cost of an Optimal Assignment
Recommended article: Certain expected values in the random assignment problem
Recommended article: On the efficiency and optimality of random allocations
description: scientific article; zbMATH DE number 513313