Search

The Majority game is a two player game with a questioner Q and an answerer A. The answerer holds n elements, each of which can be labeled as 0 or 1. The questioner can ask questions comparing whether two elements have the same or different label. The goal for the questioner is to ask as few questions as possible to be able to identify a single element which has a majority label, or in the case of a tie claim there is none. We denote the minimum number of questions Q needs to make, regardless of A's answers, as q*. In this paper we consider a variation of the Majority game where A is allowed to lie up to t times, i.e., Q needs to find an error-tolerant strategy. In this paper we will give upper and lower bounds for q* for an adaptive game (where questions are processed one at a time), and will find q* for an oblivious game (where questions are asked in one batch). [ABSTRACT FROM AUTHOR]

In this paper, we consider the evacuation problem for a network which consists of a directed graph with capacities and transit times on its arcs. This problem can be solved by the algorithm of Hoppe and Tardos [1] in polynomial time. However their running time is high-order polynomial, and hence is not practical in general. Thus it is necessary to devise a faster algorithm for a tractable and practically useful subclass of this problem. In this paper, we consider a dynamic network with a single sink s such that () for each vertex v the sum of transit times of arcs on any path from v to s takes the same value, and () for each vertex v the minimum v-s cut is determined by the arcs incident to s whose tails are reachable from v. We propose an efficient algorithm for this network problem. This class of networks is a generalization of the grid network studied in the paper [2]. [ABSTRACT FROM AUTHOR]

Given a digraph, suppose that some intruders hide on vertices or along edges of the digraph. We want to find the minimum number of searchers required to capture all the intruders hiding in the digraph. In this paper, we propose and study two digraph searching models: strong searching and mixed strong searching. In these two search models, searchers can move either from tail to head or from head to tail when they slide along edges, but intruders must follow the edge directions when they move along edges. We prove the monotonicity of each model respectively, and show that both searching problems are NP-complete. [ABSTRACT FROM AUTHOR]

Pricing arithmetic average options continues to intrigue researchers in the field of financial engineering. Since there is no analytical solution for this problem until present, developing an efficient numerical algorithm becomes a promising alternative. One of the most famous numerical algorithms for pricing arithmetic average options is introduced by Hull and White [10]. In this paper, motivated by the common idea of reducing the nonlinearity error in the adaptive mesh model [7] and the adaptive quadrature numerical integration method [6], the logarithmically equally-spaced placement rule in the Hull and White's model is replaced by an adaptive placement method, in which the number of representative average prices is proportional to the degree of curvature of the option value as a function of the arithmetic average price. Numerical experiments verify the superior performance of our method in terms of reducing the interpolation error. In fact, it is straightforward to apply this method to any pricing algorithm with the techniques of augmented state variables and the piece-wise linear interpolation approximation. [ABSTRACT FROM AUTHOR]

For feature selection in machine learning, set covering (SC) is most suited, for it selects support features for data under analysis based on the individual and the collective roles of the candidate features. However, the SC-based feature selection requires the complete pair-wise comparisons of the members of the different classes in a dataset, and this renders the meritorious SC principle impracticable for selecting support features from a large number of data. Introducing the notion of implicit SC-based feature selection, this paper presents a feature selection procedure that is equivalent to the standard SC-based feature selection procedure in supervised learning but with the memory requirement that is multiple orders of magnitude less than the counterpart. With experiments on six large machine learning datasets, we demonstrate the usefulness of the proposed implicit SC-based feature selection scheme in large-scale supervised data analysis. [ABSTRACT FROM AUTHOR]

Proportional Integral (PI) controller has attracted researchers in industrial control processes because of its simplicity and robust performance in a wide range of operating conditions. It has been used to provide proportional delay differentiation on web servers in previous work. However, PI controller cannot achieve satisfactory results due to (1) the web server's non-linearity properties, and (2) the difficulty of building an accurate model for the web server. To address these issues, a nonlinear fuzzy PI controller is proposed in this paper, which has the advantage of fuzzy controller while maintaining the simplicity and robustness of PI controller. The proposed controller are self-tuned according to the periodical online performance measurement. The experimental results demonstrate that our fuzzy PI controller outperforms the PI controller in several aspects. [ABSTRACT FROM AUTHOR]

BitTorrent (BT) in practice is a very efficient method to share data over a network of clients. In this paper we extend the recent work of Arthur and Panigrahy [1] on modelling the distribution of individual data blocks in BT systems, aiming at a better understanding of why BT can achieve a high degree of parallelism. In particular, we include in our study several new network features that BT systems are using, as well as different local heuristics for routing data blocks in each client. We conduct simulations to figure out to what extent the new network features and routing heuristics would affect the distribution efficiency. Our findings confirm that for the primitive network setting studied in [1], it does require Ω(b logn) phases for n clients to download b data blocks. More interestingly, our work suggests that for the more realistic network setting, the heuristics Random and Rarest Block First both allow n clients to download b blocks in b + O(logn) phases. We believe that the latter bound better reflects the high degree of parallelism of BT observed in reality. It is also worth-mentioning that b + logn is the smallest possible number of phases needed; it is interesting to see that some simple local routing heuristics have a performance so close to the optimal. [ABSTRACT FROM AUTHOR]

In this paper we establish a general algorithmic framework between bin packing and strip packing, with which we achieve the same asymptotic bounds by applying bin packing algorithms to strip packing. More precisely we obtain the following results: (1) Any offline bin packing algorithm can be applied to strip packing maintaining the same asymptotic worst-case ratio. Thus using FFD (First Fit Decreasing Height) as a subroutine, we get a practical (simple and fast) algorithm for strip packing with an upper bound 11/9. (2) A class of Harmonic-based algorithms for bin packing can be applied to online strip packing maintaining the same asymptotic competitive ratio. It implies online strip packing admits an upper bound of 1.58889 on the asymptotic competitive ratio. This significantly improves the previously best bound of 1.6910 and affirmatively answers an open question posed in [5] . [ABSTRACT FROM AUTHOR]

The best known algorithm for the one-to-all shortest path problem is Dijkstra's algorithm, which can achieve time complexity O(E + Vlog(V)) by the implementation of data structures like buckets. While for one-to-some shortest path problem, no matter how small the "some" is, the time complexity of Dijkstra's algorithm remains O(E + Vlog(V)) and it often still needs to explore a large part of the graph and thus is not efficient. This paper proposes a novel algorithm which computes the shortest paths bidirectionally with A* algorithm multiple times to solve the one-to-some shortest path problem on road maps efficiently, where the size of the destination set is much smaller than the total number of vertices in the graph. The experiments on both randomly generated graphs and real road maps show that our algorithm is more space and time efficient than Dijkstra's algorithm with buckets, one of the most efficient algorithm for one-to-some shortest path problem. [ABSTRACT FROM AUTHOR]

In this paper, we study an interesting geometric partition problem, called optimal field splitting with feathering (OFSF), which arises in Intensity-Modulated Radiation Therapy (IMRT). In current clinical practice, a multi-leaf collimator (MLC) with a maximum field size is used to deliver the prescribed intensity maps (IMs). However, the maximum field size of an MLC may require to split a large intensity map into several overlapping sub-IMs each being delivered separately, which may result in sacrificed treatment quality. Few IM splitting techniques reported in the literature have addressed the issue of treatment delivery accuracy for large IMs. We develop a new algorithm for solving the OFSF problem while minimizing the total delivery error. Our basic idea is to formulate the OFSF problem as computing a d-link shortest path in a directed acyclic graph, which expresses a special "layered" structure. The edge weights of the graph satisfy the Monge property, which enables us to solve this d-link shortest path problem by examining only a small portion of the graph, yielding an optimal linear time algorithm for the OFSF problem. [ABSTRACT FROM AUTHOR]

For a plane triangulation G with n vertices, it has been proved that there exists a plane triangulation G with n vertices such that for any st-orientation of G, the length of the longest directed paths of G from s to t is $\geq \lfloor \frac{2n}{3}\rfloor$ [18] . In this paper, we prove the bound $\frac{2n}{3}$ is optimal by showing that every plane triangulation G with n-vertices admits an st-orientation with the length of its longest directed paths bounded by $\frac {2n}{3}+O(1)$. In addition, this st-orientation is constructible in linear time. A by-product of this result is that every plane graph G with n vertices admits a visibility representation with height $\le \frac{2n}{3}+O(1)$, constructible in linear time, which is also optimal. [ABSTRACT FROM AUTHOR]

A barrier option is an option whose payoff depends on whether the price path of the underlying asset ever reaches certain predetermined price levels called the barriers. A single- (double-) barrier option is a barrier option with one (two, respectively) barrier(s). No simple and exact closed-form pricing formula for double-barrier options has been reported in the literature. This paper proposes a novel tree model that can price both single- and double-barrier options efficiently and accurately. This tree model achieves the high efficiency by combinatorial techniques and numerical accuracy by hitting the barriers exactly. Numerical experiments are given to verify the superiority of our method. [ABSTRACT FROM AUTHOR]

The complexity of algorithms for computing game trees on random assignments has been given substantial attention in the literature. In this line, we investigate the complexity of algorithms that compute a special class of game trees $T_{2}^{k}$ from a new perspective — eigen-distribution. This particular distribution is defined as the worst distribution on assignments to variables of $T_{2}^{k}$ regarding a best algorithm. In this paper, we show the eigen-distribution on assignments for $T_{2}^{k}$ in two separate cases, where the assignments to leaves are independently distributed (ID) and correlated distributed(CD). Then we use eigen-distribution to derive the tight bound of the complexity of algorithms for $T_{2}^{k}$. [ABSTRACT FROM AUTHOR]

We introduce and study satisfiability games, a new class of games that can be seen as the non-cooperative version of classical maximum satisfiability problems. We give several results involving these games and mainly focus on their expressiveness. In particular, we show that there exists a strong correspondence between satisfiability games and congestion games. As one of the consequences of our results, we show that each game is isomorphic to a congestion game with player specific payoffs. Thus, each other game can be defined as a particular specialization of congestion games with player specific payoffs and this paper can be considered as a first effort in outlining a classification of non-cooperative games. [ABSTRACT FROM AUTHOR]

In this paper we propose a polynomial time algorithm for the optimal rate and power allocation problem in a two cell CDMA network. We assume continuous rates and limited powers for the base stations. [ABSTRACT FROM AUTHOR]

Orthogonal Variable Spreading Factor (OVSF) code assignment is a fundamental problem in Wideband Code-Division Multiple-Access (W-CDMA) systems, which play an important role in third generation mobile communications. In the OVSF problem, codes must be assigned to incoming code requests, with different data rate requirements, in such a way that they are mutually orthogonal with respect to an OVSF code tree. An OVSF code tree is a complete binary tree in which each node represents a code associated with the combined bandwidths of its two children. To be mutually orthogonal, each leaf-to-root path must contain at most one assigned code. In this paper, we focus on the online version of the OVSF code assignment problem, in the often-studied context of the single cell as well as in the more general context of the whole multi-cell cellular network (for which there are no known results). With the help of 1/8 and 11/8 extra bandwidth resources, we are able to give a 5-competitive algorithm in the single cell and the multi-cell context respectively, which means that the competitive ratio is a constant and not a function of the height of the OVSF tree and thereby improving upon past results. [ABSTRACT FROM AUTHOR]

Given an undirected graph G = (V,E) and a weight function w : E →ℤ + , we consider the problem of orienting all edges in E so that the maximum weighted outdegree among all vertices is minimized. In this paper (1) we prove that the problem is strongly NP-hard if all edge weights belong to the set {1,k}, where k is any integer greater than or equal to 2, and that there exists no pseudo-polynomial time approximation algorithm for this problem whose approximation ratio is smaller than (1 + 1/k) unless P=NP; (2) we present a polynomial time algorithm that approximates the general version of the problem within a factor of (2 − 1/k), where k is the maximum weight of an edge in G; (3) we show how to approximate the special case in which all edge weights belong to {1,k} within a factor of 3/2 for k = 2 (note that this matches the inapproximability bound above), and (2 − 2/(k + 1)) for any k ≥ 3, respectively, in polynomial time. [ABSTRACT FROM AUTHOR]

This paper addresses two augmentation problems related to bipartite graphs. The first, a fundamental graph-theoretical problem, is how to add a set of edges with the smallest possible cardinality so that the resulting graph is 2-edge-connected, i.e., bridge-connected, and still bipartite. The second problem, which arises naturally from research on the security of statistical data, is how to add edges so that the resulting graph is simple and dose not contain any bridges. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of both releasing and scheduling of lots in a wafer fab. In the lot release problem, we determine the number of lots of different products to be released in each period of a planning horizon in order to minimize total tardiness. The problem of the scheduling of lots at various workstations is modeled as a mathematical program for the objective of minimizing the cycle times of the lots and is solved by the Lagrangian relaxation method. Computational results are presented that exhibit that our methodology constantly generates better solutions compared to those obtained by commonly-used dispatching rules. [ABSTRACT FROM AUTHOR]

This paper presents a guided multi-restart search (GMRS) algorithm for scheduling parallel machines in terms of global optimum. GMRS consists of a strategic guided local search phase and a phase that generates a beneficial restart point using the information acquired during the local search. The experimental results show that the proposed algorithm considerably improves the solution within a reasonable time. [ABSTRACT FROM AUTHOR]

Minimizing total completion time ∑ Cj on normal batching machine is solvable in polynomial time for fixed B(B > 1), while Minimizing total completion time ∑ Cj for arbitrary B and minimizing total weighted completion time ∑ WjCj are open problems. In this paper, we consider the problem of scheduling jobs on a flexible batching machine in order to minimizing the total completion time. We prove that the problem is strongly NP-hard. Then the problem with agreeable is NP-hard even if there have three fixed capacities all the time. [ABSTRACT FROM AUTHOR]

In this paper, we present a new and efficient algorithm for solving the LCS problem for two strings. Our algorithm runs in $O(\mathcal R\log\log n + n)$ time, where $\mathcal R$ is the total number of ordered pairs of positions at which the two strings match. [ABSTRACT FROM AUTHOR]

A rectangular drawing is a plane drawing in which every face is a rectangle. In this paper we give a simple encoding scheme for rectangular drawings. Given a rectangular drawing R with maximum degree 3, our scheme encodes R with $\frac{5}{3}m + o(n)$ bits for each n-vertex rectangular drawing R, where m is the number of edges of R, and supports a rich set of queries, including adjacency and degree queries on the faces, in constant time. [ABSTRACT FROM AUTHOR]

Sourcing professionals buy several trillion dollars worth of goods and services yearly. We introduced a new paradigm called expressive commerce and applied it to sourcing. It combines the advantages of highly expressive human negotiation with the advantages of electronic reverse auctions. The idea is that supply and demand are expressed in drastically greater detail than in traditional electronic auctions, and are algorithmically cleared. This creates a Pareto efficiency improvement in the allocation (a win-win between the buyer and the sellers) but the market clearing problem is a highly complex combinatorial optimization problem. We developed the world's fastest tree search algorithms for solving it. We have hosted $25 billion of sourcing using the technology, and created $3.2 billion of hard-dollar savings plus numerous harder-to-quantify benefits. The suppliers also benefited by being able to express production efficiencies and creativity, and through exposure problem removal. Supply networks were redesigned, with quantitative understanding of the tradeoffs, and implemented in weeks instead of months. URL for the paper: http://www.cs.cmu.edu/~sandholm/Expressive%20commerce.aimag.pdf [ABSTRACT FROM AUTHOR]