检索结果-内蒙古大学图书馆

combinatorial ANALYSIS OF AN EFFICIENT ALGORITHM FOR PROCESSOR AND STORAGE ALLOCATION

SIAM JOURNAL ON COMPUTING 1979年第2期8卷 202-217页

作者： COFFMAN, EG LEUNG, JYT

An NPNPNP-complete bin-packing problem is studied in which the objective is to maximize the number of pieces packed into a fixed set of equal capacity bins. Applications to processor and storage allocation in computer... 详细信息

N P

$NP$ -complete bin-packing problem is studied in which the objective is to maximize the number of pieces packed into a fixed set of equal capacity bins. Applications to processor and storage allocation in computer systems are discussed, and an efficient approximation algorithm is defined and studied. The main results are bounds on the complexity of the algorithm and on its performance.

关键词： bin-packing storage allocation scheduling theory combinatorial algorithms approximation algorithms worst-case performance bounds

来源：评论

学校读者我要写书评

暂无评论

combinatorial Multigrid: Advanced Preconditioners For Ill-Conditioned Linear Systems

Combinatorial Multigrid: Advanced Preconditioners For Ill-Co...

引用

IEEE High Performance Extreme Computing Conference (HPEC)

作者： Langston, M. Harper Harris, Mitchell Tong Letourneau, Pierre-David Lethin, Richard Ezick, James Reservoir Labs Inc New York NY 10012 USA

ISBN: (纸本)9781728150208

The combinatorial Multigrid (CMG) technique is a practical and adaptable solver and combinatorial preconditioner for solving certain classes of large, sparse systems of linear equations. CMG is similar to Algebraic Multigrid (AMG) but replaces large groupings of fine-level variables with a single coarse-level one, resulting in simple and fast interpolation schemes. These schemes further provide control over the refinement strategies at different levels of the solver hierarchy depending on the condition number of the system being solved [1]. While many pre-existing solvers may be able to solve large, sparse systems with relatively low complexity, inversion may require O(n(2)) space;whereas, if we know that a linear operator has n = O(n) nonzero elements, we desire to use O(n) space in order to reduce communication as much as possible. Being able to invert sparse linear systems of equations, asymptotically as fast as the values can be read from memory, has been identified by the Defense Advanced Research Projects Agency (DARPA) and the Department of Energy (DOE) as increasingly necessary for scalable solvers and energy-efficient algorithms [2], [3] in scientific computing. Further, as industry and government agencies move towards exascale, fast solvers and communication-avoidance will be more necessary [4], [5]. In this paper, we present an optimized implementation of the combinatorial Multigrid in C using Petsc and analyze the solution of various systems using the CMG approach as a preconditioner on much larger problems than have been presented thus far. We compare the number of iterations, setup times and solution times against other popular preconditioners for such systems, including Incomplete Cholesky and a Multigrid approach in Petsc against common problems, further exhibiting superior performance by the CMG.

关键词： combinatorial algorithms spectral support solver linear systems fast solvers preconditioners multigrid graph laplacian benchmarking iterative solvers

来源：评论

学校读者我要写书评

暂无评论

A combinatorial Algorithm for Base-station Location Optimization for LTE Mixed-Cell MIMO Wireless Systems 9

A Combinatorial Algorithm for Base-station Location Optimiza...

引用

9th European Conference on Antennas and Propagation EuCAP

作者： Athanasiadou, G. E. Tsoulos, G. V. Zarbouti, D. Univ Peloponnese Dept Informat & Telecommun Tripoli Greece

ISBN: (纸本)9788890701856

The optimization of base station locations started with coverage and traffic criteria. Nowadays, the increased demand for geographically inhomogeneous capacity leads to mixed cell structures as well as relay nodes, while the cost of the different deployments varies significantly. Furthermore, MIMO technology offers solutions to the ever increasing capacity requirements. The peculiarity of heterogeneous systems is that the optimum solution can be a small group of macrocells or a large number of microcells or anything in between. The algorithm presented here has been developed specifically for heterogeneous wireless systems, follows a combinatorial approach and the optimization analysis is based on the triplet coverage, capacity and cost. Results demonstrate the adaptive performance of the algorithm and the tendency towards the deployment of very small cells as capacity increases, as well as the considerable capacity increase and planning flexibility offered by MIMO techniques.

关键词： Base-station location optimization Mixed-cell wireless systems combinatorial algorithms MIMO

来源：评论

学校读者我要写书评

暂无评论

The Haplotyping Problem：An Overview of Computational Models and Solutions

引用

Journal of Computer Science & Technology 2003年第6期18卷 675-688页

作者： PaolaBonizzoni GianlucaDellaVedova RiccardoDondi JingLi DISCo viaBicoccadegliArcimboldi8UniversityofMilano-Bicocca20135-MilanoItaly Dip.Statistica viaBicoccadegliArcimboldi8UniversityofMilano-Bicocca20135-MilanoItaly DISCo viaBicoccadegliArcimboldi8UniversityofMilano-Bicocca20135-MilanoItaly DepartmentofComputerScience UniversityofCaliforniaatRiversideRiversideCAUSA

The investigation of genetic differences among humans has given evidence thatmutations in DNA sequences are responsible for some genetic diseases. The most common mutation isthe one that involves only a single nucleotide of the DNA sequence, which is called a singlenucleotide polymorphism (SNP). As a consequence, computing a complete map of all SNPs occurring inthe human populations is one of the primary goals of recent studies in human genomics. Theconstruction of such a map requires to determine the DNA sequences that from all chromosomes. Indiploid organisms like humans, each chromosome consists of two sequences called *** the information contained in both haplotypes when analyzing chromosome sequencesposes several new computational issues which collectively form a new emerging topic of ComputationalBiology known as Haplotyping. This paper is a comprehensive study of some new combinatorialapproaches proposed in this research area and it mainly focuses on the formulations and algorithmicsolutions of some basic biological problems. Three statistical approaches are briefly discussed atthe end of the paper.

关键词： bioinformatics combinatorial algorithms haplotypes

来源：评论

学校读者我要写书评

暂无评论

Detecting and enumerating small induced subgraphs in c-closed graphs

引用

DISCRETE APPLIED MATHEMATICS 2021年 302卷 198-207页

作者： Koana, Tomohiro Nichterlein, Andre TU Berlin Fac 4 Algorithm & Computat Complex Berlin Germany

Fox et al. (2020) introduced a new parameter, called c-closure, for a parameterized study of clique enumeration problems. A graph G is c-closed if every pair of vertices with at least c common neighbors is adjacent. The c-closure of G is the smallest c such that G is c-closed. We systematically explore the impact of c-closure on the computational complexity of detecting and enumerating small induced subgraphs. More precisely, for each graph H on three or four vertices, we investigate parameterized polynomial-time algorithms for detecting H and for enumerating all occurrences of H in a given c-closed graph. (C) 2021 Elsevier B.V. All rights reserved.

关键词： FPT in P combinatorial algorithms Subgraph detection Subgraph enumeration

来源：评论

学校读者我要写书评

暂无评论

Information raining and optimal link-layer design for mobile hotspots

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2005年第3期4卷 271-284页

作者： Ho, DH Valaee, S Redknee Inc Mississauga ON L4W 4Y9 Canada Univ Toronto Dept Elect & Comp Engn Toronto ON M5S 3G4 Canada

In this paper, we propose a link layer design for mobile hotspots. We design a novel system architecture that enables highspeed Internet access in railway systems. The proposed design uses a number of repeaters placed along the track and multiple antennas installed on the roof of a vehicle. Each packet is decomposed into smaller fragments and relayed to the vehicle via adjacent repeaters. We also use erasure coding to add parity fragments to original data. This approach is called information raining since fragments are rained upon the vehicle from adjacent repeaters. We investigate two instances of information raining. In blind information raining, all repeaters awaken when they sense the presence of the vehicle. The fragments are then blindly transmitted via awakened repeaters. A vehicle station installed inside the train is responsible for aggregating a large enough number of fragments. In the throughput-optimized information raining, the vehicle station selects a bipartite matching between repeaters and roof-top antennas and activates only a subset of the repeaters. It also dictates the amount of transmission power of each activated repeater. Both the bipartite matching and power allocations are individually shown to be NP-complete. Matching heuristics based on the Hungarian algorithm and Gale-Shapley algorithm are proposed. A simplex-type algorithm is proposed as the power allocation heuristics.

关键词： emerging technologies network architecture and design wireless communication network protocols mobile communication systems mobile environments medium access control mobile hotspots graphs and networks linear programming constrained optimization graph theory combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

The complexity of the single individual SNP haplotyping problem

引用

ALGORITHMICA 2007年第1期49卷 13-36页

作者： Cilibrasi, Rudi van Iersel, Leo Kelk, Steven Tromp, John Ctr Wiskunde & Informat NL-1098 SJ Amsterdam Netherlands Tech Univ Eindhoven NL-5612 AX Eindhoven Netherlands

We present several new results pertaining to haplotyping. These results concern the combinatorial problem of reconstructing haplotypes from incomplete and/or imperfectly sequenced haplotype fragments. We consider the complexity of the problems Minimum Error Correction (MEC) and Longest Haplotype Reconstruction (LHR) for different restrictions on the input data. Specifically, we look at the gapless case, where every row of the input corresponds to a gapless haplotype-fragment, and the 1-gap case, where at most one gap per fragment is allowed. We prove that MEC is APX-hard in the 1-gap case and still NP-hard in the gapless case. In addition, we question earlier claims that MEC is NP-hard even when the input matrix is restricted to being completely binary. Concerning LHR, we show that this problem is NP-hard and APX-hard in the 1-gap case (and thus also in the general case), but is polynomial time solvable in the gapless case.

关键词： combinatorial algorithms complexity hierarchies complexity of approximation computational biology genetics

来源：评论

学校读者我要写书评

暂无评论

Untangling Tanglegrams: Comparing Trees by Their Drawings

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2010年第4期7卷 588-597页

作者： Venkatachalam, Balaji Apple, Jim John, Katherine St. Gusfield, Dan Univ Calif Davis Dept Comp Sci Davis CA 95616 USA Lehman Coll Dept Math & Comp Sci W Bronx NY 10468 USA CUNY Grad Ctr W Bronx NY 10468 USA

A tanglegram is a pair of trees on the same set of leaves with matching leaves in the two trees joined by an edge. Tanglegrams are widely used in biology-to compare evolutionary histories of host and parasite species and to analyze genes of species in the same geographical area. We consider optimization problems in tanglegram drawings. We show a linear time algorithm to decide if a tanglegram admits a planar embedding by a reduction to the planar graph drawing problem. This problem was also studied by Fernau et al. [15]. A similar reduction to a graph crossing problem also helps to solve an open problem they posed, showing a fixed-parameter tractable algorithm for minimizing the number of crossings over all d-ary trees. For the case where one tree is fixed, we show an O(n log n) algorithm to determine the drawing of the second tree that minimizes the number of crossings. This improves the bound from earlier methods. We introduce a new optimization criterion using Spearman's footrule distance and give an O(n(2)) algorithm. We also show integer programming formulations to quickly obtain tanglegram drawings that minimize the two optimization measures discussed. We prove lower bounds on the maximum gap between the optimal solution and the heuristic of Dwyer and Schreiber [13] to minimize crossings.

关键词： Optimization combinatorial algorithms graph algorithms trees analysis of algorithms phylogeny tree comparison graph drawing combinatorics

来源：评论

学校读者我要写书评

暂无评论

Dynamic Programming and Graph algorithms in Computer Vision

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2011年第4期33卷 721-740页

作者： Felzenszwalb, Pedro F. Zabih, Ramin Univ Chicago Dept Comp Sci Chicago IL 60637 USA Cornell Univ Dept Comp Sci Ithaca NY 14853 USA

Optimization is a powerful paradigm for expressing and solving problems in a wide range of areas, and has been successfully applied to many vision problems. Discrete optimization techniques are especially interesting since, by carefully exploiting problem structure, they often provide nontrivial guarantees concerning solution quality. In this paper, we review dynamic programming and graph algorithms, and discuss representative examples of how these discrete optimization techniques have been applied to some classical vision problems. We focus on the low-level vision problem of stereo, the mid-level problem of interactive object segmentation, and the high-level problem of model-based recognition.

关键词： combinatorial algorithms vision and scene understanding artificial intelligence computing methodologies

来源：评论

学校读者我要写书评

暂无评论

Permutation Betting Markets: Singleton Betting with Extra Information

引用

ALGORITHMICA 2011年第4期60卷 853-876页

作者： Ghodsi, Mohammad Mahini, Hamid Mirrokni, Vahab S. Zadimoghaddam, Morteza Sharif Univ Technol Dept Comp Engn Tehren Iran Microsoft Res Redmond WA 98052 USA

We study permutation betting markets, introduced by Chen et al. (Proceedings of the ACM Conference on Electronic Commerce, 2007). For these markets, we consider subset bettings in which each trader can bet on a subset of candidates ending up in a subset of positions. We consider the revenue maximization problem for the auctioneer in two main frameworks: the risk-free revenue maximization (studied in Chen et al., Proceedings of the ACM Conference on Electronic Commerce, 2007), and the probabilistic revenue maximization. We also explore the use of some certain knowledge or extra information about the possible outcomes of the market. We first show that finding the optimal revenue in the risk-free model for the subset betting problem is inapproximable. This resolves an open question posed by Chen et al. (Proceedings of the ACM Conference on Electronic Commerce, 2007). In order to identify solvable variants of the problem, we propose the singleton betting language which allows traders to bet an arbitrary value on one candidate for one position. For singleton bettings, we first provide a linear-time implementable necessary and sufficient condition for existence of a solution with positive revenue for any possible outcome. Furthermore, we develop an LP-based polynomial-time algorithm to find the optimum solution of this problem. In addition, we show how to extend this LP-based method to handle some extra information about the possible outcomes. Finally, we consider the revenue maximization problem in a probabilistic setting. For this variant, we observe that the problem of maximizing the expected revenue is polynomial-time solvable, but we show that maximizing the probability of achieving a pre-specified revenue is #P-Complete.

关键词： Prediction markets Revenue maximization Betting markets Linear programming combinatorial algorithms Matching markets

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：