Name
Title | ||
|---|---|---|
Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality |
Abstract | ||
|---|---|---|
. The problem of integer programming in bounded variables, overconstraints with no more than two variables in each constraint is NP-complete, evenwhen all variables are binary. This paper deals with integer linear minimizationproblems in n variables subject to m linear constraints with at most two variablesper inequality, and with all variables bounded between 0 and U . For such systems,a 2\Gammaapproximation algorithm is presented that runs in time O(mnU2log(Un2=m)),so it... |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1007/BF01585160 | Math. Program. |
Keywords | Field | DocType |
tight bound,integer program,2-approximation algorithm | Discrete mathematics,Approximation algorithm,Integer square root,Mathematical optimization,Combinatorics,Branch and price,Integer programming,Vertex cover,Time complexity,Optimization problem,Mathematics,Special ordered set | Journal |
Volume | Issue | ISSN |
62 | 1 | 1436-4646 |
Citations | PageRank | References |
57 | 4.08 | 12 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dorit S. Hochbaum | 1 | 4411 | 553.92 |
| Nimrod Megiddo | 2 | 4244 | 668.46 |
| Joseph (Seffi) Naor | 3 | 4173 | 365.63 |
| Arie Tamir | 4 | 1201 | 137.91 |