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

Aspects of a multivariate complexity analysis for Rectangle Tiling

OPERATIONS RESEARCH LETTERS 2011年第5期39卷 346-351页

作者： Nichterlein, Andre Dom, Michael Niedermeier, Rolf TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany Univ Jena Inst Informat D-6900 Jena Germany

We initiate a parameterized complexity study of the NP-hard problem to tile a positive integer matrix with rectangles, keeping the number of tiles and their maximum weight small. We show that the problem remains NP-hard even for binary matrices only using 1 x 1 and 2 x 2-squares as tiles and provide insight into the influence of naturally occurring parameters on the problem's complexity. (C) 2011 Elsevier B.V. All rights reserved.

关键词： combinatorial algorithms NP-hardness Computational complexity Fixed-parameter tractability

来源：评论

学校读者我要写书评

暂无评论

Generalized minimal cost flow problem in fuzzy nature: An application in bus network planning problem

引用

APPLIED MATHEMATICAL MODELLING 2008年第12期32卷 2490-2508页

作者： Ghatee, Mehdi Hashemi, S. Mehdi Amir Kabir Univ Technol Dept Comp Sci Tehran 158754413 Iran

The aim of minimal cost flow problem (MCFP) in fuzzy nature, which is denoted with FMCFP, is to find the least cost of the shipment of a commodity through a capacitated network in order to satisfy imprecise concepts in supply or demand of network nodes and capacity or cost of network links. Fuzzy supply-demand may arise in real problems, where incomplete statistical data or simulation results are used. Also, variation in the cost or capacity of links is commonly happening. In the present paper, after defining a total order on LR type fuzzy numbers, three models are studied;MCFP with fuzzy costs, MCFP with fuzzy supply-demand and a combination of two cases. For the first model, scaling negative cycle cancelling algorithm, which is a polynomial time algorithm, is proposed. For the second model, "nominal flow" is introduced which provides an efficient scheme for finding fuzzy flow. For the third model, we present an exact and some heuristic methods. Numerical examples are illustrated to demonstrate the efficiency of the proposed schemes. Finally, an application of this viewpoint in bus network planning problem is provided. (C) 2007 Elsevier Inc. All rights reserved.

关键词： fuzzy MCFP total ordering combinatorial algorithms nominality concept

来源：评论

学校读者我要写书评

暂无评论

Spending Constraint Utilities with Applications to the Adwords Market

引用

MATHEMATICS OF OPERATIONS RESEARCH 2010年第2期35卷 458-478页

作者： Vazirani, Vijay V. Georgia Inst Technol Coll Comp Atlanta GA 30332 USA

The notion of a "market" has undergone a paradigm shift with the Internet. Totally new and highly successful markets have been defined and launched by Internet companies, which already form an important part of today's economy and are projected to grow considerably in the future. Another major change is the availability of massive computational power for running these markets in a centralized or distributed manner. In view of these new realities, the study of market equilibria, an important, though essentially nonalgorithmic, theory within mathematical economics, needs to be revived and rejuvenated via an inherently algorithmic approach. Such a theory should not only address traditional market models, but also de. ne new models for some of the new markets. We present a new, natural class of utility functions that allow buyers to explicitly provide information on their relative preferences as a function of the amount of money spent on each good. These utility functions offer considerable expressivity, especially in Google's Adwords market. In addition, they lend themselves to efficient computation, while retaining some of the nice properties of traditional models. The latter include weak gross substitutability, and the uniqueness and continuity of equilibrium prices and utilities.

关键词： market equilibrium Fisher's model linear utilities piecewise-linear concave utilities Adwords market search engines combinatorial algorithms primal-dual algorithms weak gross substitutability

来源：评论

学校读者我要写书评

暂无评论

Simultaneous Identification of Duplications and Lateral Gene Transfers

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2011年第2期8卷 517-535页

作者： Tofigh, Ali Hallett, Michael Lagergren, Jens KTH Royal Inst Technol Sch Comp Sci & Commun Dept Computat Biol S-10044 Stockholm Sweden SBC S-10044 Stockholm Sweden McGill Univ McGill Ctr Bioinformat Montreal PQ H3G 0B1 Canada McGill Univ Sch Comp Sci Montreal PQ H3G 0B1 Canada

The incongruency between a gene tree and a corresponding species tree can be attributed to evolutionary events such as gene duplication and gene loss. This paper describes a combinatorial model where so-called DTL-scenarios are used to explain the differences between a gene tree and a corresponding species tree taking into account gene duplications, gene losses, and lateral gene transfers (also known as horizontal gene transfers). The reasonable biological constraint that a lateral gene transfer may only occur between contemporary species leads to the notion of acyclic DTL-scenarios. Parsimony methods are introduced by defining appropriate optimization problems. We show that finding most parsimonious acyclic DTL-scenarios is NP-hard. However, by dropping the condition of acyclicity, the problem becomes tractable, and we provide a dynamic programming algorithm as well as a fixed-parameter tractable algorithm for finding most parsimonious DTL-scenarios.

关键词： Trees biology and genetics combinatorial algorithms graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Safe RuleFit: Learning Optimal Sparse Rule Model by Meta Safe Screening

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2023年第2期45卷 2330-2343页

作者： Kato, Hiroki Hanada, Hiroyuki Takeuchi, Ichiro Nagoya Inst Technol Dept Comp Sci Nagoya Aichi 4668555 Japan RIKEN Ctr Adv Intelligence Project Chuo Tokyo 1030027 Japan Nagoya Univ Grad Sch Engn Nagoya Aichi 4648601 Japan

We consider the problem of learning a sparse rule model, a prediction model in the form of a sparse linear combination of rules, where a rule is an indicator function defined over a hyper-rectangle in the input space. Since the number of all possible such rules is extremely large, it has been computationally intractable to select the optimal set of active rules. In this paper, to solve this difficulty for learning the optimal sparse rule model, we propose Safe RuleFit (SRF). Our basic idea is to develop meta safe screening (mSS), which is a non-trivial extension of well-known safe screening (SS) techniques. While SS is used for screening out one feature, mSS can be used for screening out multiple features by exploiting the inclusion-relations of hyper-rectangles in the input space. SRF provides a general framework for fitting sparse rule models for regression and classification, and it can be extended to handle more general sparse regularizations such as group regularization. We demonstrate the advantages of SRF through intensive numerical experiments.

关键词： Predictive models Random forests Dictionaries Analytical models Regression tree analysis Pattern analysis Numerical models Machine learning knowledge representation formalisms and methods convex programming combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

A graph approach to generate all possible regression submodels

引用

COMPUTATIONAL STATISTICS & DATA ANALYSIS 2007年第2期52卷 799-815页

作者： Gatu, Cristian Yanev, Petko L. Kontoghiorghesc, Erricos J. Univ Neuchatel Inst Informat CH-2000 Neuchatel Switzerland INRIA IRISA Rennes France Univ Cyprus Dept Publ Nicosia Cyprus Univ Cyprus Business Adm Nicosia Cyprus Alexandru Ioan Cuza Univ Fac Comp Sci Iasi Romania Paisij Hilendarski Univ Plovdiv Fac Math & Informat BG-4000 Plovdiv Bulgaria Birkbeck Coll Sch Comp Sci & Informat Syst London England

A regression graph to enumerate and evaluate all possible subset regression models is introduced. The graph is a generalization of a regression tree. All the spanning trees of the graph are minimum spanning trees and provide an optimal computational procedure for generating all possible submodels. Each minimum spanning tree has a different structure and characteristics. An adaptation of a branch-and-bound algorithm which computes the best-subset models using the regression graph framework is proposed. Experimental results and comparison with an existing method based on a regression tree are presented and discussed. (C) 2007 Elsevier B.V. All rights reserved.

关键词： graphs regression trees model selection combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

algorithms for square-3PC(.,.)-free berge graphs

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2008年第1期22卷 51-71页

作者： Maffray, Frederic Trotignon, Nicolas Vuskovic, Kristina CNRS Lab GSCOP F-38031 Grenoble France Univ Paris 01 Ctr Econ Sorbonne F-75647 Paris 13 France Univ Leeds Sch Comp Leeds LS2 9JT W Yorkshire England

We consider the class of graphs containing no odd hole, no odd antihole, and no configuration consisting of three paths between two nodes such that any two of the paths induce a hole, and at least two of the paths are of length 2. This class generalizes claw-free Berge graphs and square-free Berge graphs. We give a combinatorial algorithm of complexity O(n(7)) to find a clique of maximum weight in such a graph. We also consider several subgraph-detection problems related to this class.

关键词： recognition algorithm maximum weight clique algorithm combinatorial algorithms perfect graphs star decomposition

来源：评论

学校读者我要写书评

暂无评论

Parallel dynamic programming on clusters of workstations

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2005年第9期16卷 785-798页

作者： Canto, SD de Madrid, AP Bencomo, SD Univ Nacl Educ Distancia Dept Comp Sci & Automat Control Madrid 28040 Spain

The standard DP ( Dynamic Programming) algorithms are limited by the substantial computational demands they put on contemporary serial computers. In this work, the theory behind the solution to serial monadic dynamic programming problems highlights the theory and application of parallel dynamic programming on a general-purpose architecture ( Cluster or Network Of Workstations). A simple and well-known technique, message passing, is considered. Several parallel serial monadic DP algorithms are proposed, based on the parallelization in the state variables and the parallelization in the decision variables. algorithms with no interpolation are also proposed. It is demonstrated how constraints introduce load unbalance which affect scalability and how this problem is inherent to DP.

关键词： parallel dynamic programming constrained optimization combinatorial algorithms networked workstations performance evaluation NOWs

来源：评论

学校读者我要写书评

暂无评论

NP-HARDNESS AND FIXED-PARAMETER TRACTABILITY OF REALIZING DEGREE SEQUENCES WITH DIRECTED ACYCLIC GRAPHS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2015年第4期29卷 1931-1960页

作者： Hartung, Sepp Nichterlein, Andre TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany

In graph realization problems, one is given a degree sequence and the task is to decide whether there is a graph whose vertex degrees match the given sequence. This realization problem is known to be polynomial-time solvable when the graph is directed or undirected. In contrast, we show NP-completeness for the problem of realizing a given sequence of pairs of nonnegative integers (representing in-and outdegrees) with a directed acyclic graph (DAG), answering an open question of Berger and Muller-Hannemann. Furthermore, we classify the problem as fixed-parameter tractable with respect to the parameter "maximum degree." Investigating sparse and dense settings, we show that the problem remains NP-hard even if the realizing DAG (precisely, the underlying undirected graph) can be transformed into a clique (a tree) by adding (deleting) a constant fraction of the arcs. In contrast, if at most k arcs have to be inserted, respectively, removed to obtain a clique or a tree in the underlying undirected graph, then the problem becomes fixed-parameter tractable with respect to k.

关键词： graph realization problems combinatorial algorithms parameterized complexity structural parameterization

来源：评论

学校读者我要写书评

暂无评论

Quadratic Kernelization for Convex Recoloring of Trees

引用

ALGORITHMICA 2011年第2期61卷 362-388页

作者： Bodlaender, Hans L. Fellows, Michael R. Langston, Michael A. Ragan, Mark A. Rosamond, Frances A. Weyer, Mark Univ Utrecht Dept Informat & Comp Sci Utrecht Netherlands Univ Newcastle Parameterized Complex Res Unit Off DVC Res Callaghan NSW 2308 Australia Australian Res Council Ctr Excellence Bioinformat Brisbane Qld Australia Univ Tennessee Dept Comp Sci Knoxville TN 37996 USA Oak Ridge Natl Lab Comp Sci & Math Div Oak Ridge TN 37831 USA Univ Queensland Inst Mol Biosci Brisbane Qld 4072 Australia Humboldt Univ Inst Informat Berlin Germany

The Convex Recoloring (CR) problem measures how far a tree of characters differs from exhibiting a so-called "perfect phylogeny". For an input consisting of a vertex-colored tree T, the problem is to determine whether recoloring at most k vertices can achieve a convex coloring, meaning by this a coloring where each color class induces a subtree. The problem was introduced by Moran and Snir (J. Comput. Syst. Sci. 73:1078-1089, 2007;J. Comput. Syst. Sci. 74:850-869, 2008) who showed that CR is NP-hard, and described a search-tree based FPT algorithm with a running time of O(k(k/log k) (k) n (4)). The Moran and Snir result did not provide any nontrivial kernelization. In this paper, we show that CR has a kernel of size O(k (2)).

关键词： algorithms combinatorial algorithms Fixed parameter tractability Kernelization Convex recoloring Trees Phylogeny

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：