Name
Abstract | ||
|---|---|---|
In the generalized balanced optimization problem (GBaOP) the objective value $${\max_{e \in S}{|c(e)-k\max(S)|}}$$ is minimized over all feasible subsets S of E = {1, . . . , m}. We show that the algorithm proposed in Punnen and Aneja (Oper Res Lett 32:27–30, 2004) can be modified to ensure that the resulting solution is indeed optimal. This modification is attained at the expense of
increased worst-case complexity, but still maintains polynomial solvability of various special cases that are of general interest.
In particular, we show that GBaOP can be solved in polynomial time if an associated bottleneck problem can be solved in polynomial
time. For the solution of this bottleneck problem, we propose two alternative approaches. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/s00186-010-0331-4 | Math. Meth. of OR |
Keywords | Field | DocType |
combinatorial optimization · balanced optimization · bottleneck problems,polynomial time,optimization problem,combinatorial optimization | Discrete mathematics,Bottleneck,Combinatorics,Mathematical optimization,Polynomial,Combinatorial optimization,Time complexity,Optimization problem,Mathematics | Journal |
Volume | Issue | ISSN |
73 | 1 | 1432-2994 |
Citations | PageRank | References |
3 | 0.45 | 10 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lara Turner | 1 | 7 | 1.86 |
| Abraham P. Punnen | 2 | 630 | 56.52 |
| Yash P. Aneja | 3 | 73 | 11.08 |
| Horst W. Hamacher | 4 | 562 | 57.39 |