Do you want BuboFlash to help you learning these things? Or do you want to add or correct something? Click here to log in or create user.

#computation #social-choice

1.5.2 Linear and Integer Programming One notable computational problem is that of solving linear programs. A linear program consists of a set of variables x j (1 j n), a set of constraints indexed by i (1 i m), and an objective. Constraint i is defined by parameters a ij (1 j n) and b i , resulting in the following inequality constraint: n j=1 a ij x j b i . The objective is defined by parameters c j , resulting in the following objective: n j=1 c j x j . The goal is to find a vector of nonnegative values for the x j that maximizes the value of the objective while still meeting all the constraints (i.e., all the inequalities should hold). Natural variants, such as not requiring variables to take nonnegative values, allowing equality constraints, having a minimization rather than a maximization objective, and so on, are not substantively different from this basic setup. There is a rich theory of linear programming; for the purpose of this book, what is most important to know is that linear programs can be solved to optimality in polynomial time. Thus, if a computational problem can be formulated as (equivalently, reduced to) a polynomial- sized linear program, then it can be solved in polynomial time.

If you want to change selection, open document below and click on "Move attachment"

status | not read | reprioritisations | ||
---|---|---|---|---|

last reprioritisation on | suggested re-reading day | |||

started reading on | finished reading on |

Do you want to join discussion? Click here to log in or create user.