Name
Abstract | ||
|---|---|---|
We consider combinatorial optimization problems with a feasible solution set S ⊆{0,1} n specified by a system of linear constraints in 0–1 variables. Additionally, several cost functions c 1 ,…, c p are given. The max-linear objective function is defined by f ( x ):= max { c 1 x ,…, c p x : x ∈ S }; where c q :=( c q 1 ,…, c q n ) is for q =1,…, p an integer row vector in R n . The problem of minimizing f ( x ) over S is called the max-linear combinatorial optimization (MLCO) problem . We will show that MLCO is NP-hard even for the simplest case of S ⊆{0,1} n and p =2, and strongly NP-hard for general p . We discuss the relation to multi-criteria optimization and develop some bounds for MLCO. |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1016/0166-218X(93)90043-N | Discrete Applied Mathematics |
Keywords | Field | DocType |
max-linear objective function,combinatorial optimization,objective function,mathematics | Integer,Discrete mathematics,Combinatorics,Combinatorial optimization problem,Row vector,Multicriteria analysis,Combinatorial optimization,Solution set,Branch and bound method,Optimization problem,Mathematics | Journal |
Volume | Issue | ISSN |
42 | 2-3 | Discrete Applied Mathematics |
Citations | PageRank | References |
5 | 1.99 | 6 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sung-Jin Chung | 1 | 72 | 8.21 |
| Horst W. Hamacher | 2 | 562 | 57.39 |
| Francesco Maffioli | 3 | 271 | 44.39 |
| Katta G. Murty | 4 | 602 | 95.15 |