𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the approximability of an interval scheduling problem

✍ Scribed by Frits C. R. Spieksma

Publisher
Springer US
Year
1999
Tongue
English
Weight
148 KB
Volume
2
Category
Article
ISSN
1094-6136

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we consider a general interval scheduling problem. The problem is a natural generalization of "nding a maximum independent set in an interval graph. We show that, unless P"NP, this maximization problem cannot be approximated in polynomial time within arbitrarily good precision. On the other hand, we present a simple greedy algorithm that delivers a solution with a value of at least times the value of an optimal solution. Finally, we investigate the quality of an LP-relaxation of a formulation for the problem, by establishing an upper bound on the ratio between the value of the LP-relaxation and the value of an optimal solution.

πŸ“œ SIMILAR VOLUMES

The impact of approximate evaluation on
The impact of approximate evaluation on the performance of search algorithms for warehouse scheduling
✍ Watson, J. P. (author);Rana, S. (author);Whitley, L. D. (author);Howe, A. E. (au πŸ“‚ Article πŸ“… 1999 πŸ› Springer Netherlands 🌐 English βš– 254 KB πŸ‘ 2 views

The Coors warehouse scheduling problem involves finding a permutation of customer orders that minimizes the average time that customers' orders spend at the loading docks while at the same time minimizing the running average inventory, Search-based solutions require fast objective functions. Thus, a

Deferred-query: An efficient approach fo
Deferred-query: An efficient approach for some problems on interval graphs
✍ Chang, Maw-Shang; Peng, Sheng-Lung; Liaw, Jenn-Liang πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 99 KB πŸ‘ 2 views

This paper introduces the idea of a deferred-query approach to design O(n) algorithms for the domatic partition, optimal path cover, Hamiltonian path, Hamiltonian circuit, and maximum matching problems on interval graphs given n endpoint-sorted intervals. The previous best-known algorithms run in O(

An improved approximation scheme for the
An improved approximation scheme for the Group Steiner Problem
✍ C. S. Helvig; Gabriel Robins; Alexander Zelikovsky πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 322 KB

the Group Steiner Problem asks for a minimumcost tree which contains at least one node from each group N i N i N i . In this paper, we give polynomial-time O O O(k k k )approximation algorithms for any fixed > > > 0. This result improves the previously known O O O(k k k)-approximation. We also apply

Measurement-scheduled control for the RT
Measurement-scheduled control for the RTAC problem: an LMI approach
✍ StΓ©phane Dussy; Laurent El Ghaoui πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 430 KB πŸ‘ 1 views

The RTAC nonlinear control design benchmark problem is addressed using a multi-objective control methodology based on linear matrix inequalities and robust control. The approach hinges on the search for a common quadratic Lyapunov function ensuring various specifications (stability, L -gain, command