Scaling the Indian Buffet Process via Submodular Maximization

Inference for latent feature models is inherently difficult as the inference space grows exponentially with the size of the input data and number of latent features. In this work, we use Kurihara & Welling (2008)'s maximization-expectation framework to perform approximate MAP inference for linear-Gaussian latent feature models with an Indian Buffet Process (IBP) prior. This formulation yields a submodular function of the features that corresponds to a lower bound on the model evidence. By adding a constant to this function, we obtain a nonnegative submodular function that can be maximized via a greedy algorithm that obtains at least a one-third approximation to the optimal solution. Our inference method scales linearly with the size of the input data, and we show the efficacy of our method on the largest datasets currently analyzed using an IBP model.

Packing LUT clusters with network flow programming

This paper describes a two-step packing algorithm for LUT clusters of which the LUT input multipliers are depopulated. In the first step, a greedy algorithm is used to search for BLE locations and cluster inputs. If the greedy algorithm fails, the second step with network flow programming algorithm is employed. Numerical results illustrate that our two-step packing algorithm obtains better packing density than one-step greedy packing algorithm.

Adaptive Routing of QoS-constrained Media Streams over Scalable Overlay Topologies

Current research on Internet-based distributed systems emphasizes the scalability of overlay topologies for efficient search and retrieval of data items, as well as routing amongst peers. However, most existing approaches fail to address the transport of data across these logical networks in accordance with quality of service (QoS) constraints. Consequently, this paper investigates the use of scalable overlay topologies for routing real-time media streams between publishers and potentially many thousands of subscribers. Specifically, we analyze the costs of using k-ary n-cubes for QoS-constrained routing. Given a number of nodes in a distributed system, we calculate the optimal k-ary n-cube structure for minimizing the average distance between any pair of nodes. Using this structure, we describe a greedy algorithm that selects paths between nodes in accordance with the real-time delays along physical links. We show this method improves the routing latencies by as much as 67%, compared to approaches that do not consider physical link costs. We are in the process of developing a method for adaptive node placement in the overlay topology, based upon the locations of publishers, subscribers, physical link costs and per-subscriber QoS constraints. One such method for repositioning nodes in logical space is discussed, to improve the likelihood of meeting service requirements on data routed between publishers and subscribers. Future work will evaluate the benefits of such techniques more thoroughly.

Cache-and-Relay Streaming Media Delivery for Asynchronous Clients

We consider the problem of delivering popular streaming media to a large number of asynchronous clients. We propose and evaluate a cache-and-relay end-system multicast approach, whereby a client joining a multicast session caches the stream, and if needed, relays that stream to neighboring clients which may join the multicast session at some later time. This cache-and-relay approach is fully distributed, scalable, and efficient in terms of network link cost. In this paper we analytically derive bounds on the network link cost of our cache-and-relay approach, and we evaluate its performance under assumptions of limited client bandwidth and limited client cache capacity. When client bandwidth is limited, we show that although finding an optimal solution is NP-hard, a simple greedy algorithm performs surprisingly well in that it incurs network link costs that are very close to a theoretical lower bound. When client cache capacity is limited, we show that our cache-and-relay approach can still significantly reduce network link cost. We have evaluated our cache-and-relay approach using simulations over large, synthetic random networks, power-law degree networks, and small-world networks, as well as over large real router-level Internet maps.

Scheduling for parallel dedicated machines with a single server

This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule is NP-hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst-case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two-machine flow shop and the open shop problems with a single server are also shown to be NP-hard in the strong sense. However, we reduce the two-machine flow shop no-wait problem with a single server to the Gilmore-Gomory traveling salesman problem and solve it in polynomial time. (c) 2000 John Wiley & Sons, Inc.

Enabling Complexity-Performance Trade-Offs for Successive Cancellation Decoding of Polar Codes

Polar codes are one of the most recent advancements in coding theory and they have attracted significant interest. While they are provably capacity achieving over various channels, they have seen limited practical applications. Unfortunately, the successive nature of successive cancellation based decoders hinders fine-grained adaptation of the decoding complexity to design constraints and operating conditions. In this paper, we propose a systematic method for enabling complexity-performance trade-offs by constructing polar codes based on an optimization problem which minimizes the complexity under a suitably defined mutual information based performance constraint. Moreover, a low-complexity greedy algorithm is proposed in order to solve the optimization problem efficiently for very large code lengths.

Retrieving Regions of Interest for User Exploration

We consider an application scenario where points of interest (PoIs) each have a web presence and where a web user wants to iden- tify a region that contains relevant PoIs that are relevant to a set of keywords, e.g., in preparation for deciding where to go to conve- niently explore the PoIs. Motivated by this, we propose the length- constrained maximum-sum region (LCMSR) query that returns a spatial-network region that is located within a general region of in- terest, that does not exceed a given size constraint, and that best matches query keywords. Such a query maximizes the total weight of the PoIs in it w.r.t. the query keywords. We show that it is NP- hard to answer this query. We develop an approximation algorithm with a (5 + ǫ) approximation ratio utilizing a technique that scales node weights into integers. We also propose a more efficient heuris- tic algorithm and a greedy algorithm. Empirical studies on real data offer detailed insight into the accuracy of the proposed algorithms and show that the proposed algorithms are capable of computingresults efficiently and effectively.

Efficient Algorithms for Answering the m-Closest Keywords Query

As an important type of spatial keyword query, the m-closest keywords (mCK) query finds a group of objects such that they cover all query keywords and have the smallest diameter, which is defined as the largest distance between any pair of objects in the group. The query is useful in many applications such as detecting locations of web resources. However, the existing work does not study the intractability of this problem and only provides exact algorithms, which are computationally expensive.

In this paper, we prove that the problem of answering mCK queries is NP-hard. We first devise a greedy algorithm that has an approximation ratio of 2. Then, we observe that an mCK query can be approximately answered by finding the circle with the smallest diameter that encloses a group of objects together covering all query keywords. We prove that the group enclosed in the circle can answer the mCK query with an approximation ratio of 2 over 3. Based on this, we develop an algorithm for finding such a circle exactly, which has a high time complexity. To improve efficiency, we propose another two algorithms that find such a circle approximately, with a ratio of 2 over √3 + ε. Finally, we propose an exact algorithm that utilizes the group found by the 2 over √3 + ε)-approximation algorithm to obtain the optimal group. We conduct extensive experiments using real-life datasets. The experimental results offer insights into both efficiency and accuracy of the proposed approximation algorithms, and the results also demonstrate that our exact algorithm outperforms the best known algorithm by an order of magnitude.

Traduction statistique par recherche locale

La traduction statistique vise l’automatisation de la traduction par le biais de modèles statistiques. Dans ce travail, nous relevons un des grands défis du domaine : la recherche (Brown et al., 1993). Les systèmes de traduction statistique de référence, tel Moses (Koehn et al., 2007), effectuent généralement la recherche en explorant l’espace des préfixes par programmation dynamique, une solution coûteuse sur le plan computationnel pour ce problème potentiellement NP-complet (Knight, 1999). Nous postulons qu’une approche par recherche locale (Langlais et al., 2007) peut mener à des solutions tout aussi intéressantes en un temps et un espace mémoire beaucoup moins importants (Russell et Norvig, 2010). De plus, ce type de recherche facilite l’incorporation de modèles globaux qui nécessitent des traductions complètes et permet d’effectuer des modifications sur ces dernières de manière non-continue, deux tâches ardues lors de l’exploration de l’espace des préfixes. Nos expériences nous révèlent que la recherche locale en traduction statistique est une approche viable, s’inscrivant dans l’état de l’art.

Comparing finite state machine test coverage criteria

To plan testing activities, testers face the challenge of determining a strategy, including a test coverage criterion that offers an acceptable compromise between the available resources and test goals. Known theoretical properties of coverage criteria do not always help and, thus, empirical data are needed. The results of an experimental evaluation of several coverage criteria for finite state machines (FSMs) are presented, namely, state and transition coverage; initialisation fault and transition fault coverage. The first two criteria focus on FSM structure, whereas the other two on potential faults in FSM implementations. The authors elaborate a comparison approach that includes random generation of FSM, construction of an adequate test suite and test minimisation for each criterion to ensure that tests are obtained in a uniform way. The last step uses an improved greedy algorithm.

Optimal Path Searching through Specified Routes using different Algorithms

To connect different electrical, network and data devices with the minimum cost and shortest path, is a complex job. In huge buildings, where the devices are placed at different locations on different floors and only some specific routes are available to pass the cables and buses, the shortest path search becomes more complex. The aim of this thesis project is, to develop an application which indentifies the best path to connect all objects or devices by following the specific routes.To address the above issue we adopted three algorithms Greedy Algorithm, Simulated Annealing and Exhaustive search and analyzed their results. The given problem is similar to Travelling Salesman Problem. Exhaustive search is a best algorithm to solve this problem as it checks each and every possibility and give the accurate result but it is an impractical solution because of huge time consumption. If no. of objects increased from 12 it takes hours to search the shortest path. Simulated annealing is emerged with some promising results with lower time cost. As of probabilistic nature, Simulated annealing could be non optimal but it gives a near optimal solution in a reasonable duration. Greedy algorithm is not a good choice for this problem. So, simulated annealing is proved best algorithm for this problem. The project has been implemented in C-language which takes input and store output in an Excel Workbook

Spanning Tree Approach On The Snow Cleaning Problem

Snow cleaning is one of the important tasks in the winter time in Sweden. Every year government spends huge amount money for snow cleaning purpose. In this thesis we generate a shortest road network of the city and put the depots in different place of the city for snow cleaning. We generate shortest road network using minimum spanning tree algorithm and find the depots position using greedy heuristic. When snow is falling, vehicles start work from the depots and clean the snow all the road network of the city. We generate two types of model. Models are economic model and efficient model. Economic model provide good economical solution of the problem and it use less number of vehicles. Efficient model generate good efficient solution and it take less amount of time to clean the entire road network.

Systèmes de numération et automates

Let beta be an hyperbolic algebraic integer of modulus greater than 1. Lot A be a finite set of Q[beta] and D-beta = {(a(i), b(i))(igreater than or equal to0) is an element of (A x A)(N) \ Sigma(i=0)(infinity) a(i)beta(-i)}. We give a necessary and sufficient condition for D-beta to be sofic. As a consequence, we obtain a result due to Thurston (see Corollary 1). We also treat the case where the set of digits A is given by the greedy algorithm and study the connection with the beta-shift. (C) 2002 Academie des sciences/Editions scientifiques et medicales Elsevier SAS.

Novo algoritimo genético para problemas de cobertura de conjuntos

The Set Covering Problem (SCP) plays an important role in Operational Research since it can be found as part of several real-world problems. In this work we report the use of a genetic algorithm to solve SCP. The algorithm starts with a population chosen by a randomized greedy algorithm. A new crossover operator and a new adaptive mutation operator were incorporated into the algorithm to intensify the search. Our algorithm was tested for a class of non-unicost SCP obtained from OR-Library without applying reduction techniques. The algorithms found good solutions in terms of quality and computational time. The results reveal that the proposed algorithm is able to find a high quality solution and is faster than recently published approaches algorithm is able to find a high quality solution and is faster than recently published approaches using the OR-Library.

Dynamic Traffic Grooming Algorithms for Reconfigurable SONET Over WDM Networks

The emergence of wavelength-division multiplexing (WDM) technology provides the capability for increasing the bandwidth of synchronous optical network (SONET) rings by grooming low-speed traffic streams onto different high-speed wavelength channels. Since the cost of SONET add–drop multiplexers (SADM) at each node dominates the total cost of these networks, how to assign the wavelength, groom the traffic, and bypass the traffic through the intermediate nodes has received a lot of attention from researchers recently. Moreover, the traffic pattern of the optical network changes from time to time. How to develop dynamic reconfiguration algorithms for traffic grooming is an important issue. In this paper, two cases (best fit and full fit) for handling reconfigurable SONET over WDM networks are proposed. For each approach, an integer linear programming model and heuristic algorithms (TS-1 and TS-2, based on the tabu search method) are given. The results demonstrate that the TS-1 algorithm can yield better solutions but has a greater running time than the greedy algorithm for the best fit case. For the full fit case, the tabu search heuristic yields competitive results compared with an earlier simulated annealing based method and it is more stable for the dynamic case.