Content deleted Content added
applications: added French keyboard standard info. |
|||
Line 43:
In addition to the original plant ___location formulation, QAP is a mathematical model for the problem of placement of interconnected [[electronic component]]s onto a [[printed circuit board]] or on a [[integrated circuit|microchip]], which is part of the [[place and route]] stage of [[computer aided design]] in the electronics industry.
The QAP has also been used to model the cost of character placement on a keyboard. In this case, the locations are keys on the keyboard and their pairwise distances correspond to the time required to press a given pair of keys. The facilities are characters and their weights are proportional to how often the given pair of characters occur in a text corpus. This type of QAP model was used in the design of the French keyboard standard (NF Z71-300).<ref name="t142">{{cite book | last=John | first=Maximilian | last2=Karrenbauer | first2=Andreas | title=Mathematical Optimization Theory and Operations Research | chapter=Dynamic Sparsification for Quadratic Assignment Problems | publisher=Springer International Publishing | publication-place=Cham | volume=11548 | date=2019 | isbn=978-3-030-22628-2 | doi=10.1007/978-3-030-22629-9_17 | page=232–246|url=https://resources.mpi-inf.mpg.de/keyboardoptimization/MOTOR2019/MOTOR2019.pdf}}</ref>
==See also==
Line 48 ⟶ 50:
== References ==
{{Reflist}}
== Other sources ==
* {{cite book|author = [[Michael R. Garey]] and [[David S. Johnson]] | year = 1979 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness | publisher = W.H. Freeman | isbn = 0-7167-1045-5| title-link = Computers and Intractability: A Guide to the Theory of NP-Completeness }} A2.5: ND43, pg.218.
| |||