90C27 Combinatorial optimization
Refine
Document Type
- ZIB-Report (5)
Language
- English (5)
Has Fulltext
- yes (5)
Is part of the Bibliography
- no (5)
Keywords
Institute
- ZIB Allgemein (5)
In the online traveling salesman problem $OLTSP$ requests for visits to cities arrive online while the salesman is traveling. We study the $F{\_max}-OLTSP$ where the objective is to minimize the maximum flow time. This objective is particularly interesting for applications. Unfortunately, there can be no competitive algorithm, neither deterministic nor randomized. Hence, competitive analysis fails to distinguish online algorithms. Not even resource augmentation which is helpful in scheduling works as a remedy. This unsatisfactory situation motivates the search for alternative analysis methods. We introduce a natural restriction on the adversary for the $F{\_max}-OLTSP$ on the real line. A \emph{non-abusive adversary} may only move in a direction if there are yet unserved requests on this side. Our main result is an algorithm which achieves a constant competitive ratio against the non-abusive adversary.
In the problem of \emph{Online Call Admission in Optical Networks}, briefly called \textsc{oca}, we are given a graph $G=(V,E)$ together with a set of wavelengths~$W$ and a finite sequence $\sigma=r_1,r_2,\dots$ of calls which arrive in an online fashion. Each call~$r_j$ specifies a pair of nodes to be connected and an integral demand indicating the number of required lightpaths. A lightpath is a path in~$G$ together with a wavelength~$\lambda \in W$. Upon arrival of a call, an online algorithm must decide immediately and irrevocably whether to accept or to reject the call without any knowledge of calls which appear later in the sequence. If the call is accepted, the algorithm must provide the requested number of lightpaths to connect the specified nodes. The essential restriction is the wavelength conflict constraint: each wavelength is available only once per edge, which implies that two lightpaths sharing an edge must have different wavelengths. Each accepted call contributes a benefit equal to its demand to the overall profit. The objective in \textsc{oca} is to maximize the overall profit. Competitive algorithms for \textsc{oca} have been known for the special case where every call requests just a single lightpath. In this paper we present the first competitive online algorithms for the general case of larger demands.
Optimization is the task of finding an optimum solution to a given problem. When the decision variables are discrete we speak of a combinatorial optimization problem. Such a problem is online when decisions have to be made before all data of the problem are known. And we speak of a real-time online problem when online decisions have to be computed within very tight time bounds. This paper surveys the are of combinatorial online and real-time optimization, it discusses, in particular, the concepts with which online and real-time algorithms can be analyzed.
In the online traveling salesman problem requests for visits to cities (points in a metric space) arrive online while the salesman is traveling. The salesman moves at no more than unit speed and starts and ends his work at a designated origin. The objective is to find a routing for the salesman which finishes as early as possible. Performance of algorithms is measured through their competitive ratio, comparing the outcome of the algorithms with that of an adversary who provides the problem instance and therefore is able to achieve the optimal offline solution. Objections against such omnipotent adversaries have lead us to devise an adversary that is in a natural way, in the context of routing problems, more restricted in power. For the exposition we consider the online traveling salesman problem on the metric space given by the non-negative part of the real line. We show that a very natural strategy is~$3/2$-competitive against the conventional adversary, which matches the lower bound on competitive ratios achievable for algorithms for this problem. Against the more ``\emph{fair adversary}'', that we propose, we show that there exists an algorithm with competitive ratio $\frac{1+\sqrt{17}}{4}\approx 1.28$ and provide a matching lower bound. We also show competitiveness results for a special class of algorithms (called zealous algorithms) that do not allow waiting time for the server as long as there are requests unserved.
The traveling repairman problem (TRP) is a variant of the famous traveling salesman problem (TSP). The objective for the TRP is to minimize the latency, that is the the weighted sum of completion times of the cities, where the completion time of a city is defined to be the time in the tour before the city is reached. In the online traveling repairman problem (OLTRP) requests for visits to cities (points in a metric space) arrive online while the repairman is traveling. We analyze the performance of algorithms using competitive analysis, where the cost of an online algorithm is compared to that of an optimal offline algorithm. An optimal offline algorithm knows the entire request sequence in advance and can serve it with minimum cost. Recently, Feuerstein and Stougie presented a $9$-competitive algorithm for the OLTRP on the real line. In this paper we show how to use techniques from online-scheduling to obtain an $8$-competitive deterministic algorithm which works for any metric space. We also present a randomized algorithm which has a competitive ratio of $\frac{4}{\ln 2}\approx 5.7708$ against an oblivious adversary. All of our results also hold for the ``dial-a-ride'' generalization of the OLTRP, where objects have to be picked up and delivered by a server.