Search

… MLTD

23rd MLTD Biennial International Congress on Thrombosis -- MAY 14-17, 2014 -- Valencia, SPAIN, WOS: 000338292900290, …, MLTD

Given a network together with a set of connection requests, call admission control is the problem of deciding which calls to accept and which ones to reject in order to maximize the total profit of the accepted requests. We consider call admission control problems with advance reservations in star networks. For the most general variant we present a constant-factor approximation algorithm resolving an open problem due to Erlebach. Our method is randomized and achieves an approximation ratio of 1/18. It can be generalized to accommodate call alternatives, in which case the approximation ratio is 1/24. We show how our method can be derandomized. In addition we prove that call admission control in star networks is ${\mathcal APX}$-hard even for very restricted variants of the problem.

The aim of this study is to investigate the effects of exogenous l-arginine and HDL on LDL and oxidized LDL (ox-LDL)-mediated platelet activation. Adenosine diphosphate (ADP)-activated platelets have been incubated with lipoproteins with or without l-arginine. P-selectin receptor numbers per platelet have been measured by flow cytometry. After incubation with only l-arginine (without lipoproteins), platelet nitric oxide (NO) levels and P-selectin receptor numbers significantly increased compared to the controls (P

The aim of the study was to investigate the protective and therapeutic effects of Polygonum cognatum Meissn (PC) in the treatment of colitis. Rats were orogastrically treated with PC (2g/kg) throughout a 10-day interval before and/or after colitis, which was induced by intracolonic administration of acetic acid. Microscopic damage scores and scanning electron microscopy changes of colon segments were analyzed. The levels of interleukin-6 (IL-6) and tumor necrosis factor-alpha (TNF-?) in serum, malonyldialdehyde (MDA), glutathione (GSH), tissue factor (TF) levels, myeloperoxidase (MPO), superoxide dismutase (SOD), catalase (CAT) and gammaglutamyltransferase (GGT) activities in the colon tissues were measured. PC treatment ameliorated the acetic acid-induced disturbances in colonic tissue. Serum IL-6 and TNF-? levels decreased with PC treated colitis group. Colonic tissue GGT, MPO activities and MDA levels were decreased on the other hand SOD, CAT activities and GSH levels were increased in PC treated colitis group. PC was effective in the treatment of acetic acid-induced colitis in rats. This may be due to the supression and down regulation of mediators in intestinal inflammatory response and the expression of antioxidant and anti-inflammatory response. In conclusion, PC can play an protective role by downregulating the colonic tissue damage and oxidative stress which may be related to modulating the activities of antioxidant molecules in rat model of colitis

We consider a scheduling problem in which two classes of independent jobs have to be processed non-preemptively by a single machine. The processing times of the jobs are assumed to be exponentially distributed with parameters depending on the class of each job. The objective is to minimize the sum of expected completion times. We adopt a bayesian framework in which both job class parameters are assumed to be unknown. However, by processing jobs from the corresponding class, the scheduler can gradually learn about the value of these parameters, thereby enhancing the decision making in the future.for the traditional stochastic scheduling variant, in which the parameters are known, the policy that always processes a job with shortest expected processing time (sept) is an optimal policy. In this paper, we show that in the bayesian framework the performance of sept is at most a factor 2 away from the performance of an optimal policy. Furthermore, we introduce a second policy learning-sept (ℓ-sept), which is an adaptive variant of sept. We show that ℓ-sept is no worse than sept and empirically outperforms sept. However, both policies have the same worst-case performance, that is, the bound of 2 is tight for both policies.keywordsschedule problemcompletion timeoptimal policyschedule policyperformance guaranteethese keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

We address the classical uniformly related machine scheduling problem with minsum objective. The problem is solvable in polynomial time by the algorithm of Horowitz and Sahni. In that solution, each machine sequences its jobs shortest first. However when jobs may choose the machine on which they are processed, while keeping the same sequencing rule per machine, the resulting Nash equilibria are in general not optimal. The price of anarchy measures this optimality gap. By means of a new characterization of the optimal solution, we show that the price of anarchy in this setting is bounded from above by 2. We also give a lower bound of e/(e−1)≈1.58. This complements recent results on the price of anarchy for the more general unrelated machine scheduling problem, where the price of anarchy equals 4. Interestingly, as Nash equilibria coincide with shortest processing time first (SPT) schedules, the same bounds hold for SPT schedules. Thereby, our work also fills a gap in the literature.

We consider a scheduling problem in which two classes of independent jobs have to be processed non-preemptively by a single machine. The processing times of the jobs are assumed to be exponentially distributed with parameters depending on the class of each job. The objective is to minimize the sum of expected completion times. We adopt a bayesian framework in which both job class parameters are assumed to be unknown. However, by processing jobs from the corresponding class, the scheduler can gradually learn about the value of these parameters, thereby enhancing the decision making in the future.for the traditional stochastic scheduling variant, in which the parameters are known, the policy that always processes a job with shortest expected processing time (sept) is an optimal policy. In this paper, we show that in the bayesian framework the performance of sept is at most a factor 2 away from the performance of an optimal policy. Furthermore, we introduce a second policy learning-sept (l-sept), which is an adaptive variant of sept. We show that l-sept is no worse than sept and empirically outperforms sept. However, both policies have the same worst-case performance, that is, the bound of 2 is tight for both policies.

We consider the problem to minimize the weighted sum of completion times in nonpreemptive parallel machine scheduling. In a landmark paper from 1986, Kawaguchi and Kyan showed that scheduling the jobs according to the WSPT rule -also known as Smith's rule- has a performance guarantee of 1.207. They also gave an instance to show that this bound is tight. We consider the stochastic variant of this problem in which the processing times are exponentially distributed random variables. We show, somehow counterintuitively, that the performance guarantee of the WSEPT rule, the stochastic analogue of WSPT, is not better than 1.243. This constitutes the first lower bound for WSEPT in this setting, and in particular, it sheds new light on the fundamental differences between deterministic and stochastic scheduling problems.

We consider a Stackelberg pricing problem in directed networks. Tariffs have to be defined by an operator, the leader, for a subset of the arcs, the tariff arcs. Clients, the followers, choose paths to route their demand through the network selfishly and independently of each other, on the basis of minimal cost. Assuming there exist bounds on the costs clients are willing to bear, the problem is to find tariffs such as to maximize the operators revenue. Except for the case of a single client, no approximation algorithm is known to date for that problem. We derive the first approximation algorithms for the case of multiple clients. Our results hold for a restricted version of the problem where each client takes at most one tariff arc to route the demand. We prove that this problem is still strongly NP-hard. Moreover, we show that uniform pricing yields both an $m$–approximation, and a $(1 + ln D)$–approximation. Here, $m$ is the number of tariff arcs, and $D$ is upper bounded by the total demand. We furthermore derive lower and upper bounds for the approximability of the pricing problem where the operator must serve all clients, and we discuss some polynomial special cases. A computational study with instances from France Télécom suggests that uniform pricing performs better than theory would suggest.

We consider a non-preemptive, stochastic parallel machine scheduling model with the goal to minimize the weighted completion times of jobs. In contrast to the classical stochastic model where jobs with their processing time distributions are known beforehand, we assume that jobs appear one by one, and every job must be assigned to a machine online. We propose a simple online scheduling policy for that model, and prove a performance guarantee that matches the currently best known performance guarantee for stochastic parallel machine scheduling. For the more general model with job release dates we derive an analogous result, and for NBUE distributed processing times we even improve upon the previously best known performance guarantee for stochastic parallel machine scheduling. Moreover, we derive some lower bounds on approximation.

The robustness function of an optimization problem measures the maximum change in the value of its optimal solution that can be produced by changes of a given total magnitude on the values of the elements in its input. The problem of computing the robustness function of matroid optimization problems is studied under two cost models: the discrete model, which allows the removal of elements from the input, and the continuous model, which permits finite changes on the values of the elements in the input. For the discrete model, an $O(\log k)$-approximation algorithm is presented for computing the robustness function of minimum spanning trees, where $k$ is the number of edges to be removed. The algorithm uses as key subroutine a 2-approximation algorithm for the problem of dividing a graph into the maximum number of components by removing $k$ edges from it. For the continuous model, a number of results are presented. First, a general algorithm is given for computing the robustness function of any matroid. The algorithm runs in strongly polynomial time on matroids with a strongly polynomial time independence test. Faster algorithms are also presented for some particular classes of matroids: (1) an $O(n^3m^2 \log (n^2/m))$-time algorithm for graphic matroids, where $m$ is the number of elements in the matroid and $n$ is its rank, (2) an $O(mn(m+n^2)|E|\log(m^2/|E|+2))$-time algorithm for transversal matroids, where $|E|$ is a parameter of the matroid, (3) an $O(m^2n^2)$-time algorithm for scheduling matroids, and (4) an $O(m \log m)$-time algorithm for partition matroids. For this last class of matroids an optimal algorithm is also presented for evaluating the robustness function at a single point.

We study the problem of finding a spanning tree with maximum number of leaves. We present a simple 2-approximation algorithm for the problem, improving on the previous best performance ratio of 3 achieved by algorithms of Ravi and Lu. Our algorithm can be implemented to run in linear time using simple data structures. We also study the variant of the problem in which a given subset of vertices are required to be leaves in the tree. We provide a 5/2-approximation algorithm for this version of the problem