Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Quadratic bottleneck assignment problem
open-in-new
<p>In mathematics, the quadratic bottleneck assignment problem (QBAP) is one of the fundamental <a href="/facts/Combinatorial_optimization/PTcloS79">combinatorial optimization</a> problems in the branch of <a href="/facts/Optimization_(mathematics)/oRn8Iv5I">optimization</a> or <a href="/facts/Operations_research/H5yJkV5n">operations research</a>, from the category of the <a href="/facts/Optimal_facility_location/ssbU6ww2">facilities location</a> problems. </p><p>It is related to the <a href="/facts/Quadratic_assignment_problem/kQ5KJSb2">quadratic assignment problem</a> in the same way as the <a href="/facts/Linear_bottleneck_assignment_problem/pTVD5Pwa">linear bottleneck assignment problem</a> is related to the <a href="/facts/Linear_assignment_problem/dIMpM0aW">linear assignment problem</a>, the "sum" is replaced with "max" in the <a href="/facts/Objective_function/xv5ozuhl">objective function</a>. </p><p>The problem models the following real-life problem: </p> There are a set of <i>n</i> facilities and a set of <i>n</i> locations. For each pair of locations, a <i>distance</i> is specified and for each pair of facilities a <i>weight</i> or <i>flow</i> is specified (e.g., the amount of supplies transported between the two facilities). The problem is to assign all facilities to different locations with the goal of minimizing the maximum of the distances multiplied by the corresponding flows.