Home About us Contact
|
Home About us Contact | ||
|
|
||
Greedy Algorithm (greedy + algorithm)
Selected AbstractsService restoration method considering simultaneous disconnection of distributed generators by one-bank fault of distribution systemELECTRONICS & COMMUNICATIONS IN JAPAN, Issue 8 2008Hirotaka Takano Abstract Distributed generators (DGs) such as fuel cells and solar cells are going to be installed in the demand side of distribution systems. The DGs can reduce distribution loss by appropriate allocation. However, there are several problems installing DGs such as service restoration of distribution system with DGs and so on. When one bank fault of distribution substation occurs in distribution system, since DGs are simultaneously disconnected from the system, it is not easy to restore isolated load by one bank switching in distribution substation. Therefore, a service restoration method to determine restoration configuration and restoration procedures (switching procedure from normal configuration to restoration configuration) taking into account simultaneous disconnection of DGs is needed. In this paper, the authors propose a computation method to determine the optimal restoration configuration and the restoration procedure considering simultaneous disconnection of DGs by one bank fault of distribution system. In the proposed algorithm, after all of the restoration configuration candidates are effectively enumerated under the operational constraints, the optimal configuration to restore the isolated load is selected among enumerated configuration candidates. After determining the optimal restoration configuration, the optimal restoration procedures are obtained by greedy algorithm. Numerical simulations are carried out for a real scale system model with 237 sectionalizing switches (configuration candidates are 2237) and 21 DGs (total output is 5250 kW which is 3% of total load) in order to examine the validity of the proposed algorithm. © 2008 Wiley Periodicals, Inc. Electron Comm Jpn, 91(8): 44,55, 2008; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecj.10133 [source] Optimizing Patching-based multicast for video-on-demand in wireless mesh networksINTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, Issue 9-10 2010Fei Xie Abstract In this work, we study the application of video-on-demand (VoD) in wireless mesh networks (WMN), a next generation edge technology to provide broadband data access in residential, business and even city-wise networks. We adopt a Patching-based multicast technique to better utilize the bandwidth resources in the mesh network. We optimize the Patching-based multicast by addressing two critical problems, namely, the Minimum Cost Multicast Tree (MCMT) problem and the Maximum Benefit Multicast Group (MBMG) problem. The MCMT problem is to find a MCMT in the network. We show that finding such a tree in the WMN can be formulated as a graph theory problem, which is to find the tree with minimum number of non-leaf nodes, and which spans all the nodes in the multicast group. We further prove the problem is NP-hard and propose a fast greedy algorithm to accommodate the real-time feature of the VoD application. We solve the MBMG problem by minimizing the communication of a Patching group in the entire network. A Markov model is proposed to capture the growth of the multicast group in the WMN. Simulation study results validate the proposed solutions of the two problems. Copyright © 2009 John Wiley & Sons, Ltd. [source] An Explicit Solution of a Generalized Optimum Requirement Spanning Tree Problem With a Property Related to MongeINTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 3 2001Tsutomu Anazawa The paper considers a generalization of the optimum requirement spanning tree problem (ORST problem) first studied by Hu in 1974. Originally, ORST was regarded as a communication network of tree type with the minimum average cost, and it is obtained by the well-known Gomory,Hu algorithm when the degrees of vertices are not restricted. The ORST problem is generalized by (i) generalizing the objective function and (ii) imposing maximum degree constraints. The generalized ORST problem includes some practical problems, one of which is proposed in this paper, but is not efficiently solvable in general. However, I show that a particular tree (which is obtained by a sort of greedy algorithm but is explicitly definable) is a solution of the generalized problem when a certain practical condition is satisfied. The condition is closely related to the Monge property, which is originally discussed in the Hitchcock transportation problem, and is known to make some NP-hard problems efficiently solvable. [source] The sequential sum problem and performance bounds on the greedy algorithm for the on-line Steiner problemNETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2005Zevi Miller Abstract This article is motivated by versions of the dynamic or "on-line" Steiner tree problem (OST) introduced by Imase and Waxman [4]. In this problem one is given an edge-weighted graph G and a sequence , = (x1,,,xn) of distinct vertices of G. The requirement is to construct for each i , n a tree Ti spanning the first i vertices of , subject to the condition that Ti,1,Ti for all i, where Ti is constructed without knowledge of the remaining vertices xj, j > i. The goal of the on-line Steiner problem is to minimize the performance ratio; that is, the maximum (over 1 , i , n) of the ratio of the weight of Ti to the weight of the minimum weight tree in G spanning the first i vertices (the latter tree is called the "Steiner tree" for these vertices). In [4] a lower bound of 1 + ˝, log2(n,1), was proved for this ratio. The authors further made the interesting conjecture that there is some on-line algorithm for the OST whose performance ratio achieves this lower bound. We show that a strong form of the greedy algorithm achieves a ratio that converges to the conjectured ˝log2(k) + O(1) as the proportion of degree 2 vertices in the instance graph grows. Our results also imply improvements in certain cases on the known upper bound ,log2(n), for the performance ratio of the greedy algorithm. Our approach is to study a related graph parameter. For each sequence , as above, define the associated cost where c(i,,) = min1 , t < idist(xi, xt). Then let Opt(n, G) be the maximum of L(,) over all such sequences , of length n. The problem of, given n and G, determining Opt(n, G) we call the Sequential Sum Problem (SSP). In this article we analyze the SSP, obtaining exact values and bounds on Opt(n, G) and relating these bounds to the greedy algorithm for the OST. For example, we calculate Opt(n, P) for the path P, and obtain a surprising characterization of all length n sequences , which realize Opt(n, P). By analyzing Opt(n, P) for the "continuous" path, we derive upper bounds on the performance ratio of the greedy algorithm for the OST in arbitrary graphs. On the other hand, generalizing the lower bound argument of [4] we show that there are instances of OST, which can significantly "fool" any on-line algorithm for OST. Specifically, given any tree T normalized to have total edge weight 1, we construct a graph G and a length k , |V(T)| sequence , of vertices of G for which the performance ratio of any on-line algorithm for the OST with input , is lower bounded by Opt(k, T). Finally, we show that the SSP for arbitrary G is NP-complete. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(3), 143,164 2005 [source] The facility location problem with general cost functionsNETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2003M. T. Hajiaghayi Abstract In this paper, we introduce a generalized version of the facility location problem in which the facility cost is a function of the number of clients assigned to the facility. We focus on the case of concave facility cost functions. We observe that this problem can be reduced to the uncapacitated facility location problem. We analyze a natural greedy algorithm for this problem and show that its approximation factor is at most 1.861. We also consider several generalizations and variants of this problem. © 2003 Wiley Periodicals, Inc. [source] Probabilistic cross-link analysis and experiment planning for high-throughput elucidation of protein structurePROTEIN SCIENCE, Issue 12 2004Xiaoduan Ye Abstract Emerging high-throughput techniques for the characterization of protein and protein-complex structures yield noisy data with sparse information content, placing a significant burden on computation to properly interpret the experimental data. One such technique uses cross-linking (chemical or by cysteine oxidation) to confirm or select among proposed structural models (e.g., from fold recognition, ab initio prediction, or docking) by testing the consistency between cross-linking data and model geometry. This paper develops a probabilistic framework for analyzing the information content in cross-linking experiments, accounting for anticipated experimental error. This framework supports a mechanism for planning experiments to optimize the information gained. We evaluate potential experiment plans using explicit trade-offs among key properties of practical importance: discriminability, coverage, balance, ambiguity, and cost. We devise a greedy algorithm that considers those properties and, from a large number of combinatorial possibilities, rapidly selects sets of experiments expected to discriminate pairs of models efficiently. In an application to residue-specific chemical cross-linking, we demonstrate the ability of our approach to plan experiments effectively involving combinations of cross-linkers and introduced mutations. We also describe an experiment plan for the bacteriophage , Tfa chaperone protein in which we plan dicysteine mutants for discriminating threading models by disulfide formation. Preliminary results from a subset of the planned experiments are consistent and demonstrate the practicality of planning. Our methods provide the experimenter with a valuable tool (available from the authors) for understanding and optimizing cross-linking experiments. [source] Hiding role assignment in mission-critical collaborative systemsQUALITY AND RELIABILITY ENGINEERING INTERNATIONAL, Issue 3 2002Xinwen Fu Abstract In a mission critical collaboration system, a group of roles are assigned to computer nodes connected by a communication network. Role assignment is mission-critical information and needs to be protected. In this paper, we develop methods to effectively and efficiently protect the information of role assignment from traffic analysis, a passive attack. To measure the system security, we introduce a metric of detection probability, defined as the probability that a role assignment can be discovered. A heuristic greedy algorithm is given to minimize the resource consumption while guaranteeing a low detection-probability level. Our performance evaluation shows that the algorithm proposed in this paper performs well in terms of execution time and resource usage compared to an exhaustive search algorithm. We also propose to use additional means (e.g. additional nodes) to further increase the security level of a system at the cost of a mild resource consumption increase. Copyright © 2002 John Wiley & Sons, Ltd. [source] Greedy colorings of uniform hypergraphsRANDOM STRUCTURES AND ALGORITHMS, Issue 2 2009András Pluhár Abstract We give a very short proof of an Erd,s conjecture that the number of edges in a non-2-colorable n -uniform hypergraph is at least f(n)2n, where f(n) goes to infinity. Originally it was solved by József Beck in 1977, showing that f(n) at least clog n. With an ingenious recoloring idea he later proved that f(n) , cn1/3+o(1). Here we prove a weaker bound on f(n), namely f(n) , cn1/4. Instead of recoloring a random coloring, we take the ground set in random order and use a greedy algorithm to color. The same technique works for getting bounds on k -colorability. It is also possible to combine this idea with the Lovász Local Lemma, reproving some known results for sparse hypergraphs (e.g., the n -uniform, n -regular hypergraphs are 2-colorable if n , 8). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 [source] Multiple choice tries and distributed hash tablesRANDOM STRUCTURES AND ALGORITHMS, Issue 3 2009Luc Devroye In this article we consider tries built from n strings such that each string can be chosen from a pool of k strings, each of them generated by a discrete i.i.d. source. Three cases are considered: k = 2, k is large but fixed, and k , clog n. The goal in each case is to obtain tries as balanced as possible. Various parameters such as height and fill-up level are analyzed. It is shown that for two-choice tries a 50% reduction in height is achieved when compared with ordinary tries. In a greedy online construction when the string that minimizes the depth of insertion for every pair is inserted, the height is only reduced by 25%. To further reduce the height by another 25%, we design a more refined online algorithm. The total computation time of the algorithm is O(nlog n). Furthermore, when we choose the best among k , 2 strings, then for large but fixed k the height is asymptotically equal to the typical depth in a trie. Finally, we show that further improvement can be achieved if the number of choices for each string is proportional to log n. In this case highly balanced trees can be constructed by a simple greedy algorithm for which the difference between the height and the fill-up level is bounded by a constant with high probability. This, in turn, has implications for distributed hash tables, leading to a randomized ID management algorithm in peer-to-peer networks such that, with high probability, the ratio between the maximum and the minimum load of a processor is O(1). © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009 [source] | |||||||||||||