Search

The Erdős-Gyárfás conjecture states that every graph with minimum degree at least three has a cycle whose length is a power of 2. Since this conjecture has proven to be far from reach, Hobbs asked if the Erdős-Gyárfás conjecture holds in claw-free graphs. In this paper, we obtain some results on this question, in particular for cubic claw-free graphs

Motivated by the exploding growth of web-based services and the importance of efficiently managing the computational resources of such systems, we introduce and study a theoretical model for load balancing of very large databases such as commercial search engines. Our model is a more realistic version of the well-received balls-into-bins model with an additional constraint that limits the number of servers that carry each piece of the data. This additional constraint is necessary when, on one hand, the data is so large that we can not copy the whole data on each server. On the other hand, the query response time is so limited that we can not ignore the fact that the number of queries for each piece of the data changes over time, and hence we can not simply split the data over different machines. In this paper, we develop an almost optimal load balancing algorithm that works given an estimate of the load of each piece of the data. Our algorithm is almost perfectly robust to wrong estimates, to the extent that even when all of the loads are adversarially chosen the performance of our algorithm is 1 - 1/e, which is provably optimal. Along the way, we develop various techniques for analyzing the balls-into-bins process under certain correlations and build a novel connection with the multiplicative weights update scheme. [ABSTRACT FROM AUTHOR]

Background: Treatment of pilonidal sinus involves the use of various surgical procedures, most of which are associated with many complications and problems. Meanwhile, open and closed surgical procedures are two common surgical procedures for the treatment of patients with pilonidal sinus disease. The aim of this study is to compare the outcomes of open and closed surgical procedures in pilonidal cysts excision. Methods: This study was a randomized clinical trial that was performed on patients with pilonidal sinus referred to Shahid Beheshti Hospital of Yasuj University of Medical Sciences, Yasuj, Iran. Patients having inclusion criteria were assigned to 2 groups; first group for open surgical procedure (n:30) and second group for closed surgical procedure (n:30) using a simple randomized method. The data gathering tools were a demographic data form and a visual analog scale (VAS). Two types of open and closed surgery procedures were performed randomly on patients. Data were analyzed by SPSS-16 software using mean, standard deviation, independent t-test, Chi-square or Fisher exact test. Results: The results showed that the outcomes of recurrence of the disease (P = 0.001), wound infection (P = 0.003), and duration of surgery (P = 0.001) in open surgical procedure were significantly lower than the closed surgical procedure. Conclusions: Considering the better outcomes of open surgical procedure in terms of patient satisfaction after surgery and lower additional costs, the open surgical procedure is suggested for the treatment of pilonidal sinus - if one of these two methods should be selected by the surgeon. [ABSTRACT FROM AUTHOR]

We consider the problem of estimating the size of a maximum matching when the edges are revealed in a streaming fashion. When the input graph is planar, we present a simple and elegant streaming algorithm that, with high probability, estimates the size of a maximum matching within a constant factor using O (n2/3) space, where n is the number of vertices. The approach generalizes to the family of graphs that have bounded arboricity, which include graphs with an excluded constant-size minor. To the best of our knowledge, this is the first result for estimating the size of a maximum matching in the adversarial-order streaming model (as opposed to the random-order streaming model) in o(n) space. We circumvent the barriers inherent in the adversarial-order model by exploiting several structural properties of planar graphs, and more generally, graphs with bounded arboricity. We further reduce the required memory size to O(v n) for three restricted settings: (i) when the input graph is a forest; (ii) when we have 2-passes and the input graph has bounded arboricity; and (iii) when the edges arrive in random order and the input graph has bounded arboricity. Finally, we design a reduction from the Boolean Hidden Matching Problem to show that there is no randomized streaming algorithm that estimates the size of the maximum matching to within a factor better than 3/2 and uses only o(n1/2) bits of space. Using the same reduction, we show that there is no deterministic algorithm that computes this kind of estimate in o(n) bits of space. The lower bounds hold even for graphs that are collections of paths of constant length. [ABSTRACT FROM AUTHOR]

Optimal stopping theory is a powerful tool for analyzing scenarios such as online auctions in which we generally require optimizing an objective function over the space of stopping rules for an allocation process under uncertainty. Perhaps the most classic problems of stopping theory are the prophet inequality problem and the secretary problem. The classical prophet inequality states that by choosing the same threshold OPT/2 for every step, one can achieve the tight competitive ratio of 0.5. On the other hand, for the basic secretary problem, the optimal strategy achieves the tight competitive ratio of 1/e ≈ 0.36 In this paper, we introduce prophet secretary, a natural combination of the prophet inequality and the secretary problems. In the prophet secretary problem we are given a set {D1,...,Dn} of (not necessarily identical) distributions. A number Xi is drawn from each distribution Di and then, after applying a random permutation π1,..., πn, the numbers are given to us in an online fashion, i.e., at step k, Xπk is revealed. We are allowed to choose only one number, which can be done only upon receiving that number. The goal is to maximize the expectation of the chosen value, compared to the expectation of the optimum offline solution that knows the drawn values in advance. In particular, we show that by using a single uniform threshold one cannot break the 0.5 barrier of the prophet inequality for the prophet secretary problem. However, we show that • using n distinct nonadaptive thresholds one can obtain a competitive ratio that goes to (1 - 1/e ≈ 0.63) as n grows, and • no online algorithm can achieve a competitive ratio better than 0.75. Our results improve the (asymptotic) approximation guarantee of single-item sequential posted pricing mechanisms from 0.5 to (1-1/e) when the order of agents (customers) is chosen randomly. We also consider the minimization variants of stopping theory problems and, in particular, the prophet secretary problem. Interestingly, we show that, even for the simple case in which the input elements are drawn from identical and independent distributions, there is no constant competitive online algorithm for the minimization variant of the prophet secretary problems. We extend this hardness result to the minimization variants of both the prophet inequality and the secretary problem as well. [ABSTRACT FROM AUTHOR]