Catálogo de publicaciones - libros

Recent legislation in the US regarding gambling over the web has led to renewed interest in the question of which games are games of skill. We take a statistical approach to the problem, defining the skill index of a game to be the average amount of playing time after which variance due to chance and variance due to skill differences are equal.

We then look at tournament results for championship-level duplicate bridge, PGA golf, and duplicate poker, as well as some simulated toy games, to see how their skill indices compare.

At any given time, the traffic on the network can be described using a traffic matrix. Entry in the matrix denotes the traffic originating in with destination currently in the network. As traffic demands are dynamic, the matrix itself is ever changing. Traditionally network capacity has been deployed so that it can support any traffic matrix with high probability, given the known traffic distribution patterns. Recently the need for resilience and reliabilibility of the network for mission critical data has brought the need for backbone capacity that can support all traffic matrices. In this talk we give an overview of the state of the art on networks and routing schemes with this property.

The two main alternatives for achieving high QoS on the public internet are (i) admission control and (ii) capacity overprovisioning. In the study of these alternatives the implicit (and sometimes explicit) message is that ideally, QoS issues should be dealt with by means of sophisticated admission control (AC) algorithms, and only because of their complexity providers fall on the simpler, perhaps more cost-effective, yet “wasteful” solution of capacity overprovisioning (CO) (see e.g. Olifer and Olifer [Wiley&Sons, 2005], Parekh [IWQoS’2003], Milbrandt et al. [J.Comm. 2007]). In the present survey we observe that these two alternatives are far from being mutually exclusive. Rather, for data critical applications, a substantial amount of “overprovisioning” is in fact a fundamental step of any safe and acceptable solution to QoS and resiliency requirements. We observe from examples in real life that in many cases large amounts of overprovisioning are already silently deployed within the internet domain and that in some restricted network settings they have become accepted practice even in the academic literature. Then we survey the main techniques currently in use to compute the provisioning capacities required in a resilient high QoS network.

In the recently introduced model for a graph with brushes, we use a degree-greedy algorithm to clean a random -regular graph on vertices (with even). We then use a differential equations method to find the (asymptotic) number of brushes needed to clean a random -regular graph using this algorithm. As well as the case for general , interesting results for specific values of are examined. We also state various open problems.

We study the efficiency of selfish routing problems in which traffic demands are revealed . We go beyond the common Nash equilibrium concept in which possibly all players reroute their flow and form a new equilibrium upon arrival of a new demand.

In our model, demands arrive in sequential games. In each game, the new demands form a Nash equilibrium and their routings remain unchanged afterwards. We study the problem both with nonatomic and atomic player types and with continuous and nondecreasing latency functions on the edges. For polynomial latency functions, we give constant upper and lower bounds on the competitive ratio of the resulting online routing in terms of the maximum degree, the number of games and in the atomic setting the number of players. In particular, for nonatomic players and affine latency functions we show that the competitive ratio is at most . Finally, we present improved upper bounds for the special case of two nodes connected by parallel arcs.

Random graphs with given expected degrees () were introduced by Chung and Lu so as to extend the theory of classical (,) random graphs to include random power law graphs. We investigate asymptotic results for the game of Cops and Robber played on () and (,). Under mild conditions on the degree sequence , an asymptotic lower bound for the cop number of () is given. We prove that the cop number of random power law graphs with vertices is asymptotically almost surely (). We derive concentration results for the cop number of (,) for as a function of .

We consider the problem of scheduling on parallel uniformly related machines, where preemptions are allowed and the machines are controlled by selfish agents. Our goal is to minimize the makespan, whereas the goal of the agents is to maximize their profit. We show that a known algorithm is monotone and can therefore be used to create a truthful mechanism for this problem which achieves the optimal makespan. We extend this result for additional common goal functions.

We study routing and path coloring problems in all-optical networks as non-cooperative games. We especially focus on oblivious payment functions, that is, functions that charge a player according to her own strategy only.

We first strengthen a known relation between such games and online routing and path coloring. In particular, we show that the price of anarchy of such games is lower-bounded by, and in several cases precisely equal to, the competitive ratio of appropriate modifications of the First Fit algorithm.

Based on this framework we provide results for two classes of games in ring networks: in Selfish Routing and Path Coloring a player must determine both a routing and a coloring for her request, while in Selfish Path Coloring the routing is predetermined and only a coloring of requests needs to be specified. We prove specific upper and lower bounds on the price of anarchy of these games under various payment functions.

The problem of counting the number of independent sets of a graph (denoted as ()) is a classic #P-complete problem for graphs of degree 3 or higher. Exploiting the strong relation between () and Fibonacci numbers, we show that if the depth-first graph of does not contain a pair of basic cycles with common edges, then () can be computed in linear time (in the size of the graph). This determines new classes of instances of graphs without restrictions on their degrees and where the number of independent sets is computed in polynomial time.

We design an exact deterministic algorithm for computing () based on the topological structure of the graph , applying the well-known splitting rule from Davis and Putnam (D&P) procedure. D&P is a familiar method for solving the Satisfiability Boolean Problem. Our algorithm for computing () establishes a leading Worst-Case Upper Bound of ( (,)* 1.220744), and being the number of nodes and edges of the graph , respectively. The exact technique reported here can be used to compute the redundancy of a line in a communication network.

Helsgaun has introduced and implemented the lower tolerances (-values) for an approximation of Held-Karp’s 1-tree with the purpose to improve the Lin-Kernighan Heuristic (LKH) for the Symmetric TSP (STSP). The LKH appears to exceed the performance of all STSP heuristic algorithms proposed to date.

In this paper we improve Helsgaun’s LKH based on an approximation of Zhang and Looks’ backbones and an extension of double bridges further combined with implementation details by all of which we guide the search process instead of Helsgaun’s -values. Our computational results are competitive and lead to improved solutions for some of the VLSI instances announced at the TSP homepage.