Name
Abstract | ||
|---|---|---|
Good bounds on the optimum value of hard optimization problems can often be efficiently obtained by pricing out certain bad constraints and incorporating them into the objective function. The resulting problem is known as the Lagrangian dual. Here we give improved algorithms for solving the Lagrangian duals of problems that have both of the following properties. First, in the absence of the bad constraints, the problems can be solved in strongly polynomial time by combinatorial algorithms. Second, the number of bad constraints is fixed. As part of our solution to these problems, we extend Cole's circuit simulation approach and develop a weighted version of Megiddo's multidimensional search technique. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1007/3-540-56287-7_103 | FSTTCS |
Keywords | Field | DocType |
lagrangian dual,objective function,optimization problem,polynomial time | Discrete mathematics,Mathematical optimization,Combinatorics,Lagrangian,Linear form,Computer science,Quadratic assignment problem,Dual polyhedron,Lagrangian relaxation,Time complexity,Linear inequality,Optimization problem | Conference |
Volume | ISSN | ISBN |
652 | 0302-9743 | 3-540-56287-7 |
Citations | PageRank | References |
1 | 0.37 | 12 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Richa Agarwala | 1 | 310 | 58.02 |
| David Fernández-Baca | 2 | 201 | 23.65 |