This work estimates the complexity of Uruguayan Truco, an imperfect-information two-team card game, by computing a lower bound on the total number of information sets in its extensive-form representation. We adapt the HyperLogLog (HLL) probabilistic counting algorithm to support arbitrarily long hashes, enabling its use in this new domain. This adapted version is combined with Monte Carlo rollouts to handle the intractable size of the game tree. To validate our approach, we introduce mini-Truco, a simplified and tractable variant of the original game. Our experiments show that, in expectation, this approach yields accurate estimates of the underlying set size while providing horizontal scalability across multiple nodes. After running this game-agnostic method for 100 days (totaling 4.8×105core-hours), we establish that a 20-point 2-player game of Uruguayan Truco contains at least 1.49×1012information sets, providing a concrete lower bound on the game’s complexity.

Network reliability computation is an NP-hard problem which has attracted much attention in literature. This problem consists in, given a network where the links may fail or operate with known probabilities, to compute the probability that a given subset of nodes (known as terminals) are connected by the operational links. Given the difficulty to compute the exact value of the network reliability, an alternative which has been much explored in the literature is the use of Monte Carlo estimation methods. In this work, we discuss the Permutation Monte Carlo method, which is an estimation algorithm which has shown much promise but that is prone to numerical problems in the case of networks with a large number of links. We discuss this situation and we present a simple way to rewrite the algorithm's computations which is more numerically stable. We present some computational results showing that the method is more efficient that the standard Monte Carlo method for highly reliable networks, and that it can be applied to topologies with hundreds of links.

Nowadays, the assimilation of workers with disabilities is recognized as both a challenge and an opportunity in terms of staff diversity and of corporate social responsibility of different organizations. In this context, achieving a fair and efficient task distribution is an essential aspect of guaranteeing the effective and full involvement of all the workers, independently from their cognitive and physical capacities. A task distribution model is a method for assigning and managing tasks within a work team, organization or group of persons, usually aiming to optimize productivity and efficiency. The main objective is to ensure that the correct tasks are assigned to the appropriate persons, taking into account their abilities, experience and current work charge. Task distribution models are particularly relevant when including people with disabilities, where they must be flexible and adaptable enough to guarantee the full integration of all the team members. In this work, we present a Mathematical Programming model for task distribution in the context of hiring people with disabilities. We discuss a practical case study at the Intendencia de Montevideo (IdeM - the municipality of the city of Montevideo), as part of a project for improving the integration of people with disabilities in its staff (currently the IdeM staff only includes about 1.5% of employees with disabilities; while applicable laws state that this percentage should raise to at least 4%). We present the results of applying the Mathematical Programming model, comparing the results against manual assignments. Different objective functions are also taken into account, as the various stakeholders also have specific goals that are important to take into account. The results show that mathematical programming models are an effective tool that can be used to support decision making and improve the integration of workers with disabilities in an organization.

Uruguayan Truco is a positive-sum and imperfect information card game with 2, 4 and 6 player variants. Finding the Nash equilibria of such games is very hard, so we approximate them using Computational Game Theory and Deep Reinforcement Learning methods. We implement Counterfactual Regret Minimization (CFR) and some of its variants, and Deep Monte Carlo (DMC). We also propose two levels of manual abstraction to reduce the number of information sets, which are sets of indistinguishable game states. We evaluate our methods on T1K22, a dataset of 79,000 random hands of Uruguayan Truco, against two baseline agents and a human player. We find that CFR-based methods outperform DMC, especially External Sampling Monte Carlo CFR, which converges faster and achieves a higher win rate. It is remarkable that, after 2 weeks of training (totaling 4,032 core hours), starting from scratch and without using any human knowledge, the best agents defeated every baseline, with win rates significantly higher than 50%.

The creation and the destruction processes (CPs and DPs) are the basis of many efficient Monte Carlo methods for estimating the unreliability of highly reliable networks on both, the static and the stochastic flow network models, for the case of independent components. Some of these methods are based on the splitting variance reduction techniques. Due to the splitting basic mechanism, they operate over CP. Here, we propose a splitting-based Monte Carlo method, using the Marshall–Olkin copula for the case of nonindependent components. This proposal operates on the DP, because the Marshall–Olkin copula model over networks is quite related—and somehow similar—to DP, which is unusual but here necessary. Before addressing the proposal, the article presents a review of the methods based on CP and DP. At the end, a comparative experimental analysis shows the efficiency of the proposed approach.

The Creation Process is an algorithm that transforms a static network model into a dynamic one. It is the basis of different variance reduction methods designed to make efficient reliability estimations on highly reliable networks in which links can only assume two possible values, operational or failed. In this paper, the Creation Process is extended to let it operate on network models in which links can assume more than two values. The proposed algorithm, called here as the Multilevel Creation Process, is the basis of a method, also introduced here, to make efficient reliability estimations of highly reliable stochastic flow networks. The method proposed, which consists in an application of Splitting over the Multilevel Creation Process, is empirically shown to be accurate, efficient, and robust.

This state of the art discusses the problem of reliability estimation for highly reliable stochastic flow networks. There are algorithms to compute this reliability exactly, but they have exponential complexity, making the problem intractable for large or even medium sized networks. In this case Monte Carlo simulation is a simple and straightforward alternative tool to provide a reliability estimation. However, standard Monte Carlo is efficient only if the reliability is not extremely high, otherwise variance reduction techniques are required. This work explores different methods designed to reduce the variance of the estimators in this context. These methods are introduced together with a brief review of the algorithms in which they are based. Also, their precision and computational efficiency is discussed, giving some insights on their relative performance and suitability.

This work presents an application of mathematical programming methods and their implementation in free software tools to develop a support tool for the assignment of habitational units in a cooperative. In Uruguay building and housing cooperatives have a history of developing housing solutions, at lower prices and higher quality levels than possible with traditional approaches. In these cooperatives, it is usual that, once the houses are built, the assignment to members is done randomly (ie, holding a lottery). In this work we develop a computational tool that can take into account the stated preferences of the cooperative members and generate assignments that maximize their satisfaction, with results of much higher satisfaction levels than those achieved using the traditional lottery method.

Let be a simple graph with vertices and edges, a subset of terminals, a vector and a positive integer , called the diameter. We assume vertices are perfect but edges fail stochastically and independently, with probabilities . The diameter constrained reliability (DCR) is the probability that the terminals of the resulting subgraph remain connected by paths composed of or fewer edges. This number is denoted by . The general DCR computation problem belongs to the class of ‐hard problems. The contributions of this article are threefold. First, the computational complexity of DCR‐subproblems is discussed in terms of the number of terminal vertices and the diameter . Either when or when and is fixed, the DCR problem belongs to the class of polynomial‐time solvable problems. The DCR problem becomes ‐hard when is a fixed input parameter and . The cases where or is a free input parameter and is fixed have not been studied in the prior literature. Here, the ‐hardness of both cases is established. Second, we categorize certain classes of graphs that allow the DCR computation to be performed in polynomial time. We include graphs with bounded corank, graphs with bounded genus, planar graphs, and in particular, Monma graphs, which are relevant in robust network design. Third, we introduce the problem of analyzing the asymptotic properties of the DCR measure in networks that grow infinitely following given probabilistic rules. We introduce basic results for Gilbert's random graph model. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(4), 296–305 2015

Scheduling is a capital problem when using distributed heterogeneous computing (HC) and grid environments to solve complex problems. The scheduling problem in heterogeneous environments is NP‐hard, so a significant effort has been made to develop efficient methods for solving the problem. However, few works have faced realistic grid‐sized problem instances. This work presents a parallel CHC (pCHC) evolutionary algorithm codified over MALLBA, a general‐purpose library for combinatorial optimization, for solving the scheduling problem in HC and grid environments. Efficient numerical results are reported in the experimental analysis performed on both a standard benchmark and a set of large‐sized problem instances specially designed in this work. The comparative study shows that pCHC is able to achieve high problem solving efficacy, significantly improving over traditional deterministic scheduling methods, while also showing a good scalability behavior when solving large problem instances.

We propose a polynomial-time algorithm for detecting and deleting classes of network edges which are irrelevant in the evaluation of the Source-to-terminal Diameter Constrained Network reliability parameter. As evaluating this parameter is known to be an NP-hard problem, the proposed procedure may lead to important computational gains when combined with an exact method to calculate the reliability. For illustration, we integrate this algorithm within an exact recursive factorization approach based upon Moskowitz's edge decomposition. Experiments conducted on different real-world topologies confirmed a substantial computational gain, except when highly-dense graphs were tested.

In this paper, we present an algorithm based on the GRASP meta-heuristic for solving a dynamic assignment problem in a P2P network designed for sending real-time video over the Internet. In a highly dynamic P2P topology, the frequent connections and disconnections of nodes are the main obstacle we face when trying to offer a high Quality-of-Experience (QoE) to clients. We first introduce the P2P network architecture where this node dynamics occurs. This architecture employs a multi-source streaming approach where the stream is decomposed into several flows sent by different peers to each client, including some level of redundancy, in order to cope with the fluctuations in network connectivity. Then, we present the GRASP-based algorithm developed in order to tackle the problem of maintaining connectivity in presence of node dynamics by periodically reassigning network connections; these assignments are performed so as to maximize the global expected QoE, calculated using the recently proposed PSQA methodology. Additionally, we provide a variation of the GRASP-based algorithm, based on the Random Neural Network model. Finally, we show the results obtained when these algorithms are applied to a case study based on real life data.

This paper explores a key aspect of the problem of sending real-time video over the Internet using a P2P architecture. The main difficulty with such a system is the high dynamics of the P2P topology, because of the frequent moves of the nodes leaving and entering the network. We consider a multi-source approach where the stream is decomposed into several flows sent by different peers to each client. Using the recently proposed PSQA technology for evaluating automatically and accurately the perceived quality at the client side, the paper focuses on the consequences of the way the stream is decomposed on the resulting quality. Our main contribution is to provide a global methodology that can be used to design such a system, illustrated by looking at three extreme cases. Our approach allows to do the design by addressing the ultimate target, the perceived quality (or Quality of Experience), instead of the standard but indirect metrics such as loss rates, delays, reliability, etc. We also propose an improved version of PSQA obtained by considering the video sequences at frame-level, instead of the packet-level approach of previous works.

This paper proposes a new formulation of the recursive variance-reduction Monte Carlo estimator of the /spl kappa/ terminal unreliability parameter of communication systems. This formulation allows significant reduction in the simulation execution time, as demonstrated by experimental results.

The RVR (recursive variance reduction) simulation technique has been used with success for the evaluation of the K-terminal reliability measure of networks where only links can fail. In this paper, we show how this technique can be adapted for computing the K-terminal residual connectedness reliability measure in the case of networks where nodes can fail. We prove that an RVR simulation of the residual connectedness reliability has a lower variance than standard Monte Carlo simulation, leading to better estimates. We study the worst-case computational complexity of the RVR method, and we discuss the influence of the node failure probability on the algorithm performance, which makes it more efficient and especially suited for very reliable networks.