|
A P P O L I I W o r k s h o p September 12–13, 2003 |
|
|
Contact: appol@jgytf.u-szeged.hu |
|
|
Friday, September 12, 2003 8.30-9.00 Reception 9.00-9.40 Klaus Jansen: Approximation algorithms for the max-min resource sharing problem (Abstract) 9.40-10.20 Stamatis Stefanakos: Wavelength Conversion in Shortest-Path All-Optical Networks (Abstract) 10.20-10.40 Coffee break 10.40-11.20 Matus Mihalak, Gabor Szabo, Marc Nunkesser: An algorithmic view on OVSF assignment (Abstract) 11.20-12.00 Guochuan Zhang, Klaus Jansen, D. Ye: Scheduling parallel jobs on networks (Abstract) 12.00-13.00 Lunch 13.00-19.00 Excursion to the National Historical Memorial Park, Ópusztaszer (http://www.opusztaszer.hu) 19.00- Dinner
Saturday, September 13, 2003 9.00-9.40 Joris van de Klundert: Scheduling with materials requirements constraints. (Abstract) 9.40-10.20 András Erik Csallner: Approximation algorithms using interval arithmetic (Abstract) 10.20-11.00 Aleksei Fishkin: Scheduling Multicast Traffic in Star Coupled WDM LANs: The Open Block Problem (Abstract) 11.00-11.20 Coffee break 11.20-12.00 Sai Anand: Pre-routed Call Admission Control (Abstract) 12.00-12.40 Foto Afrati: Towards Comprehensive Web Mining − Searching for Web Communities (Abstract) 13.00-15.00 Lunch 15.00-17.00 Guided sightseeing tour Abstracts Klaus Jansen: Approximation algorithms for the max-min resource sharing problem We propose an improved approximation algorithm for the general max-min resource sharing (and fractional covering) problem with M nonnegative concave (or linear) constraints on a convex set B. The algorithm (based on a Lagrangian decomposition method) uses an approximate block solver that solves a simpler maximization problem over the convex set B (called the block problem) approximately with raio c >= 1. We show that our algorithm achieves within O(M epsilon^{-2} ln(M epsilon^{-1})) iterations or calls to the approximate block solver a solution for the max-min resource sharing (and fractional covering) problem with approximation ratio c /(1- epsilon). Our algorithm is the first one for both problems where the number of iterations is independent of the width and the approximation ratio c.
Stamatis Stefanakos: Wavelength Conversion in Shortest-Path All-Optical Networks We consider all-optical networks with shortest-path routing that use wavelength-division multiplexing and employ wavelength conversion at specific nodes in order to maximize their capacity usage. We present efficient algorithms for deciding whether a placement of wavelength converters allows the network to run at maximum capacity, and for finding an optimal wavelength assignment when such a placement of converters is known. Our algorithms apply to both undirected and directed networks. Furthermore, we show that the problem of finding an optimal placement of converters is $\APX$-hard in both undirected and directed networks. Finally, we give a polynomial-time algorithm for finding an optimal placement of converters in undirected triangle-free networks, and show that the problem remains $\NP$-hard in bidirected triangle-free planar networks.
Matus Mihalak, Gabor Szabo, Marc Nunkesser: An algorithmic view on OVSF assignment Recently UMTS has received a lot of attention, and also raised new algorithmic problems. In this talk we focus on a specific aspect of its multiple access method DS-CDMA, that turns out to be of algorithmic interest. The DS-CDMA method makes it possible for all users in one cell to share the bandwidth by assigning them Orthogonal Variable Spreading Factor (OVSF-) codes. This assignment is straight-forward, as long as only a few users request such codes. In cells with many users new code requests can make code reassignments necessary. We give and analyze algorithms that aim at minimizing the number of such necessary reassignments. We show that existing algorithms for the underlying code assignment (CA-) problem are erroneous, and that its offline version is NP-complete. Finally, we argue that the online-version of the CA-problem is the most natural one.
Guochuan Zhang, Klaus Jansen, D. Ye: Scheduling parallel jobs on networks We consider a parallel computer system with an interconnection topology, such as PRAMs, Lines and Meshes. Several processors can execute a job simultaneously if they are connected in the underlying network. A parallel job requires a fixed number of processors or a specified subsystem of a certain size for its execution at a time. Our goal is to assign the parallel jobs to the processors so that the makespan is minimized or the throughput is maximized. In many cases parallel job scheduling is related to rectangle packing. Steinberg [SIAM J Computing 26, 401-409, 1997] gave a sufficient condition to determine if a number of rectangles can be packed into a rectangular bin. We make a further extension of his theorem and apply it to several parallel job scheduling problems. We either improve the previous results or obtain some new results.
Joris van de Klundert : Scheduling with materials requirements constraints Classical and widely used MRP systems order raw materials for anticipated production. However, while these decisions are being taken, actual orders are not known and (therefore) actual scheduling of jobs is not taken into account. In this talk we identify and study the scheduling problems that play a role in this setting. We present exact and approximate algorithms, including worst case analysis and computational results. In addition, we study high multiplicity properties of these problems.
András Erik Csallner: Approximation Algorithms Using Interval Arithmetic In the last five decades from the invention of interval arithmetic (due to Sunaga and Moore) to now much has been done to grow this notion to a useful tool in both computations and numerical proofs. Using closed intervals instead of real numbers gives the opportunity to control all errors automatically and give guaranteed correct lower and upper bounds on a calculated real value. With the aid of branch and bound methods it is also possible to tighten these inclusions to a desired accuracy. In the presentation the notion of machine intervals is thoroughly introduced, the easiest way of generating interval inclusions is shown, and using a model algorithm for the interval branch and bound methods for global optimization the pivoting points of refining interval results is discussed.
Aleksei Fishkin: Scheduling Multicast Traffic in Star Coupled WDM LANs: The Open Block Problem" Wavelength Division Multiplexing (WDM) is the current favorite technology for building optical communication networks. WDM supports multiple wavelengths (channels) on a single fiber. In broadcast WDM local area networks (LANs), where all nodes are combined using a passive star coupler, information transmitted on any channel is broadcast to the entire set of nodes, but it only received by those with a receiver listening on that channel. This broadcast future makes it possible to design scheduling algorithms such that a single transmission of multicast packet can reach all nodes in the packet's destination set simultaneously. In two basic cases, the problem of scheduling multicast traffic in Star Coupled WDM LANs can be modeled as the multiprocessor dedicated task scheduling problem and the open shop problem. Here, considering the general case, we introduce a new scheduling problem, called the open block problem. We derive a number of polynomial time solvable cases, provide hardness results, and present several approximation algorithms.
Sai Anand: Pre-routed Call Admission Control Call admission control deals with accepting and routing decisions of call requests. In pre-routed call control a protocol or strategy fixes unique routes for calls. In this case, the call control algorithm has to make only acceptance and rejection decisions. The bandwidth constraints on links imply that the number of calls that are routed through an edge cannot exceed the capapcity.The objective of call control is to maximize the number (or profits) of accepted call requests under the bandwidth limitation. In this talk we restrict the communication network to be a cycle. We present a simple 2-approximation algorithm for maximizing the profits of accepted calls. Discuss special cases for which the problem can be solved optimally. Finally, derive that our problem is as hard as the "exaact matching problem", whose computational complexity has not been resolved to be in P or NP-hard. This derivation is an easy re-working of a recent result by Hochbaum et al. on cyclic scheduling.
Foto Afrati: Towards Comprehensive Web Mining − Searching for Web Communities. We have developed a novel algorithm for searching the web to find web communities. The algorithm is based on pattern matching techniques. We will present the algorithm and discuss its performance. Also, we will discuss implementation issues and especially an efficient crawler..
|
|
