The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Computational advertising is an emerging new scientific sub-discipline, at the intersection of large scale search and text analysis, information retrieval, statistical modeling, machine learning, classification, optimization, and microeconomics. The central challenge of computational advertising is to find the “best match” between a given user in a given context and a suitable advertisement. The context...
Collaborative filtering has been widely used to predict the interests of a user. Given a users past activities, collaborative filtering predicts the users future preferences. This talk presents techniques and discoveries of our recent parallelization effort on collaborative filtering algorithms. In particular, parallel association mining and parallel latent Dirichlet allocation will be presented and...
In this paper, we study several versions of optimization problems related to haplotype reconstruction/identification. The input to the first problem is a set C1 of haplotypes, a set C2 of haplotypes, and a set G of genotypes. The objective is to select the minimum number of haplotypes from C2 so that together with haplotypes in C1 they resolve all (or the...
We study restricted improvement cycles (ri-cycles) in finite positional n-person games with perfect information modeled by directed graphs (digraphs) that may contain cycles. We obtain criteria of restricted improvement acyclicity (ri-acyclicity) in two cases: for n = 2 and for acyclic digraphs. We provide several examples that outline the limits of these criteria and show that, essentially, there...
In this paper we introduce a discrete version of the online traveling salesman problem (DOLTSP). We represent the metric space using a weighted graph, where the server is allowed to modify its route only at the vertices. This limitation directly affects the capacity of the server to react and increases the risk related to each decision. We prove lower bounds on the performance of deterministic online...
In an implicit combinatorial optimization problem, the constraints are not enumerated explicitly but rather stated implicitly through equations, other constraints or auxiliary algorithms. An important subclass of such problems is the implicit set cover (or, equivalently, hitting set) problem in which the sets are not given explicitly but rather defined implicitly. For example, the well-known minimum...
The Banzhaf index, Shapley-Shubik index and other voting power indices measure the importance of a player in a coalitional game. We consider a simple coalitional game called the spanning connectivity game (SCG) based on an undirected, unweighted multigraph, where edges are players. We examine the computational complexity of computing the voting power indices of edges in the SCG. It is shown that computing...
Procurement executives often find it difficult to articulate their preferences and constraints regarding auctions, making it difficult to cast procurement decisions as straightforward optimization problems. This paper presents an efficient algorithm to aid decision support in such situations. Instead of trying to compute a single optimal solution for the auction winner determination problem, we generate...
Polyhedra are widely used in model checking and abstract interpretation. Polyhedral analysis is effective when the relationships between variables are linear, but suffers from imprecision when it is necessary to take into account the integrality of the represented space. Imprecision also arises when non-linear constraints occur. Moreover, in terms of tractability, even a space defined by linear constraints...
In this paper we present approximation algorithms for solving the line segment facility location problem in weighted regions. The weighted region setup is a more realistic model for many facility location problems that arise in practical applications. Our algorithms exploit an interesting property of the problem, that could possibly be used for solving other problems in weighted regions.
In the Flow Edge-Monitor Problem, we are given an undirected graph G = (V,E), an integer k > 0 and some unknown circulation ψ on G. We want to find a set of k edges in G, so that if we place k monitors on those edges to measure the flow along them, the total number of edges for which the flow can be uniquely determined is maximized. In this paper, we first show that the Flow Edge-Monitor Problem...
In the frequency assignment problem we are given a graph representing a wireless network and a sequence of requests, where each request is associated with a vertex. Each request has two more attributes: its arrival and departure times, and it is considered active from the time of arrival to the time of departure. We want to assign frequencies to all requests so that at any time no two active requests...
We develop algorithms to compute Voronoi diagrams, shortest path maps, and the Fréchet distance in the plane with polygonal obstacles. Distances between points are measured either by link distance or by Euclidean shortest path distance.
During the last years, a wide range of huge networks has been made available to researchers. The discovery of natural groups, a task called graph clustering, in such datasets is a challenge arising in many applications such as the analysis of neural, social, and communication networks. We here present Orca, a new graph clustering algorithm, which operates locally and hierarchically contracts...
Wiener index as one of the oldest chemical index has been well studied. It has been extensive used in Computational Biology, Preliminary screening of drugs and Complex Network. Based on variable Wiener index, I.Gutman et al [6] introduced the concept of equiseparable pairs of trees and chemical trees, meanwhile they gave a rule on how to construct such equiseparable pairs. D.Vukic̆ević and I.Gutman...
We introduce a reduction technique for the well-known TSP. The basic idea of the approach consists of transforming a TSP instance to another one with smaller size by contracting pseudo backbone edges computed in a preprocessing step, where pseudo backbone edges are edges which are likely to be in an optimal tour. A tour of the small instance can be re-transformed to a tour of the original instance...
Most sponsored search auctions use the Generalized Second Price (GSP) rule. Given the GSP rule, they try to give an optimal allocation, an easy task when the only need is to allocate ads to slots. However, when other practical conditions must be fulfilled –such as budget constraints, exploration of the performance of new ads, etc.– optimal allocations are hard to obtain. We provide a method to optimally...
We consider the problem of estimating the hybrid frequency moment of matrix data that is updated point-wise in arbitrary order by a data stream. In this model, data is viewed to be organized in the form of a matrix (Ai,j)1 ≤ i,j, ≤ n. The entries Ai,j are updated coordinate-wise (both increments and decrements are allowed),...
We describe a two-level push-relabel algorithm for the maximum flow problem and compare it to the competing codes. The algorithm generalizes a practical algorithm for bipartite flows. Experiments show that the algorithm performs well on several problem families.
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.