Linear bottleneck assignment problem

Last updated November 27, 2023

In combinatorial optimization, a field within mathematics, the linear bottleneck assignment problem (LBAP) is similar to the linear assignment problem.^[1]

There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task in such a way that the maximum cost among the individual assignments is minimized.

The term "bottleneck" is explained by a common type of application of the problem, where the cost is the duration of the task performed by an agent. In this setting the "maximum cost" is "maximum duration", which is the bottleneck for the schedule of the overall job, to be minimized.

Formal definition

The formal definition of the bottleneck assignment problem is

Given two sets, A and T, together with a weight function C : A×T→ R . Find a bijection f : A→T such that the cost function:

\max _{a\in A}C(a,f(a))

is minimized.

Usually the weight function is viewed as a square real-valued matrix C, so that the cost function is written down as:

\max _{a\in A}C_{a,f(a)}

Mathematical programming formulation

\min \,\max _{i,j}c_{ij}x_{ij}

subject to:

\sum _{j=1}^{n}x_{ij}=1(i=1,2,\dots ,n),

\sum _{i=1}^{n}x_{ij}=1(j=1,2,\dots ,n),

x_{ij}\in \{0,1\}(i,j=1,2,\dots ,n)

Asymptotics

Let $c_{n}^{*}$ denote the optimal objective function value for the problem with n agents and n tasks. If the costs $c_{ij}$ are sampled from the uniform distribution on (0,1), then^[2]

E[c_{n}^{*}]={\frac {\log n+\log 2+\gamma }{n}}+O\left({\frac {(\log n)^{2}}{n^{7/5}}}\right)

and

Var[c_{n}^{*}]={\frac {\zeta (2)-2(\log 2)^{2}}{n^{2}}}+O\left({\frac {(\log n)^{2}}{n^{7/3}}}\right).

Related Research Articles

In the mathematical field of numerical analysis, interpolation is a type of estimation, a method of constructing (finding) new data points based on the range of a discrete set of known data points.

In machine learning, support vector machines are supervised learning models with associated learning algorithms that analyze data for classification and regression analysis. Developed at AT&T Bell Laboratories by Vladimir Vapnik with colleagues SVMs are one of the most robust prediction methods, being based on statistical learning frameworks or VC theory proposed by Vapnik and Chervonenkis (1974). Given a set of training examples, each marked as belonging to one of two categories, an SVM training algorithm builds a model that assigns new examples to one category or the other, making it a non-probabilistic binary linear classifier. SVM maps training examples to points in space so as to maximise the width of the gap between the two categories. New examples are then mapped into that same space and predicted to belong to a category based on which side of the gap they fall.

The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:

In mathematics, a low-discrepancy sequence is a sequence with the property that for all values of N, its subsequence x₁, ..., x_N has a low discrepancy.

In statistics, nonlinear regression is a form of regression analysis in which observational data are modeled by a function which is a nonlinear combination of the model parameters and depends on one or more independent variables. The data are fitted by a method of successive approximations.

The Gauss–Newton algorithm is used to solve non-linear least squares problems, which is equivalent to minimizing a sum of squared function values. It is an extension of Newton's method for finding a minimum of a non-linear function. Since a sum of squares must be nonnegative, the algorithm can be viewed as using Newton's method to iteratively approximate zeroes of the components of the sum, and thus minimizing the sum. In this sense, the algorithm is also an effective method for solving overdetermined systems of equations. It has the advantage that second derivatives, which can be challenging to compute, are not required.

A Hopfield network is a form of recurrent artificial neural network and a type of spin glass system popularised by John Hopfield in 1982 as described by Shun'ichi Amari in 1972 and by Little in 1974 based on Ernst Ising's work with Wilhelm Lenz on the Ising model. Hopfield networks serve as content-addressable ("associative") memory systems with binary threshold nodes, or with continuous variables. Hopfield networks also provide a model for understanding human memory.

In mathematics, a moment problem arises as the result of trying to invert the mapping that takes a measure $to the sequence of moments$

In mathematics, an elliptic boundary value problem is a special kind of boundary value problem which can be thought of as the stable state of an evolution problem. For example, the Dirichlet problem for the Laplacian gives the eventual distribution of heat in a room several hours after the heating is turned on.

The study of facility location problems (FLP), also known as location analysis, is a branch of operations research and computational geometry concerned with the optimal placement of facilities to minimize transportation costs while considering factors like avoiding placing hazardous materials near housing, and competitors' facilities. The techniques also apply to cluster analysis.

Non-linear least squares is the form of least squares analysis used to fit a set of m observations with a model that is non-linear in n unknown parameters (m ≥ n). It is used in some forms of nonlinear regression. The basis of the method is to approximate the model by a linear one and to refine the parameters by successive iterations. There are many similarities to linear least squares, but also some significant differences. In economic theory, the non-linear least squares method is applied in (i) the probit regression, (ii) threshold regression, (iii) smooth regression, (iv) logistic link regression, (v) Box–Cox transformed regressors ( $).$

The maximum coverage problem is a classical question in computer science, computational complexity theory, and operations research. It is a problem that is widely taught in approximation algorithms.

David Bernard Shmoys is a Professor in the School of Operations Research and Information Engineering and the Department of Computer Science at Cornell University. He obtained his Ph.D. from the University of California, Berkeley in 1984. His major focus has been in the design and analysis of algorithms for discrete optimization problems.

In graph theory, the graph bandwidth problem is to label the $n$ vertices $v i$ of a graph $G$ with distinct integers $so that the quantity is minimized . The problem may be visualized as placing the vertices of a graph at distinct integer points along the x -axis so that the length of the longest edge is minimized. Such placement is called linear graph arrangement, linear graph layout or linear graph placement .$

Randomized (Block) Coordinate Descent Method is an optimization algorithm popularized by Nesterov (2010) and Richtárik and Takáč (2011). The first analysis of this method, when applied to the problem of minimizing a smooth convex function, was performed by Nesterov (2010). In Nesterov's analysis the method needs to be applied to a quadratic perturbation of the original function with an unknown scaling factor. Richtárik and Takáč (2011) give iteration complexity bounds which do not require this, i.e., the method is applied to the objective function directly. Furthermore, they generalize the setting to the problem of minimizing a composite function, i.e., sum of a smooth convex and a convex block-separable function:

<span class="mw-page-title-main">Matrix completion</span>

Matrix completion is the task of filling in the missing entries of a partially observed matrix, which is equivalent to performing data imputation in statistics. A wide range of datasets are naturally organized in matrix form. One example is the movie-ratings matrix, as appears in the Netflix problem: Given a ratings matrix in which each entry $represents the rating of movie by customer, if customer has watched movie and is otherwise missing, we would like to predict the remaining entries in order to make good recommendations to customers on what to watch next. Another example is the document-term matrix: The frequencies of words used in a collection of documents can be represented as a matrix, where each entry corresponds to the number of times the associated term appears in the indicated document.$

In machine learning and mathematical optimization, loss functions for classification are computationally feasible loss functions representing the price paid for inaccuracy of predictions in classification problems. Given $as the space of all possible inputs, and as the set of labels, a typical goal of classification algorithms is to find a function which best predicts a label for a given input . However, because of incomplete information, noise in the measurement, or probabilistic components in the underlying process, it is possible for the same to generate different . As a result, the goal of the learning problem is to minimize expected loss, defined as$

Regularized least squares (RLS) is a family of methods for solving the least-squares problem while using regularization to further constrain the resulting solution.

Graph cut optimization is a combinatorial optimization method applicable to a family of functions of discrete variables, named after the concept of cut in the theory of flow networks. Thanks to the max-flow min-cut theorem, determining the minimum cut over a graph representing a flow network is equivalent to computing the maximum flow over the network. Given a pseudo-Boolean function $, if it is possible to construct a flow network with positive weights such that$

In fractal geometry, the Higuchi dimension (or Higuchi fractal dimension (HFD)) is an approximate value for the box-counting dimension of the graph of a real-valued function or time series. This value is obtained via an algorithmic approximation so one also talks about the Higuchi method. It has many applications in science and engineering and has been applied to subjects like characterizing primary waves in seismograms, clinical neurophysiology and analyzing changes in the electroencephalogram in Alzheimer’s disease.

References

↑ Assignment Problems, by Rainer Burkard, Mauro Dell'Amico, Silvano Martello, 2009, Chapter 6.2 "Linear Bottleneck Assignment Problem" (p. 172)
↑ Spivey, Michael Z. (2011). "Asymptotic Moments of the Bottleneck Assignment Problem". Mathematics of Operations Research . 36 (2): 205–226. doi:10.1287/moor.1110.0493.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Assignment Problems, by Rainer Burkard, Mauro Dell'Amico, Silvano Martello, 2009, Chapter 6.2 "Linear Bottleneck Assignment Problem" (p. 172)

[2] Spivey, Michael Z. (2011). "Asymptotic Moments of the Bottleneck Assignment Problem". Mathematics of Operations Research . 36 (2): 205–226. doi:10.1287/moor.1110.0493.

[1]

[2]