## Invited Session Fri.1.H 3004

#### Friday, 10:30 - 12:00 h, Room: H 3004

**Cluster 2: Combinatorial optimization** [...]

### Approximation algorithms for hard problems

**Chair: Guochuan Zhang**

**Friday, 10:30 - 10:55 h, Room: H 3004, Talk 1**

**Lin Chen**

Approximation algorithms for scheduling parallel machines with capacity constraints

**Coauthors: Klaus Jansen, Wenchang Luo, Guochuan Zhang**

**Abstract:**

In this paper, we consider the classical scheduling problem on

parallel machines with capacity constraints. We are given *m*

identical machines, where each machine *k* can process up to *c*_{k}

jobs. The goal is to assign the *n ≤ ∑*_{k=1}^{m}c_{k} independent

jobs on the machines subject to the capacity constraints such that

the makespan is minimized. This problem is a generalization of

*c*-partition, which is strongly NP-hard for *c ≥ 3* and the best

known approximation algorithm of which has a performance ratio of

4/3 due to Babel et al..

We deal with the general problem and improve the previous results by

establishing an efficient polynomial time approximation scheme

(EPTAS) whose running time is at most *2*^{O(1/ε2log3(1/ε))}+poly(1/ε,*log* n)+O(n*log* n). We develop a best-fit schedule for small

jobs, and then handle the assignment of big jobs through a mixed

integer programming (MILP). Such an MILP consists of a huge number

of integer variables which is not even a constant, however, we would

provide a greedy rounding technique to modify it iteratively so that the number of its integer and fractional variables is sharply reduced.

**Friday, 11:00 - 11:25 h, Room: H 3004, Talk 2**

**Guangting Chen**

Approximation algorithms for parallel open shop scheduling

**Coauthors: Yong Chen, An Zhang**

**Abstract:**

This paper investigates a new scheduling problem, namely the parallel open shop scheduling.

In this problem, each job consists of two operations, which must be non-preemptively processed by one of the *m* two-stage parallel open shops.

The objective is to minimize the makespan. As the problem is NP-hard, we provide the first approximation algorithm with a worst case ratio

of *2* for *m* machines, and for *m=2*, an improved algorithm with worst case ration *3/2* is further proposed. Both algorithms run in *O(n **log* n) time.

**Friday, 11:30 - 11:55 h, Room: H 3004, Talk 3**

**Xudong Hu**

New models for network connection problems with interval data

**Coauthors: E. Alvarez-Miranda, Xujin Chen, Jie Hu, Bi Li**

**Abstract:**

In this talk, I will present a new approach for dealing with network connection problems

with uncertain parameters, where, it is assumed, cost on a link/node in a given network

fall into an interval. We introduced two risk models for these problems, proposed

polynomial-time algorithms for solving the problems and conducted computational

experiments on algorithms proposed. Our theoretical and computational results show

the flexibility of this new approach for decision makers at different levels of aversion to

risk, as well as satisfactory performance of standard CPLEX solver on our model.