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


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 ck
jobs. The goal is to assign the n ≤ ∑k=1mck 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 2O(1/ε2log3
+poly(1/ε,log n)+O(nlog 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


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


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.


  Getting Payday Loans In California should be thought of many times. Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.