On Very Large Scale Assignment Problems

Yusin Lee and James B. Orlin
Additional contact information
Yusin Lee: Massachusetts Institute of Technology, Department of Civil Engineering
James B. Orlin: Massachusetts Institute of Technology, Sloan School of Management

A chapter in Large Scale Optimization, 1994, pp 206-244 from Springer

Abstract: Abstract In this paper we present computational testing results on very large scale random assignment problems. We consider a fully dense assignment problem with 2n nodes. Some conjectured or derived properties regarding fully dense assignment problems including the convergence of the optimal objective function value and the portion of nodes assigned with their kth best arc have been verified for networks up to n = 100,000 in size. Also we demonstrate the power of our approach in solving very large scale assignment problems by solving a one million node, one trillion arc random assignment problem.

Keywords: Assignment Problem; Cost Distribution; Short Path Tree; Task Node; Minimum Cost Flow Problem (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4613-3632-7_12

Ordering information: This item can be ordered from
http://www.springer.com/9781461336327

DOI: 10.1007/978-1-4613-3632-7_12

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().