Atomic Congestion Games: Fast, Myopic and Concurrent

We study here the effect of concurrent greedy moves of players in atomic congestion games where n selfish agents (players) wish to select a resource each (out of m resources) so that her selfish delay there is not much. The problem of “maintaining” global progress while allowing concurrent play is exactly what is examined and answered here. We examine two orthogonal settings: (i) A game where the players decide their moves without global information, each acting “freely” by sampling resources randomly and locally deciding to migrate (if the new resource is better) via a random experiment. Here, the resources can have quite arbitrary latency that is load dependent. (ii) An “organised” setting where the players are pre-partitioned into selfish groups (coalitions) and where each coalition does an improving coalitional move. Our work considers concurrent selfish play for arbitrary latencies for the first time. Also, this is the first time where fast coalitional convergence to an approximate equilibrium is shown.     

Perfect load balancing on the star interconnection network

In this paper, we use the regular distribution method to design a perfect load balancing algorithm for an n-star with a maximum error of 1 and a time complexity of 3n(n+1). This algorithm is based on the novel notion of leader trees. A second algorithm proposed in this paper as an enhancement to our first algorithm and uses an arbitrary spanning tree as the leader tree and has a worst time complexity of 2.25n ²−3n+0.75. We also discuss the issue of dynamically selecting the leader tree and hybrid load balancing algorithms in general. Furthermore, we present a hybrid algorithm for load balancing on the star interconnection network which benefits from a diffusion load balancing preprocessing phase and shows a smaller mean time complexity than our two first algorithms.     

Connecting Polygonizations via Stretches and Twangs

We show that the space of polygonizations of a fixed planar point set S of n points is connected by O(n ²) “moves” between simple polygons. Each move is composed of a sequence of atomic moves called “stretches” and “twangs,” which walk between weakly simple “polygonal wraps” of S. These moves show promise to serve as a basis for generating random polygons.     

The memory behavior of cache oblivious stencil computations

We present and evaluate a cache oblivious algorithm for stencil computations, which arise for example in finite-difference methods. Our algorithm applies to arbitrary stencils in n-dimensional spaces. On an “ideal cache” of size Z, our algorithm saves a factor of Θ(Z ^1/n ) cache misses compared to a naive algorithm, and it exploits temporal locality optimally throughout the entire memory hierarchy. We evaluate our algorithm in terms of the number of cache misses, and demonstrate that the memory behavior agrees with our theoretical predictions. Our experimental evaluation is based on a finite-difference solution of a heat diffusion problem, as well as a Gauss-Seidel iteration and a 2-dimensional LBMHD program, both reformulated as cache oblivious stencil computations. This work was supported in part by the Defense Advanced Research Projects Agency (DARPA) under contract No. NBCH30390004.     

On the validity of using small positive lower bounds on design variables in discrete topology optimization

It is proved that an optimal {ε, 1} ⁿ solution to a “ε-perturbed” discrete minimum weight problem with constraints on compliance, von Mises stresses and strain energy densities, is optimal, after rounding to {0, 1} ⁿ , to the corresponding “unperturbed” discrete problem, provided that the constraints in the perturbed problem are carefully defined and ε > 0 is sufficiently small.     

Polynomial expansion of symmetric boolean functions by the table method

Conclusion The proposed method for polynomial expansion of SBF based on construction of the triangular tableT _n(π(F)) of local codes of its derivatives has the lowest computational complexity among known methods. Constructing the table only once, the method easily determines all the “residual” functions ϑ _rl ^km for various expansion parametersk andm. Another advantage of the method is its applicability for polynomial expansion of arbitrary BF and partially symmetric BF. In this case, the base of the “triangle” is the truth table of the arbitrary BF or the local code (including convolved local code) of the partially symmetric BF. The method can be successfully used for the synthesis of a wide class of digital networks. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 59–71, November–December, 1996.     

Quantifiable data mining using ratio rules

Association Rule Mining algorithms operate on a data matrix (e.g., customers products) to derive association rules [AIS93b, SA96]. We propose a new paradigm, namely, Ratio Rules, which are quantifiable in that we can measure the “goodness” of a set of discovered rules. We also propose the “guessing error” as a measure of the “goodness”, that is, the root-mean-square error of the reconstructed values of the cells of the given matrix, when we pretend that they are unknown. Another contribution is a novel method to guess missing/hidden values from the Ratio Rules that our method derives. For example, if somebody bought $10 of milk and $3 of bread, our rules can “guess” the amount spent on butter. Thus, unlike association rules, Ratio Rules can perform a variety of important tasks such as forecasting, answering “what-if” scenarios, detecting outliers, and visualizing the data. Moreover, we show that we can compute Ratio Rules in a single pass over the data set with small memory requirements (a few small matrices), in contrast to association rule mining methods which require multiple passes and/or large memory. Experiments on several real data sets (e.g., basketball and baseball statistics, biological data) demonstrate that the proposed method: (a) leads to rules that make sense; (b) can find large itemsets in binary matrices, even in the presence of noise; and (c) consistently achieves a “guessing error” of up to 5 times less than using straightforward column averages. Received: March 15, 1999 / Accepted: November 1, 1999     

Model-based approach to study of mechanisms of complex image viewing

A model-based approach to study complex image viewing mechanisms and the first results of its implementation are presented. The choice of the most informative regions (MIRs) is performed according to results of psychophysical tests with high-accuracy tracking of eye movements. For three test images, the MIRs were determined as image regions with maximal density of gaze fixations for the all subjects (n = 9). Individual image viewing scanpaths (n= 49) were classified into three basic types (i.e. “viewing”, “object-consequent”, and “object-returned” scanpaths). Task-related and temporal dynamics of eye movement parameters for the same subjects have been found. Artificial image scanpaths similar to experimental have been obtained by means of gaze attraction function. The article is published in the original.     

Effective spacetime from multidimensional gravity

We study the effective spacetimes in lower dimensions that can be extracted from a multidimensional generalization of the Schwarzschild-Tangherlini spacetimes derived by Fadeev, Ivashchuk, and Melnikov (Phys. Lett. A 161, 98 (1991)). The higher-dimensional spacetime has D = (4 + n + m) dimensions, where n and m are the number of “internal” and “external” extra dimensions, respectively. We analyze the effective (4 + n) spacetime obtained after dimensional reduction of the m external dimensions. We find that when the m extra dimensions are compact (i) the physics in lower dimensions is independent of m and the character of singularities in higher dimensions, and (ii) the total gravitational mass M of the effective matter distribution is less than the Schwarzschild mass. In contrast, when the m extra dimensions are large, this is not so; the physics in (4 + n) does explicitly depend on m as well as on the nature of singularities in high dimensions, and the mass of the effective matter distribution (with the exception of wormhole-like distributions) is larger than the Schwarzschild mass. These results may be relevant to observations for an experimental/observational test of the theory.     

A notion of task relatedness yielding provable multiple-task learning guarantees

The approach of learning multiple “related” tasks simultaneously has proven quite successful in practice; however, theoretical justification for this success has remained elusive. The starting point for previous work on multiple task learning has been that the tasks to be learned jointly are somehow “algorithmically related”, in the sense that the results of applying a specific learning algorithm to these tasks are assumed to be similar. We offer an alternative approach, defining relatedness of tasks on the basis of similarity between the example generating distributions that underlie these tasks. We provide a formal framework for this notion of task relatedness, which captures a sub-domain of the wide scope of issues in which one may apply a multiple task learning approach. Our notion of task similarity is relevant to a variety of real life multitask learning scenarios and allows the formal derivation of generalization bounds that are strictly stronger than the previously known bounds for both the learning-to-learn and the multitask learning scenarios. We give precise conditions under which our bounds guarantee generalization on the basis of smaller sample sizes than the standard single-task approach. Editors: Daniel Silver, Kristin Bennett, Richard Caruana. A preliminary version of this paper appears in the proceedings of COLT’03, (Ben-David and Schuller 2003).     

The complexity of agent design problems: Determinism and history dependence

The agent design problem is as follows: given a specification of an environment, together with a specification of a task, is it possible to construct an agent that can be guaranteed to successfully accomplish the task in the environment? In this article, we study the computational complexity of the agent design problem for tasks that are of the form “achieve this state of affairs” or “maintain this state of affairs.” We consider three general formulations of these problems (in both non-deterministic and deterministic environments) that differ in the nature of what is viewed as an “acceptable” solution: in the least restrictive formulation, no limit is placed on the number of actions an agent is allowed to perform in attempting to meet the requirements of its specified task. We show that the resulting decision problems are intractable, in the sense that these are non-recursive (but recursively enumerable) for achievement tasks, and non-recursively enumerable for maintenance tasks. In the second formulation, the decision problem addresses the existence of agents that have satisfied their specified task within some given number of actions. Even in this more restrictive setting the resulting decision problems are either pspace-complete or np-complete. Our final formulation requires the environment to be history independent and bounded. In these cases polynomial time algorithms exist: for deterministic environments the decision problems are nl-complete; in non-deterministic environments, p-complete.     

Allocating Weighted Jobs in Parallel

The classic balls-into-bins game considers the experiment of placing m balls independently and uniformly at random (i.u.r.) in n bins. For m=n , it is well known that the maximum load, i.e., the number of balls in the fullest bin is Θ(log n/log log n) , with high probability. It is also known (see [S2]) that a maximum load of O( m / n ) can be obtained for all m≥ n if each ball is allocated in one (suitably chosen) of two (i.u.r.) bins. Stemann presents a distributed algorithm to find the ``suitable' bin for each ball. The algorithm uses r communication rounds to achieve a maximum load of , with high probability. Adler et al. [ACMR] show that Stemann's protocol is optimal up to a constant factor for constant r . In this paper we extend the above results in two directions: we generalize the lower bound to arbitrary r≤log log n . This implies that Stemann's protocol is optimal for all r . Our key result is a generalization of Stemann's upper bound to weighted balls: Let W ^A (resp. W ^M ) denote the average (resp. maximum) weight of the balls. Furthermore, let Δ=W ^A /W ^M . Then the optimal maximum load is Ω(m/n⋅ W ^A +W ^M ) . We present a protocol that achieves a maximum load of γ⋅( m / n ⋅ W ^A +W ^M ) using O( log log n / log (γ⋅(m/n⋅Δ+1)) ) communication rounds. For uniform weights this matches the results of Stemann. In particular, we achieve a load of O( m / n ⋅ W ^A +W ^M ) using log log n communication rounds, which is optimal up to a constant factor. An extension of our lower bound shows that our algorithm also reaches a load which is within a constant factor of the optimal load in the case of weighted balls. All the balls-into-bins games model load balancing problems: the balls are jobs, the bins are resources, the task is to allocate the jobs to the resources in such a way that the maximum load is minimized. Our extension to weighted balls allows us to extend previous bounds to models where resource requirements may vary. For example, if the jobs are computing tasks, their running times may vary. Applications of such load balancing problems occur, e.g., for client-server networks and for multimedia-servers using disk arrays. Received December 23, 1997, and in final form September 9, 1998.     

On the Analysis of Randomized Load Balancing Schemes

It is well known that simple randomized load balancing schemes can balance load effectively while incurring only a small overhead, making such schemes appealing for practical systems. In this paper we provide new analyses for several such dynamic randomized load balancing schemes. Our work extends a previous analysis of the supermarket model, a model that abstracts a simple, efficient load balancing scheme in the setting where jobs arrive at a large system of parallel processors. In this model, customers arrive at a system of n servers as a Poisson stream of rate λ n , λ < 1 , with service requirements exponentially distributed with mean 1. Each customer chooses d servers independently and uniformly at random from the n servers, and is served according to the First In First Out (FIFO) protocol at the choice with the fewest customers. For the supermarket model, it has been shown that using d=2 choices yields an exponential improvement in the expected time a customer spends in the system over d=1 choice (simple random selection) in equilibrium. Here we examine several variations, including constant service times and threshold models, where a customer makes up to d successive choices until finding one below a set threshold. Our approach involves studying limiting, deterministic models representing the behavior of these systems as the number of servers n goes to infinity. Results of our work include useful general theorems for showing that these deterministic systems are stable or converge exponentially to fixed points. We also demonstrate that allowing customers two choices instead of just one leads to exponential improvements in the expected time a customer spends in the system in several of the related models we study, reinforcing the concept that just two choices yields significant power in load balancing. Received November 18, 1997, and in final form September 9, 1998.     

Fault-Tolerant Sequential Scan

We consider the fault-tolerant version of the sequential scan problem. A line of identical cells has to be visited by a scanning head. The head can only distinguish an end of the line from an internal cell but can distinguish neither one end from the other, nor one internal cell from another. When the head starts at an internal cell, its first move is in a direction chosen by the adversary. When the head comes to an internal cell from a neighbor, it has two possible moves: forward, which means “go to the other neighbor”, and back which means “return to the previous neighbor”. At this point the adversary can place a fault whose effect is the change of the motion direction (going forward instead of back and vice-versa). The head is not aware of the occurrence of a fault. The execution cost of a sequential scan algorithm for a line of length n in the presence of at most k faults is the worst-case number of steps that the head must perform in order to scan the entire line. The worst case is taken over all adversary’s decisions. We consider two scenarios: when the length of the line is known to the algorithm and when it is unknown. Our goal is to construct sequential scan algorithms with minimum execution cost. We completely solve this problem for known line size. For any parameters k and n we construct a sequential scan algorithm, analyze its complexity and prove a matching lower bound, thus showing that our algorithm is optimal. The problem of fault-tolerant sequential scan for unknown line size is solved partially. For any parameter k we construct a sequential scan algorithm which explores a line of length n with cost 2kn+o(kn), for arbitrary n. For k=1 our algorithm is shown to be optimal. However, we also show an alternative algorithm that has cost at most O(kn) (with a constant larger than 2) for any n and cost kn+o(kn) (which is asymptotically optimal) for infinitely many n. Hence the asymptotic performances of the two algorithms, for unbounded k and n, are incomparable. This work is partially supported by NSERC Discovery grants. A. Pelc is partially supported by the Research Chair in Distributed Computing at the Université du Québec en Outaouais. P. Flocchini is partially supported by the University Research Chair in Distributed Computing at the University of Ottawa.     

Sorting and Searching in Faulty Memories

In this paper we investigate the design and analysis of algorithms resilient to memory faults. We focus on algorithms that, despite the corruption of some memory values during their execution, are nevertheless able to produce a correct output at least on the set of uncorrupted values. In this framework, we consider two fundamental problems: sorting and searching. In particular, we prove that any O(nlog n) comparison-based sorting algorithm can tolerate the corruption of at most O((nlog n)^1/2) keys. Furthermore, we present one comparison-based sorting algorithm with optimal space and running time that is resilient to O((nlog n)^1/3) memory faults. We also prove polylogarithmic lower and upper bounds on resilient searching. This work has been partially supported by the Sixth Framework Programme of the EU under Contract Number 507613 (Network of Excellence “EuroNGI: Designing and Engineering of the Next Generation Internet”) and by MIUR, the Italian Ministry of Education, University and Research, under Project ALGO-NEXT (“Algorithms for the Next Generation Internet and Web: Methodologies, Design and Experiments”). A preliminary version of this work was presented at the 36th ACM Symposium on Theory of Computing (STOC’04) .     

Incremental learning of gestures for human–robot interaction

For a robot to cohabit with people, it should be able to learn people’s nonverbal social behavior from experience. In this paper, we propose a novel machine learning method for recognizing gestures used in interaction and communication. Our method enables robots to learn gestures incrementally during human–robot interaction in an unsupervised manner. It allows the user to leave the number and types of gestures undefined prior to the learning. The proposed method (HB-SOINN) is based on a self-organizing incremental neural network and the hidden Markov model. We have added an interactive learning mechanism to HB-SOINN to prevent a single cluster from running into a failure as a result of polysemy of being assigned more than one meaning. For example, a sentence: “Keep on going left slowly” has three meanings such as, “Keep on (1)”, “going left (2)”, “slowly (3)”. We experimentally tested the clustering performance of the proposed method against data obtained from measuring gestures using a motion capture device. The results show that the classification performance of HB-SOINN exceeds that of conventional clustering approaches. In addition, we have found that the interactive learning function improves the learning performance of HB-SOINN.     

ℓ 2 2 Spreading Metrics for Vertex Ordering Problems

We design approximation algorithms for the vertex ordering problems Minimum Linear Arrangement, Minimum Containing Interval Graph, and Minimum Storage-Time Product, achieving approximation factors of $O(\sqrt{\log n}\log\log n)We design approximation algorithms for the vertex ordering problems Minimum Linear Arrangement, Minimum Containing Interval Graph, and Minimum Storage-Time Product, achieving approximation factors of O(?{logn}loglogn)O(\sqrt{\log n}\log\log n) , O(?{logn}loglogn)O(\sqrt{\log n}\log\log n) , and O(?{logT}loglogT)O(\sqrt{\log T}\log\log T) , respectively, the last running in time polynomial in T (T being the sum of execution times). The technical contribution of our paper is to introduce “ℓ ₂² spreading metrics” (that can be computed by semidefinite programming) as relaxations for both undirected and directed “permutation metrics,” which are induced by permutations of {1,2,…,n}. The techniques introduced in the recent work of Arora, Rao and Vazirani (Proc. of 36th STOC, pp. 222–231, 2004) can be adapted to exploit the geometry of such ℓ ₂² spreading metrics, giving a powerful tool for the design of divide-and-conquer algorithms. In addition to their applications to approximation algorithms, the study of such ℓ ₂² spreading metrics as relaxations of permutation metrics is interesting in its own right. We show how our results imply that, in a certain sense we make precise, ℓ ₂² spreading metrics approximate permutation metrics on n points to a factor of O(?{logn}loglogn)O(\sqrt{\log n}\log\log n) .