Use a directed bipartite graph with one vertex for each job and one for each agent. Job vertices have supply and agent vertices demand . An arc from job to agent has cost and nonnegative flow ; an upper bound may be added, but is already implied by the balances. The minimum-cost flow formulation of the assignment problem is
Integer supplies and demands give an integral optimum by integrality of the transportation problem. Its positive arcs form a perfect matching, hence give one job per agent.
A network simplex algorithm basis for this connected -vertex network has tree arcs, whereas an integral assignment has only positive flows. For , at least basic tree arcs therefore carry zero flow. This unavoidable degeneracy in linear programming can cause zero-step pivots, extra bookkeeping and cycling unless an appropriate pivot rule is used. The Hungarian algorithm exploits the assignment structure directly rather than maintaining many zero-flow basic arcs.
Suppose the assignment dual potentials satisfy . For every feasible assignment ,
If the selected assignment uses only arcs with , its cost equals this lower bound. Weak duality and complementary slackness certify optimality. The PDF correctly denotes the feasible assignment by ; the TeX aid mistakenly replaces it with .
The Hungarian algorithm maintains feasible assignment dual potentials and a matching in a graph of zero reduced cost edges, where . Search for an augmenting path in a matching in this equality graph. If there is none, let be the reachable jobs and the reachable agents in the alternating search from unmatched jobs. Every agent in is matched to a job in . Set
Reduced costs from to its complement decrease by , those from outside into increase, and the remaining ones do not change. Thus feasibility and current matching equalities are preserved, while at least one new equality edge appears. Continue until an augmenting path in a matching increases the matching size. A perfect matching in the equality graph then has the same value as the dual linear program and is optimal.
For the example, start with the row minima and . The reduced cost matrix is
Match job to agent . Searching from both unmatched jobs gives and ; the minimum cost to an agent outside is . Update to and :
The new equality edge augments the matching. From unmatched job , the next alternating search reaches agent and its matched job , giving and . Now . The updated feasible assignment dual potentials and reduced costs are
The augmenting path in a matching uses job to agent , the reversed matched edge to job , then the new edge to agent . It gives the optimal assignment
The dual linear program value is , an independent optimality certificate.
Use the usual finite binary encoding of integer or rational input data. NP consists of decision problems whose yes-instances have polynomial-length certificates in computational complexity verifiable in polynomial time. A decision problem is NP-hard if every problem in NP has a polynomial-time many-one reduction to it. It is NP-complete if it is both NP-hard and in NP. An optimization problem is NP-hard when computing its optimum would solve every NP decision problem through a polynomial-time reduction and an optimum-value query; membership in NP applies directly to decision problems, not to an unqualified optimization task.
Reduce subset sum to the 0-1 knapsack problem by setting and . Every feasible value is at most , and the optimum equals exactly when the subset sum answer is yes. The transformation and final comparison take polynomial time. Since subset sum is assumed NP-complete, exact knapsack optimization is NP-hard.
For the half-approximation algorithm for knapsack, use nonnegative weights and profits. Delete overweight items and nonpositive-profit items; take all positive-profit zero-weight items for free. On the remaining positive-weight items, sort decreasing . Take the maximal initial prefix fitting the capacity, and stop at the first item that would overflow. Let be the prefix profit, and let be the largest profit of any individually feasible remaining item. Return the better of the prefix and that singleton, together with the free items. If every item fits, take them all.
The fractional knapsack problem fills exactly that prefix and a fraction of the first excluded item. Its optimum bounds the integer optimum, and without the free items its value is at most . Thus
With total free profit , the same inequality is . This gives an approximation ratio of in sorting time, with polynomial bit complexity for rational data. Nonnegative weights and capacity are the standard knapsack problem assumptions; unrestricted negative weights would not support this argument.
For the quadratic knapsack problem and its fractional row bound for quadratic knapsack, multiply the capacity inequality by the binary and use :
Remove items with first. If , the remaining coordinates are feasible in the fractional problem defining , so . If , that row's contribution is zero. Hence, with ,
The double sum counts each symmetric interaction twice; there is no factor in this problem. Each is a fractional knapsack problem, computable by sorting positive ratios, also handling zero weights separately. This takes polynomial time even when some interactions are negative, because an optional fractional item with negative profit is omitted.
The resulting 0-1 knapsack problem need not be solved exactly. Relax its capacity constraint with a Lagrange multiplier . Its Lagrangian knapsack bound is
For feasible , adding only increases its objective, and maximizing over independent binary choices produces the displayed expression. It is a convex piecewise-linear function with breakpoints at positive . Evaluate those breakpoints and zero, or use the fractional knapsack problem ordering; the best bound is computable in polynomial time. Thus computing all and one additional Lagrangian relaxation gives the requested upper bound.
For the numerical example, the problem has capacity and item ratios and . Select and . This gives
An exchange argument justifies optimality: capacity used on the lower-ratio item can be transferred to the higher-ratio item until the latter is full. The stated and similarly follow from residual capacities and . Therefore , with ratios . The fractional solution takes items and one-third of item , yielding . At the Lagrangian knapsack bound gives the same value:
The fractional solution attaining proves that this is the best bound from this auxiliary Lagrangian relaxation, though it need not be the exact quadratic optimum.
For branch and bound, branch on whether an unresolved is zero or one. If the selected set is , subtract its weight from the residual capacity and retain its exact objective as a constant. For each remaining item replace by , preserving the original interactions between remaining items. Recompute the fractional row bounds and the Lagrangian knapsack bound for that residual problem. Maintain an incumbent from genuine feasible binary solutions evaluated with the quadratic objective; prune infeasible nodes and nodes whose bound is no better than the incumbent. For example, selecting items gives the feasible value . A finite binary branching tree eventually certifies the optimum, but worst-case running time is exponential, as expected for an NP-hard problem.
Introduce integer-valued slack variables and . Write . The initial simplex dictionary is
In the simplex algorithm, let enter. The first constraint is the only limiting one, so leaves at . Substitution gives
Now enters and leaves: its ratio is smaller than the first row's ratio . The resulting simplex dictionary is
All nonbasic objective coefficients are nonpositive, and the basic values are nonnegative. Thus the continuous linear program has optimum
For integer programming, a row with integer variables yields the Gomory fractional cut , where is the fractional part. In the first row, the coefficient of on the left is , whose fractional part is , not . The two possible initial Gomory fractional cuts are therefore
Indeed . Choose the second row: implies , so its cut removes a strictly larger portion of the feasible polygon. This compares both printed alternatives before any further integer rounding.
Use the normalized integer slack variable , rather than an unnecessarily scaled cut slack. At the current basis,
The simplex dictionary is dual feasible but primal infeasible. In the dual simplex algorithm, leaves; the ratios of objective loss to improvement of this negative basic value are for and for , so enters. The pivot gives
The relaxed optimum is now , still nonintegral. The fractional row gives the next Gomory fractional cut
The negative left-hand coefficient of also has fractional part . Normalize the new integer slack variable as . Its dictionary row is . The dual simplex algorithm chooses to enter: its ratio is , compared with for . Substitution gives
Setting the nonbasic to zero gives a feasible integer solution. The final objective row bounds every point in the cut relaxation by , so the integer optimum is
Both cuts are valid for every original integer feasible point, making this also a certificate for the original integer program.

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact