Titlebook: Approximation Algorithms for Combinatorial Optimization; International Worksh Klaus Jansen,José Rolim Conference proceedings 1998 Springer-

共同给与

谈判

业余爱好者

MIR

Lower bounds for on-line scheduling with precedence constraints on identical machines,ement, and may depend on other jobs (has to be processed after them). A job arrives only after its predecessors have been completed. The cost of an algorithm is the time that the last job is completed. We show lower bounds on the competitive ratio of on-line algorithms for this problem in several ve

名次后缀

Instant recognition of half integrality and 2-approximations, form . ≤ ., where the variable . appears only in that constraint. For such binary integer programs it is possible to derive half integral superoptimal solutions in polynomial time. The scheme is also applicable with few modifications to nonbinary integer problems. For some of these problems it is p

出生

The ,-vertex cover problem: Extending the half integrality framework with budget constraints,half integral solution to such problems. These solutions can be used under certain conditions to generate 2-approximations. Here we extend these results to problems involving budget constraints that do not conform to the structure of that class. Specifically, we address the .-vertex cover problem re

的阐明

愤世嫉俗者

BAIT

Approximating circular arc colouring and bandwidth allocation in all-optical ring networks,domized approximation algorithm for the arc colouring problem, an improvement over the best previously known performance ratio of 5/3. For the problem of allocating bandwidth in an all-optical . ring network, we present a factor-of-(1.5+1/2.+.(1)) randomized approximation algorithm, improving upon t

极深