Home About us Contact
|
Home About us Contact | ||
|
|
||
Polynomial Time (polynomial + time)
Terms modified by Polynomial Time Selected AbstractsCOALITIONS AMONG INTELLIGENT AGENTS: A TRACTABLE CASECOMPUTATIONAL INTELLIGENCE, Issue 1 2006M. V. Belmonte Coalition formation is an important mechanism for cooperation in multiagent systems. In this paper we address the problem of coalition formation among self-interested agents in superadditive task-oriented domains. We assume that each agent has some "structure," i.e., that it can be described by the values taken by a set of m nonnegative attributes that represent the resources w each agent is endowed with. By defining the coalitional value as a function V of w, we prove a sufficient condition for the existence of a stable payment configuration,in the sense of the core,in terms of certain properties of V. We apply these ideas to a simple case that can be described by a linear program and show that it is possible to compute for it,in polynomial time,an optimal task allocation and a stable payment configuration. [source] On the construction of maximum residual energy resource broadcast trees with minimum diameter in static ad hoc wireless networksINTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, Issue 1 2006Chor Ping Low Abstract Each node in a wireless ad hoc network runs on a local energy source that has a limited energy life span. Thus, energy conservation is a critical issue in such networks. In addition, it is in general desirable to construct routes with low hop counts as a route with a high hop count is more likely to be unstable (because the probability that intermediate nodes will move away is higher). In this paper, we address these two issues concurrently with energy conservation as the primary objective and low hop count as the secondary objective. One way of addressing the energy conservation issue is to construct routes that maximize the minimum residual battery capacity available among all nodes in each route. A broadcast tree with all routes satisfying this condition is referred to as a maximum residual energy resource broadcast tree. A maximum residual energy resource broadcast tree with the least diameter is referred to as a minimum diameter maximum residual energy resource broadcast tree and the problem of constructing such a tree is referred to as the minimum diameter maximum residual energy resource broadcast routing problem (MDMRERBRP). We propose an algorithm for MDMRERBRP and prove that MDMRERBRP is optimally solvable in polynomial time using the proposed algorithm. Copyright © 2005 John Wiley & Sons, Ltd. [source] Toward a comprehensive treatment of temporal constraints about periodic eventsINTERNATIONAL JOURNAL OF INTELLIGENT SYSTEMS, Issue 4 2003Paolo Terenziani In this article, we propose an Allen-like approach to deal with different types of temporal constraints about periodic events. We consider the different components of such constraints (thus, unlike Allen, we also take into account quantitative constraints) including frame times, user-defined periods, qualitative temporal constraints, and numeric quantifiers and the interactions between such components. We propose a specialized high-level formalism to represent temporal constraints about periodic events; temporal reasoning on the formalism is performed by a path-consistency algorithm repeatedly applying our operations of inversion, intersection, and composition and by a specialized reasoner about periods and numeric quantification. The high-level formalism has been designed in such a way that different types of temporal constraints about periodic events can be represented in a compact and (hopefully) user-friendly way and path-consistency-based temporal reasoning on the formalism can be performed in polynomial time. We also prove that our definitions of inversion, intersection, and composition and, thus, of our path-consistency algorithm, are correct. This article also sketches the general architecture of the temporal manager for periodic events (TeMP+), that has been designed on the basis of our approach. As a working example, we show an application of our approach to scheduling in a school. © 2003 Wiley Periodicals, Inc. [source] Elementary explicit types and polynomial time operationsMLQ- MATHEMATICAL LOGIC QUARTERLY, Issue 3 2009Daria Spescha Abstract This paper studies systems of explicit mathematics as introduced by Feferman [9, 11]. In particular, we propose weak explicit type systems with a restricted form of elementary comprehension whose provably terminating operations coincide with the functions on binary words that are computable in polynomial time. The systems considered are natural extensions of the first-order applicative theories introduced in Strahm [19, 20] (© 2009 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [source] Generic separations and leaf languagesMLQ- MATHEMATICAL LOGIC QUARTERLY, Issue 4 2003Matthias Galota Abstract In the early nineties of the previous century, leaf languages were introduced as a means for the uniform characterization of many complexity classes, mainly in the range between P (polynomial time) and PSPACE (polynomial space). It was shown that the separability of two complexity classes can be reduced to a combinatorial property of the corresponding defining leaf languages. In the present paper, it is shown that every separation obtained in this way holds for every generic oracle in the sense of Blum and Impagliazzo. We obtain several consequences of this result, regarding, e. g., universal oracles, simultaneous separations and type-2 complexity. [source] Approximation algorithms for general one-warehouse multi-retailer systemsNAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 7 2009Zuo-Jun Max Shen Abstract Logistical planning problems are complicated in practice because planners have to deal with the challenges of demand planning and supply replenishment, while taking into account the issues of (i) inventory perishability and storage charges, (ii) management of backlog and/or lost sales, and (iii) cost saving opportunities due to economies of scale in order replenishment and transportation. It is therefore not surprising that many logistical planning problems are computationally difficult, and finding a good solution to these problems necessitates the development of many ad hoc algorithmic procedures to address various features of the planning problems. In this article, we identify simple conditions and structural properties associated with these logistical planning problems in which the warehouse is managed as a cross-docking facility. Despite the nonlinear cost structures in the problems, we show that a solution that is within ,-optimality can be obtained by solving a related piece-wise linear concave cost multi-commodity network flow problem. An immediate consequence of this result is that certain classes of logistical planning problems can be approximated by a factor of (1 + ,) in polynomial time. This significantly improves upon the results found in literature for these classes of problems. We also show that the piece-wise linear concave cost network flow problem can be approximated to within a logarithmic factor via a large scale linear programming relaxation. We use polymatroidal constraints to capture the piece-wise concavity feature of the cost functions. This gives rise to a unified and generic LP-based approach for a large class of complicated logistical planning problems. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009 [source] Single-warehouse multi-retailer inventory systems with full truckload shipmentsNAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 5 2009Yue Jin Abstract We consider a multi-stage inventory system composed of a single warehouse that receives a single product from a single supplier and replenishes the inventory of n retailers through direct shipments. Fixed costs are incurred for each truck dispatched and all trucks have the same capacity limit. Costs are stationary, or more generally monotone as in Lippman (Management Sci 16, 1969, 118,138). Demands for the n retailers over a planning horizon of T periods are given. The objective is to find the shipment quantities over the planning horizon to satisfy all demands at minimum system-wide inventory and transportation costs without backlogging. Using the structural properties of optimal solutions, we develop (1) an O(T2) algorithm for the single-stage dynamic lot sizing problem; (2) an O(T3) algorithm for the case of a single-warehouse single-retailer system; and (3) a nested shortest-path algorithm for the single-warehouse multi-retailer problem that runs in polynomial time for a given number of retailers. To overcome the computational burden when the number of retailers is large, we propose aggregated and disaggregated Lagrangian decomposition methods that make use of the structural properties and the efficient single-stage algorithm. Computational experiments show the effectiveness of these algorithms and the gains associated with coordinated versus decentralized systems. Finally, we show that the decentralized solution is asymptotically optimal. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009 [source] An economic lot-sizing problem with perishable inventory and economies of scale costs: Approximation solutions and worst case analysisNAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 6 2005Leon Yang Chu Abstract The costs of many economic activities such as production, purchasing, distribution, and inventory exhibit economies of scale under which the average unit cost decreases as the total volume of the activity increases. In this paper, we consider an economic lot-sizing problem with general economies of scale cost functions. Our model is applicable to both nonperishable and perishable products. For perishable products, the deterioration rate and inventory carrying cost in each period depend on the age of the inventory. Realizing that the problem is NP-hard, we analyze the effectiveness of easily implementable policies. We show that the cost of the best Consecutive-Cover-Ordering (CCO) policy, which can be found in polynomial time, is guaranteed to be no more than (4 + 5)/7 , 1.52 times the optimal cost. In addition, if the ordering cost function does not change from period to period, the cost of the best CCO policy is no more than 1.5 times the optimal cost. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005. [source] A generalization of the weighted set covering problemNAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 2 2005Jian Yang Abstract We study a generalization of the weighted set covering problem where every element needs to be covered multiple times. When no set contains more than two elements, we can solve the problem in polynomial time by solving a corresponding weighted perfect b -matching problem. In general, we may use a polynomial-time greedy heuristic similar to the one for the classical weighted set covering problem studied by D.S. Johnson [Approximation algorithms for combinatorial problems, J Comput Syst Sci 9 (1974), 256,278], L. Lovasz [On the ratio of optimal integral and fractional covers, Discrete Math 13 (1975), 383,390], and V. Chvatal [A greedy heuristic for the set-covering problem, Math Oper Res 4(3) (1979), 233,235] to get an approximate solution for the problem. We find a worst-case bound for the heuristic similar to that for the classical problem. In addition, we introduce a general type of probability distribution for the population of the problem instances and prove that the greedy heuristic is asymptotically optimal for instances drawn from such a distribution. We also conduct computational studies to compare solutions resulting from running the heuristic and from running the commercial integer programming solver CPLEX on problem instances drawn from a more specific type of distribution. The results clearly exemplify benefits of using the greedy heuristic when problem instances are large. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2005 [source] Mixed search number and linear-width of interval and split graphsNETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2010Fedor V. Fomin Abstract We show that the mixed search number and the linear-width of interval graphs and of split graphs can be computed in linear time and in polynomial time, respectively. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010 [source] Approximability of the k -server disconnection problemNETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2007Sung-Pil Hong Abstract Consider a network of k servers and their users. Each server provides a unique service that has a certain utility for each user. Now comes an attacker who wishes to destroy a set of network edges to maximize his net gain, namely the total disconnected utilities of the users minus the total edge-destruction cost. This k -server disconnection problem is NP -hard and, furthermore, cannot be approximated within a polynomially computable factor of the optimum when k is part of the input. Even for any fixed k , 2, there is a constant , > 0 such that approximation of the problem within a factor 1/(1 + ,) of the optimum is NP-hard. However, a ( )-approximation can be created in the time of O(2k) applications of a min-cut algorithm. The main idea is to approximate the optimum with special solutions computable in polynomial time due to supermodularity. Therefore, when the the network has, as is usual in most cases, only a few servers, a 0.5-approximation can be carried out in polynomial time. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(4), 273,282 2007 [source] Multiterminal resilience for series-parallel networksNETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2007Toni R. Farley Abstract Network resilience measures the average two-terminal reliability (connectedness) of a network. Multiterminal resilience extends this measure to any k vertices; it is the average k -terminal reliability of a network. This generalizes two well-studied network connectedness measures. Calculating multiterminal resilience on general networks encompasses all-terminal reliability and thus is NP-hard. Multiterminal resilience is examined on undirected series-parallel networks, and an efficient (polynomial time) algorithm is developed for calculating the resilience for every k. Applications in mobile ad hoc and sensor networks are outlined. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(2), 164,172 2007 [source] The ring grooming problemNETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2004Timothy Y. Chow Abstract The problem of minimizing the number of bidirectional SONET rings required to support a given traffic demand has been studied by several researchers. Here we study the related ring-grooming problem of minimizing the number of add/drop locations instead of the number of rings; in a number of situations this is a better approximation to the true equipment cost. Our main result is a new lower bound for the case of uniform traffic. This allows us to prove that a certain simple algorithm for uniform traffic is, in fact, a constant-factor approximation algorithm, and it also demonstrates that known lower bounds for the general problem,in particular, the linear programming relaxation,are not within a constant factor of the optimum. We also show that our results for uniform traffic extend readily to the more practically important case of quasi-uniform traffic. Finally, we show that if the number of nodes on the ring is fixed, then ring grooming is solvable in polynomial time; however, whether ring grooming is fixed-parameter tractable is still an open question. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(3), 194,202 2004 [source] Minimizing beam-on time in cancer radiation treatment using multileaf collimatorsNETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2004Natashia Boland Abstract In this article the modulation of intensity matrices arising in cancer radiation therapy using multileaf collimators (MLC) is investigated. It is shown that the problem is equivalent to decomposing a given integer matrix into a positive linear combination of (0, 1) matrices. These matrices, called shape matrices, must have the strict consecutive-1-property, together with another property derived from the technological restrictions of the MLC equipment. Various decompositions can be evaluated by their beam-on time (time during which radiation is applied to the patient) or the treatment time (beam-on time plus time for setups). We focus on the former, and develop a nonlinear mixed-integer programming formulation of the problem. This formulation can be decomposed to yield a column generation formulation: a linear program with a large number of variables that can be priced by solving a subproblem. We then develop a network model in which paths in the network correspond to feasible shape matrices. As a consequence, we deduce that the column generation subproblem can be solved as a shortest path problem. Furthermore, we are able to develop two alternative models of the problem as side-constrained network flow formulations, and so obtain our main theoretical result that the problem is solvable in polynomial time. Finally, a numerical comparison of our exact solutions with those of well-known heuristic methods shows that the beam-on time can be reduced by a considerable margin. © 2004 Wiley Periodicals, Inc. [source] The clique partitioning problem: Facets and patching facetsNETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2001Maarten Oosten Abstract The clique partitioning problem (CPP) can be formulated as follows: Given is a complete graph G = (V, E), with edge weights wij , , for all {i, j} , E. A subset A , E is called a clique partition if there is a partition of V into nonempty, disjoint sets V1,,, Vk, such that each Vp (p = 1,,, k) induces a clique (i.e., a complete subgraph), and A = , {{i, j}|i, j , Vp, i , j}. The weight of such a clique partition A is defined as ,{i,j},Awij. The problem is now to find a clique partition of maximum weight. The clique partitioning polytope P is the convex hull of the incidence vectors of all clique partitions of G. In this paper, we introduce several new classes of facet-defining inequalities of P. These suffice to characterize all facet-defining inequalities with right-hand side 1 or 2. Also, we present a procedure, called patching, which is able to construct new facets by making use of already-known facet-defining inequalities. A variant of this procedure is shown to run in polynomial time. Finally, we give limited empirical evidence that the facet-defining inequalities presented here can be of use in a cutting-plane approach for the clique partitioning problem. © 2001 John Wiley & Sons, Inc. [source] Multigraph augmentation under biconnectivity and general edge-connectivity requirements ,NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2001Toshimasa Ishii Abstract Given an undirected multigraph G = (V, E) and a requirement function r,: () , Z+ (where () is the set of all pairs of vertices and Z+ is the set of nonnegative integers), we consider the problem of augmenting G by the smallest number of new edges so that the local edge-connectivity and vertex-connectivity between every pair x, y , V become at least r,(x, y) and two, respectively. In this paper, we show that the problem can be solved in O(n3(m + n) log(n2/(m + n))) time, where n and m are the numbers of vertices and pairs of adjacent vertices in G, respectively. This time complexity can be improved to O((nm + n2 log n) log n), in the case of the uniform requirement r,(x, y)= ,, for all x, y , V. Furthermore, for the general r,, we show that the augmentation problem that preserves the simplicity of the resulting graph can be solved in polynomial time for any fixed ,,* = max{r,(x, y) | x, y , V}. © 2001 John Wiley & Sons, Inc. [source] DEADLOCK AVOIDANCE FOR FLEXIBLE MANUFACTURING SYSTEMS WITH CHOICES BASED ON DIGRAPH CIRCUIT ANALYSISASIAN JOURNAL OF CONTROL, Issue 2 2007Wenle Zhang ABSTRACT Due to existence of concurrent part flows and resource sharing in modern automated flexible manufacturing systems (FMS), deadlock is a common problem and its occurrence causes loss of productivity. When a manufacturing system is modeled by a digraph, existence of circuits in such a graph is a necessary condition for deadlock. Our previous work further showed that the knot and order of a circuit is closely related to impending deadlocks , a type of deadlock that is more difficult to detect. In this paper, we extend our previous work on deadlock avoidance for flexible manufacturing systems to allow choices in process flows (a.k.a., flexible part routing). Due to introduction of choices, part flow dynamics become more sophisticated and our previous results are no longer valid. A systematic circuit analysis is performed in this paper. New concepts such as broken circuit, basic circuit, choice circuit and supremal circuit are introduced to reduce significantly the number of circuits thus improving efficiency of our approach. The extended method is highly permissive with the adjusted effective free space calculation to capture more necessary parts flow dynamics, especially when multiple knots exist in the digraph model. The online policy runs in polynomial time once the set of basic circuits of the digraph is computed offline. Simulation results on selected examples are given. [source] | ||||||||||||||||