Back to Search
Start Over
Efficient algorithms for three-dimensional axial and planar random assignment problems
- Source :
- Random Structures & Algorithms. 46:160-196
- Publication Year :
- 2013
- Publisher :
- Wiley, 2013.
-
Abstract
- Beautiful formulas are known for the expected cost of random two-dimensional assignment problems, but in higher dimensions even the scaling is not known. In three dimensions and above, the problem has natural “Axial” and “Planar” versions, both of which are NP-hard. For 3-dimensional Axial random assignment instances of size n, the cost scales as Ω(1/ n), and a main result of the present paper is a linear-time algorithm that, with high probability, finds a solution of cost O(n–1+o(1)). For 3-dimensional Planar assignment, the lower bound is Ω(n), and we give a new efficient matching-based algorithm that with high probability returns a solution with cost O(n log n)
- Subjects :
- FOS: Computer and information sciences
Discrete mathematics
Matching (graph theory)
Random assignment
Efficient algorithm
Applied Mathematics
General Mathematics
Computer Graphics and Computer-Aided Design
Upper and lower bounds
Planar
Computer Science - Data Structures and Algorithms
FOS: Mathematics
19999 Mathematical Sciences not elsewhere classified
Mathematics - Combinatorics
Data Structures and Algorithms (cs.DS)
Probabilistic analysis of algorithms
QA Mathematics
Combinatorics (math.CO)
Time complexity
Scaling
Software
Mathematics
Subjects
Details
- ISSN :
- 10429832
- Volume :
- 46
- Database :
- OpenAIRE
- Journal :
- Random Structures & Algorithms
- Accession number :
- edsair.doi.dedup.....911dd1c1cf880ca61834ce10046b0c81