Search

The 2-Interval Pattern problem over its various models and restrictions was proposed by Vialette for RNA secondary structure prediction, and has attracted a lot of attention from the theoretical computer science community in recent years. In the framework of 2-intervals, the preceding-and-crossing model is an especially interesting model for RNA secondary structures with pseudoknots. In this paper, we present a polynomial time approximation scheme for the Weighted 2-Interval Pattern problem over the preceding-and-crossing model. Our algorithm improves the previous best 2-approximation algorithm, and closes this problem in terms of the approximation ratio. [ABSTRACT FROM AUTHOR]

We study the complexity of several coloring problems on graphs, parameterized by the treewidth t of the graph: (1) The list chromatic numberχl(G) of a graph G is defined to be the smallest positive integer r, such that for every assignment to the vertices v of G, of a list Lv of colors, where each list has length at least r, there is a choice of one color from each vertex list Lv yielding a proper coloring of G. We show that the problem of determining whether χl(G) ≤ r, the List Chromatic Number problem, is solvable in linear time for every fixed treewidth bound t. The method by which this is shown is new and of general applicability. (2) The List Coloring problem takes as input a graph G, together with an assignment to each vertex v of a set of colors Cv. The problem is to determine whether it is possible to choose a color for vertex v from the set of permitted colors Cv, for each vertex, so that the obtained coloring of G is proper. We show that this problem is W[1]-hard, parameterized by the treewidth of G. The closely related Precoloring Extension problem is also shown to be W[1]-hard, parameterized by treewidth. (3) An equitable coloring of a graph G is a proper coloring of the vertices where the numbers of vertices having any two distinct colors differs by at most one. We show that the problem is hard for W[1], parameterized by (t,r). We also show that a list-based variation, List Equitable Coloring is W[1]-hard for trees, parameterized by the number of colors on the lists. [ABSTRACT FROM AUTHOR]

The arc-searching problem is a natural extension of the edge searching problem, which is to determine the minimum number of searchers (search number) needed to capture an invisible fast intruder in a graph. We examine several models for the internal arc-searching problem, in which the searchers may not "jump" from a vertex to a non-adjacent vertex. We will explore some elementary results and characterize directed graphs with small search number for the various models. [ABSTRACT FROM AUTHOR]

The constrained minimum vertex cover problem on bipartite graphs (the Min-CVCB problem), with important applications in the study of reconfigurable arrays in VLSI design, is an NP-hard problem and has attracted considerable attention in the literature. Based on a deeper and more careful analysis on the structures of bipartite graphs, we develop an exact algorithm of running time $O((k_u+k_l)G+1.1892^{k_u+k_l})$, which improves the best previous algorithm of running time $O((k_u+k_l)G+1.26^{k_u+k_l})$ for the problem. [ABSTRACT FROM AUTHOR]

The minimum all-ones problem is applied in linear cellular automata. It is NP-complete for general graphs. In this paper, we consider the problem for graphs with small treewidth≤4. We give an O(V) algorithm. [ABSTRACT FROM AUTHOR]

The AND-OR tree is an extremely simple model to compute the read-once Boolean functions. For an AND-OR tree, the eigen-distribution is a special distribution on random assignments to the leaves, such that the distributional complexity of the AND-OR tree is achieved. Yao's Principle[8] showed that the randomized complexity of any function is equal to the distributional complexity of the same function. In the present work, we propose an eigen-distribution-based technique to compute the distributional complexity of read-once Boolean functions. Then, combining this technique and Yao's Principle, we provide a unifying proof way for some well-known results of the randomized complexity of Boolean functions. [ABSTRACT FROM AUTHOR]

We study the Connected Facility Location problems. We are given a connected graph G = (V, E) with non-negative edge cost ce for each edge e ∈ E, a set of clients D ⊆ V such that each client j ∈ D has positive demand dj and a set of facilities F ⊆ V each has non-negative opening cost fi and capacity to serve all client demands. The objective is to open a subset of facilities, say $\hat F$, to assign each client j ∈ D to exactly one open facility i(j) and to connect all open facilities by a Steiner tree T such that the cost $\sum_{i \in \hat F} f_i + \sum_{j \in D} d_j c_{i(j)j}+M\sum_{e \in T}c_e$ is minimized. We propose a LP-rounding based 8.29 approximation algorithm which improves the previous bound 8.55. We also consider the problem when opening cost of all facilities are equal. In this case we give a 7.0 approximation algorithm. [ABSTRACT FROM AUTHOR]

The Two-Sided Crossing Minimization (TSCM) problem calls for minimizing the number of edge crossings of a bipartite graph where the two sets of vertices are drawn on two parallel layers and edges are drawn as straight lines. This well-known problem has important applications in VLSI design and automatic graph drawing. In this paper, we present a new branch-and-cut algorithm for the TSCM problem by modeling it directly to a binary quadratic programming problem. We show that a large number of effective cutting planes can be derived based on a reformulation of the TSCM problem. We compare our algorithm with a previous exact algorithm by testing both implementations with the same set of instances. Experimental evaluation demonstrates the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

The Closest Substring problem (CSP), where a short string is sought that minimizes the number of mismatches between it and each of a given set of strings, is a minimization problem with polynomial time approximation schemes. In this paper, a lower bound on approximation algorithms for the CSP problem is developed. We prove that unless the Exponential Time Hypothesis (ETH Hypothesis, i.e., not all search problems in SNP are solvable in subexponential time) fails, the CSP problem has no polynomial time approximation schemes of running time f(1/ε)xO(1/ ∈ ) for any function f, where x is the size of input instance. This essentially excludes the possibility that the CSP problem has a practical polynomial time approximation scheme even for moderate values of the error bound ε . As a consequence, it is unlikely that the study of approximation schemes for the CSP problem in the literature would lead to practical approximation algorithms for the CSP problem for small error bound ε. [ABSTRACT FROM AUTHOR]

In this paper generalizations of Heilbronn's triangle problem are considered. By using results on the independence number of linear hypergraphs, for fixed integers k ≥ 3 and any integers n ≥ k a o(n6k − 4 ) time deterministic algorithm is given, which finds distributions of n points in the unit square [0,1]2 such that, simultaneously for j = 3..., k, the areas of the convex hulls determined by any j of these n points are Ω((logn)1/(j − 2)/n(j − 1)/(j − 2)). [ABSTRACT FROM AUTHOR]

We consider a nonpreemptive single machine common due window scheduling problem where the job processing times are controllable with linear costs and the due window is movable. The objective is to find a job sequence, a processing time for each job, and a position of the common due window to minimize the total cost of weighted earliness/tardiness and processing time compression. We discuss some properties of the optimal solutions and provide a polynomial time algorithm to solve the problem. [ABSTRACT FROM AUTHOR]

We present a branch-and-bound (bb) algorithm for the multiple sequence alignment problem (MSA), one of the most important problems in computational biology. The upper bound at each bb node is based on a Lagrangian relaxation of an integer linear programming formulation for MSA. Dualizing certain inequalities, the Lagrangian subproblem becomes a pairwise alignment problem, which can be solved efficiently by a dynamic programming approach. Due to a reformulation w.r.t. additionally introduced variables prior to relaxation we improve the convergence rate dramatically while at the same time being able to solve the Lagrangian problem efficiently. Our experiments show that our implementation, although preliminary, outperforms all exact algorithms for the multiple sequence alignment problem. [ABSTRACT FROM AUTHOR]

This paper first considers the use of the "15 puzzle," which is one of the most famous sliding-block puzzles, to provide secure multiparty computations. That is, we design a class of 15-puzzle-based protocols for securely computing Boolean functions. Specifically, we show that any function of 4 variables (or less) and any symmetric function of 14 variables (or less) can be securely computed by a 15-puzzle-based protocol; furthermore, we present a 5-variable function and a 15-variable symmetric function, both of which cannot be securely computed by any protocol in the class. [ABSTRACT FROM AUTHOR]

Recent experimental studies on compressed indexes (BWT, CSA, FM-index) have confirmed their practicality for indexing long DNA sequences such as the human genome (about 3 billion characters) in the main memory [5,13,16]. However, these indexes are designed for exact pattern matching, which is too stringent for most biological applications. The demand is often on finding local alignments (pairs of similar substrings with gaps allowed). In this paper, we show how to build a software called BWT-SW that exploits a BWT index of a text T to speed up the dynamic programming for finding all local alignments with any pattern P. Experiments reveal that BWT-SW is very efficient (e.g., aligning a pattern of length 3,000 with the human genome takes less than a minute). We have also analyzed BWT-SW mathematically, using a simpler model (with gaps disallowed) and random strings. We find that the expected running time is O(T0.628P). As far as we know, BWT-SW is the first practical tool that can find all local alignments. [ABSTRACT FROM AUTHOR]

A double-loop network(DLN) G(N; r, s ) is a digraph with the vertex set V = {0, 1,..., N − 1} and the edge set E = {v →v+ r (modN) andv →v + s(modN)v ∈ V}. Let D(N; r, s) be the diameter of G, D(N) = min {D(N; r, s)1 ≤ r < s < N and $\gcd(N; r, s ) = 1 \}$ and D1(N) = min {D(N; 1, s)1 < s < N }. Xu and Aguil$\acute{o}$ et al. gave some infinite families of 0-tight non-unit step(nus) integers with D1(N) − D(N) ≥ 1. In this paper, an approach is proposed for finding infinite families of k-tight(k ≥ 0) optimal double-loop networks G(N; r, s ), and two infinite families of k-tight optimal double-loop networks G(N; r, s ) are presented. We also derive one infinite family of 1-tight nus integers with D1(N) − D(N) ≥ 1 and one infinite family of 1-tight nus integers with D1(N) − D(N) ≥ 2. As a consequence of these works, some results by Xu are improved. [ABSTRACT FROM AUTHOR]

Combinatorial games pose an extreme challenge to combinatorial optimization. Several combinatorial games have been shown to be PSPACE-hard and many more are believed to be so. In this paper, we present a new approach to analyzing combinatorial games, which differs dramatically from current approaches. Using the combinatorial game Chomp as a model system, we employ ideas from physics and dynamical systems theory to unveil deep connections between such games and nonlinear phenomena commonly seen in nature. [ABSTRACT FROM AUTHOR]

This paper attends to the problem of a mechanism designer seeking to influence the outcome of a strategic game based on her creditability. The mechanism designer offers additional payments to the players depending on their mutual choice of strategies in order to steer them to certain decisions. Of course, the mechanism designer aims at spending as little as possible and yet implementing her desired outcome. We present several algorithms for this optimization problem both for singleton target strategy profiles and target strategy profile regions. Furthermore, the paper shows how a bankrupt mechanism designer can decide efficiently whether strategy profiles can be implemented at no cost at all. Finally, risk-averse players and dynamic games are examined. [ABSTRACT FROM AUTHOR]

For the m-machine Flow Shop Weighted Completion Time problem, a New Lower Bound (NLB) is derived to improve the original lower bound which was given by Kaminsky and Simchi-Levi. 1) For the case of arbitrary weight, the NLB is asymptotically equivalent to the optimality solution, as the total number of jobs goes to infinity. Specially, when the processing times of jobs are all equal, the NLB is just the optimal solution. 2) For the case of equal-weight, a tight worst case performance ratio of the optimal solution to the NLB is obtained. At the end of the paper, computational results show the effectiveness of NLB on a set of random test problems. [ABSTRACT FROM AUTHOR]

In wireless sensor networks, virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem and perform some other tasks such as area monitoring. Previous work in this area has mainly focused on how to set up a small virtual backbone for high efficiency, which is modelled as the minimum Connected Dominating Set (CDS) problem. In this paper we consider how to establish a small virtual backbone to balance efficiency and fault tolerance. This problem can be formalized as the minimum m-connected k-dominating set problem, which is a general version of minimum CDS problem with m = 1 and k = 1. In this paper we will propose some approximation algorithms for this problem that beat the current best performance ratios. [ABSTRACT FROM AUTHOR]

We discuss fast exponential time exact algorithms for generalized combinatorial optimization problems. The list of discussed NP-complete generalized combinatorial optimization problems includes the generalized minimum spanning tree problem, the generalized subset assignment problem and the generalized travelling salesman problem. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of maximizing welfare in combinatorial auctions with k duplicates of each item, where bidders are subadditive. We present two approximation algorithms for k-duplicates combinatorial auctions with subadditive bidders. First, we give a factor-$O(\sqrt{m})$ approximation algorithm for k-duplicates combinatorial auctions with subadditive valuations using value queries. This algorithm is also incentive compatible. Secondly, we give a factor-O(logm) approximation algorithm for k-duplicates combinatorial auctions with subadditive valuations using demand queries. [ABSTRACT FROM AUTHOR]

Several features of today's grid are based on centralized or hierarchical services. However, as the grid size increasing, some of their functions especially resource discovery should be decentralized to avoid performance bottlenecks and guarantee scalability. A novel grid resource discovery method based on adaptive k-Nearest Neighbors clustering is presented in this paper. A class is formed by a collection of nodes with some similarities in their characteristics, each class is managed by a leader and consists of members that serve as workers. Resource requests are ideally forwarded to an appropriate class leader that would then direct it to one of its workers. This method can handle resource requests by searching a small subset out of a large number of nodes by resource clustering which can improve the resource query efficiency; on the other hand, it also achieves well scalability by managing grid resources with adaptive mechanism. It is shown from a series of experiments that the method presented in this paper achieves more scalability and efficient lookup performance than other existing methods. [ABSTRACT FROM AUTHOR]

We define a fundamental domain of a linear programming relaxation of a combinatorial integer program which is symmetric under a group action. We then provide a construction for the polytope of a fundamental domain defined by the maximization of a linear function. The computation of this fundamental domain is at worst polynomial in the size of the group. However, for the special case of the symmetric group, whose size is exponential in the size of the integer program, we show how to compute a separating hyperplane in polynomial time in the size of the integer program. Fundamental domains may provide a straightforward way to reduce the computation difficulties that often arise in integer programs with symmetries. Our construction is closely related to the constructions of orbitopes by Kaibel and Pfetch, but are simpler and more general, at a cost of creating new non-integral extreme points. [ABSTRACT FROM AUTHOR]

A communication process in the S5-knowledge model is presented which leads to a Nash equilibrium of a strategic form game through robust messages. In the communication process each player predicts the other players' actions under his/her private information. The players communicate privately their conjectures through message according to the communication graph, where each recipient of the message learns and revises his/her conjecture. The emphasis is on that each player sends not exact information about his/her individual conjecture but robust information about the conjectures to an accuracy ε. AMS 2000 Mathematics Subject Classification: Primary 91A35, Secondary 03B45. Journal of Economic Literature Classification: C62, C78. [ABSTRACT FROM AUTHOR]

It seems reasonable that for a connected representing graph of a spy network, the more edges it has, the more jeopardy the spy network is in. So, a spy network which has the minimum number of edges is the comparatively reliable network we want. As a special kind of graph, a critically m-neighbor-scattered graph is important and interesting in applications in communication networks. In this paper, we obtain some upper bounds and a lower bound for the size of a minimum critically m-neighbor-scattered graph with given order p and 4 − p ≤ m ≤ − 1. Moreover, we construct a (1 + ∈ )-approximate graph for the minimum critically m-neighbor-scattered graph of order p for sufficiently small m and sufficiently large p. [ABSTRACT FROM AUTHOR]

We consider the problem of connecting given vertex pairs over a stochastic metric graph, each vertex of which has a probability of presence independently of all other vertices. Vertex pairs requiring connection are always present with probability 1. Our objective is to satisfy the connectivity requirements for every possibly materializable subgraph of the given metric graph, so as to optimize the expected total cost of edges used. This is a natural problem model for cost-efficient Steiner Forests on stochastic metric graphs, where uncertain availability of intermediate nodes requires fast adjustments of traffic forwarding. For this problem we allow a priori design decisions to be taken, that can be modified efficiently when an actual subgraph of the input graph materializes. We design a fast (almost linear time in the number of vertices) modification algorithm whose outcome we analyze probabilistically, and show that depending on the a priori decisions this algorithm yields 2 or 4 approximation factors of the optimum expected cost. We also show that our analysis of the algorithm is tight. [ABSTRACT FROM AUTHOR]

Based on some new results concerning k-taxi problem, a new variant of the problem, namely the on-line k-taxi problem with limited look ahead (OTLLA) is proposed by our team. Compared with the traditional k-taxi problem, in which only the start and end points of the current service request are known at each step, the OTLLA has a basic realistic consideration: the start point of the first service request is given before the whole service sequence plays, and at each step the end of the current service request and the start point of the next service request are known. In this paper, after the formulation of the model of the OTLLA, some results concerning the competitive analysis for some special cases of OTLLA are given: the competitive algorithm so called Partial Greedy Algorithm (PGA) is designed and the competitive ratios are obtained. Furthermore, some comparisons between some on-line algorithms are developed. Finally, some conclusions are given and some future research directions are discussed. [ABSTRACT FROM AUTHOR]

Many combinatorial optimization problems can be formulated as 0/1 integer programs (0/1 IPs). The investigation of the structure of these problems raises the following tasks: count or enumerate the feasible solutions and find an optimal solution according to a given linear objective function. All these tasks can be accomplished using binary decision diagrams (BDDs), a very popular and effective datastructure in computational logics and hardware verification. We present a novel approach for these tasks which consists of an output-sensitive algorithm for building a BDD for a linear constraint (a so-called threshold BDD) and a parallel AND operation on threshold BDDs. In particular our algorithm is capable of solving knapsack problems, subset sum problems and multidimensional knapsack problems. BDDs are represented as a directed acyclic graph. The size of a BDD is the number of nodes of its graph. It heavily depends on the chosen variable ordering. Finding the optimal variable ordering is an NP-hard problem. We derive a 0/1 IP for finding an optimal variable ordering of a threshold BDD. This 0/1 IP formulation provides the basis for the computation of the variable ordering spectrum of a threshold function. We introduce our new tool azove 2.0 as an enhancement to azove 1.1 which is a tool for counting and enumerating 0/1 points. Computational results on benchmarks from the literature show the strength of our new method. [ABSTRACT FROM AUTHOR]

This paper proposes a new cost function based on distance and load of the vehicle for the Capacitated Vehicle Routing Problem. The vehicle-routing problem with this new load-based cost objective is called the Energy Minimizing Vehicle Routing Problem (EMVRP). Integer linear programming formulations with O(n2) binary variables and O(n2) constraints are developed for the collection and delivery cases, separately. The proposed models are tested and illustrated by classical Capacitated Vehicle Routing Problem (CVRP) instances from the literature using CPLEX 8.0. [ABSTRACT FROM AUTHOR]

This paper proposes a novel hybrid algorithm for feature selection. This algorithm combines a global optimization algorithm called the simulated annealing algorithm based nested partitions (NP/SA). The resulting hybrid algorithm NP/SA retains the global perspective of the nested partitions algorithm and the local search capabilities of the simulated annealing method. We also present a detailed application of the new algorithm to a customer feature selection problem in customer recognition of a life insurance company and it is found to have great computation efficiency and convergence speed. [ABSTRACT FROM AUTHOR]

Multiple sequence alignment (MSA) is one of the most basic and central tasks for many studies in modern biology. In this paper, we present a new progressive alignment algorithm for this very difficult problem. Given two groups A and B of aligned sequences, this algorithm uses Dynamic Programming and the sum-of-pairs objective function to determine an optimal alignment C of A and B. The proposed algorithm has a much lower time complexity compared with a previously published algorithm for the same task [11]. Its performance is extensively assessed on the well-known BAliBase benchmarks and compared with several state-of-the-art MSA tools. [ABSTRACT FROM AUTHOR]

This paper studies a spanning tree problem with interval data that finds diverse applications in network design. Given an underlying network G = (V,E), each link e ∈ E can be established by paying a cost $c_e\in[\underline{c}_e,\overline{c}_e]$, and accordingly takes a risk $\frac{\overline{c}_e-c_e}{\overline{c}_e-\underline{c}_e}$ of link failure. The minimum risk spanning tree (MRST) problem is to establish a spanning tree in G of total cost no more than a given constant so that the risk sum over the links on the spanning tree is minimized. In this paper, we propose an exact algorithm for the MRST problem that has time-complexity of O(m2logm logn(m + n logn)), where m = E and n = V. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of computing the minimum number of searchers who can capture an intruder hiding in a graph. We propose a linear time algorithm for computing the vertex separation and the optimal layout for a unicyclic graph. The best algorithm known so far is given by Ellis et al. (2004) and needs O(n logn) time, where n is the number of vertices in the graph. By a linear-time transformation, we can compute the search number and the optimal search strategy for a unicyclic graph in linear time. We show how to compute the search number for a k-ary cycle-disjoint graph. We also present some results on approximation algorithms. [ABSTRACT FROM AUTHOR]

Motivated by the existence of an APTAS(Asymptotic PTAS) for bin packing problem, we consider the batch scheduling problem with nonidentical job sizes to minimize makespan. For the proportional special version, i.e., there exists a fixed number α such that pj = αsj for every 1 ≤ j ≤ n, we first present a lower bound of 3/2 for the approximation ratio and then design an APTAS for it. Our basic idea is quite simple: we first enumerate all the partial schedules of relatively large jobs; Then for every partial schedule we insert the small jobs, split them if necessary; Further then, we choose the best of all the obtained schedules; Finally, we collect the split small jobs and put them into new batches. As we can round the large jobs into only a constant number of different kinds at a reasonable expense of accuracy, the running time can be bounded. When the optimal objective value of instances in our consideration can not be arbitrarily small, $\inf \limits_{I}\{P_{\rm max}: P_{\rm max}$ is the largest processing time in I } ≠ 0 for instance, our result is perfect in the sense of worst-case performance. [ABSTRACT FROM AUTHOR]

Let PG(s,t) denote a shortest path between two nodes s and t in an undirected graph G with nonnegative edge weights. A replacement path at a node u ∈ PG(s,t) = (s, ⋯ ,u,v, ⋯ ,t) is defined as a shortest path PG − e(u,t) from u to t which does not make use of (u,v). In this paper, we focus on the problem of finding an edge e = (u,v) ∈ PG(s,t) whose removal produces a replacement path at node u such that the ratio of the length of PG − e(u,t) to the length of PG(u,t) is maximum. We define such an edge as an anti-block vital edge (AVE for short), and show that this problem can be solved in O(mn) time, where n and m denote the number of nodes and edges in the graph, respectively. Some applications of the AVE for two special traffic networks are shown. [ABSTRACT FROM AUTHOR]

An important issue in deploying a WSN is to provide target coverage with high energy efficiency and fault-tolerance. Sensor nodes in a wireless sensor network are resource-constrained, especially in energy supply, and prone to failure. In this paper, we study the problem of constructing energy efficient and fault-tolerant target coverage. More specifically, we propose solutions to forming k-connected coverage of targets with the minimal number of active nodes. We first address the k-connected augmentation problem, and then show that the k-connected target coverage problem is NP-hard. We propose two heuristic algorithms to solve the problem. We have carried out extensive simulations to study the performance of the proposed algorithms. The evaluation results have demonstrated their desirable efficiency. [ABSTRACT FROM AUTHOR]

In this note, we consider algorithms for computing virtual cut points in finite metric spaces and explain how these points can be used to study compatible decompositions of metrics generalizing the well-known decomposition of a tree metric into a sum of pairwise compatible split metrics. [ABSTRACT FROM AUTHOR]

For a given convex polygon with inner angle no less than $\frac{2}{3}\pi$ and boundary edge bounded by [l, αl] for 1≤ α ≤ 1.4, where l is a given standard bar's length, we investigate the problem of triangulating the polygon using some Steiner points such that (i) the length of each edge in triangulation is bounded by [βl,2l], where β is a given constant and meets $0 < \beta <\frac{1}{2}$, and (ii) the number of non-standard bars in the triangulation is minimum. This problem is motivated by practical applications and has not been studied previously. In this paper, we present a heuristic to solve the above problem, which is based on the heuristic to generate a triangular mesh with more number of standard bars and shorter maximal edge length, and a process to make the length of each edge lower bounded. Our procedure is simple and easily implemented for this problem, and we prove that it has good performance guaranteed. [ABSTRACT FROM AUTHOR]

Level of Repair Analysis (LORA) is a prescribed procedure for defence logistics support planning. For a complex engineering system containing perhaps thousands of assemblies, sub-assemblies, components, etc. organized into several levels of indenture and with a number of possible repair decisions, LORA seeks to determine an optimal provision of repair and maintenance facilities to minimize overall life-cycle costs. For a LORA problem with two levels of indenture with three possible repair decisions, which is of interest in UK and US military and which we call LORA-BR, Barros (1998) and Barros and Riley (2001) developed certain branch-and-bound heuristics. The surprising result of this paper is that LORA-BR is, in fact, polynomial-time solvable. To obtain this result, we formulate the general LORA problem as an optimization homomorphism problem on bipartite graphs, and reduce a generalization of LORA-BR, LORA-M, to the maximum weight independent set problem on a bipartite graph. We prove that the general LORA problem is NP-hard by using an important result on list homomorphisms of graphs. We introduce the minimum cost graph homomorphism problem and provide partial results. Finally, we show that our result for LORA-BR can be applied to prove that an extension of the maximum weight independent set problem on bipartite graphs is polynomial time solvable. [ABSTRACT FROM AUTHOR]

The Knapsack problem and integer programming are NP-complete problems. In this paper we show that the inverse problem of Knapsack problem can be solved with a pseudo-polynomial algorithm. We also show that the inverse problem of integer programming with fixed number of constraints is pseudo-polynomial. Keywords: Inverse problem, Knapsack problem, integer programming, pseudo-polynomial algorithm. [ABSTRACT FROM AUTHOR]

In this paper we study the Minimum Range Assignment problem in static ad-hoc networks with arbitrary structure, where the transmission distances can violate triangle inequality. We consider two versions of the Minimum Range Assignment problem, where the communication graph has to fulfill either the h-strong connectivity condition (Min-Range(h-SC)) or the h-broadcast condition (Min-Range(h-B)). Both homogeneous and non-homogeneous cases are studied. By approximating arbitrary edge-weighted graphs by paths, we present probabilistic O(log n)-approximation algorithms for Min-Range(h-SC) and Min-Range(h-B), which improves the previous best ratios O(log n loglog n) and O(n2log n loglog n), respectively [21]. The result for Min-Range(h-B) matches the lower bound [20] for the case that triangle inequality for transmission distance holds (which is a special case of our model). Furthermore, we show that if the network fulfils certain property and the distance power gradient α is sufficiently small, the approximation ratio is improved to O((loglog n)α). [ABSTRACT FROM AUTHOR]

The field of supply chain management has been growing at a rapid pace in recent years, both as a research area and as a practical discipline. In this paper, we study the computational complexity of product covering problems in 3-tier supply chain models, and present natural complete problems for the classes W[3] and W[4] in parameterized complexity theory. This seems the first group of natural complete problems for higher levels in the parameterized intractability hierarchy (i.e., the W-hierarchy), and the first precise complexity characterizations of certain optimization problems in the research of supply chain management. Our results also derive strong computational lower bounds and inapproximability for these optimization problems. [ABSTRACT FROM AUTHOR]

We study the problem of embedding a directed hypergraph on a ring that has applications in optical network communications. The undirected version (MCHEC) has been extensively studied. It was shown that the undirected version was NP-complete. A polynomial time approximation scheme (PTAS) for the undirected version has been developed. In this paper, we design a polynomial time approximation scheme for the directed version. [ABSTRACT FROM AUTHOR]

The idea of active networks has been emerged in recent years to increase the processing power inside the network. The intermediate nodes such as routers will be able to host mobile agents and many management tasks can be handled using autonomous mobile agents inside the network. One of the important limitations, which should be considered in active networks, is the restricted processing power of active nodes. In this paper, we define an optimal location problem for monitoring mobile agents in a scalable active network as a p-median problem, which is indeed a kind of facility location problem. The agents are responsible to monitor and manage the performance of all of the network nodes such that the total monitoring traffic overhead is minimized. Then we proposed two methods of finding an appropriate sub set of intermediate nodes for hosting mobile agents. In our first method, we have not considered the limited processing power of active nodes, which host mobile agents. In our second method, we have solved the problem so that the processing loads of host nodes do not exceed a predefined threshold. Since p-median problems are NP-complete and the search space of these problems is very large, our methods are based on genetic algorithms. We have tested our two methods for finding mobile agents optimal locations on four network topologies with different number of nodes and compared the obtained location. By this comparison, we have shown the importance of considering processing load limitation for active nodes as a parameter in choosing them as hosts of mobile agents in a scalable active network. The proposed locations in our second method eliminates the probability of CPU overload in the active nodes hosting the mobile agents and reduces the processing time required for finding the optimal locations of mobile agents. Keywords: Active Networks, mobile agents, Performance Monitoring, P-Median Problem, Genetic Algorithm. [ABSTRACT FROM AUTHOR]

This work extends the existing parallel- and serial-episode data mining algorithms to that for parallel connection of serial (PoS) episodes. The PoS-episodes can model more general situations and preserve the sequence information as well. The PoS-episode mining algorithm can provide episode-mining users a powerful mining tool and make the episode mining more flexible. To use the PoS-episode mining algorithm, users need to decide reasonable parameters like window width and minimum frequency ratio. Concepts and methods are provided by using Web log mining as example to illustrate the applicability of the PoS-episode mining and show how to decide reasonable parameters as well as evaluate the mining process. [ABSTRACT FROM AUTHOR]

Consider a finite point set in m-dimensional space and the polyhedral hulls it generates from constrained linear combinations of its elements. There are several interesting management problems that are modelled using these point sets and the resulting polyhedral objects. Examples include efficiency/performance evaluation, ranking and ordering schemes, stochastic scenario generation, mining for the detection of fraud, etc. These applications require the identification of frames; that is, the extreme elements of the polyhedral sets, a computationally intensive task. Traditional approaches require the solution of an LP for each point in the point set. We discuss this approach as well as a new generation of faster, output-sensitive, algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we develop a new and effective schedule algebra based algorithm to determine the K-best solutions of a knapsack problem with a single constraint. Computational experience with this algorithm is also reported and it is shown to dominate both the dynamic programming and branch and bound based procedures when applied to this problem. [ABSTRACT FROM AUTHOR]

In this paper, we propose principle factor analysis method to reduce the dimensions of a high dimensional random vector in calculating portfolio's Value at Risk. The theoretical foundation, algorithm and numerical example of the method are given. This method outperforms the principle component analysis method. Especially, the advantages of the method are marked, while the factors F's multicollinearity is serious. Keywords: principal factor analysis, value at risk, principal component analysis, multicollinearity. [ABSTRACT FROM AUTHOR]

Graph bandwidth minimization (GBM) is a classical and challenging problem in graph algorithms and combinatorial optimization. Most of existing researches on this problem have focused on unweighted graphs. In this paper, we study the bandwidth minimization problem of weighted caterpillars, and propose several algorithms for solving various types of caterpillars. More specifically, we show that the GBM problem of caterpillars with hair-length at most 2 and the GBM problem of star-shape caterpillars are NP-complete, and give a lower bound of the graph bandwidth for general weighted graphs. For caterpillars with hair-length at most 1, we present an O(n log n log (nwmax))-time algorithm to compute an optimal bandwidth layout, where n is the total number of vertices in the graph and wmax is the maximum edge weight. For caterpillars with hair-length at most k, we give a k-approximation algorithm. For arbitrary caterpillars and general graphs, we give a heuristic algorithm. Experiments show that the solutions obtained by our heuristic algorithm are roughly within a factor of log (2n) of the lower bound. [ABSTRACT FROM AUTHOR]

In this paper we study the set cover games when the elements are selfish agents. In this case, each element has a privately known valuation of receiving the service from the sets, i.e., being covered by some set. Each set is assumed to have a fixed cost. We develop several approximately efficient truthful mechanisms, each of which decides, after soliciting the declared bids by all elements, which elements will be covered, which sets will provide the coverage to these selected elements, and how much each element will be charged. For set cover games when both sets and elements are selfish agents, we show that a cross-monotonic payment-sharing scheme does not necessarily induce a truthful mechanism. [ABSTRACT FROM AUTHOR]