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

11th IEEE International Conference on Computational Science and Engineering

作者： Moura, Arnaldo V. de Souza, Cid C. Cire, Andre A. Lopes, Tony M. T. Univ Estadual Campinas Inst Comp BR-13081970 Campinas SP Brazil

ISBN: (纸本)9780769531939

Pipeline network systems are considered the major option for transporting petroleum derivatives from refineries to local markets, in view of their many economic and environmental advantages. This article deals with a large real-world pipeline system planning and scheduling problem, in which different products should be transported in a pipeline network in order to supply market demands, while also satisfying hard operational constraints related to product sequencing, flow rates and tank capacities. We propose a novel hybrid approach based on two iterative phases comprised by a heuristic strategy and a Constraint Programming model. The resulting algorithm was tested with real-world instances yielding feasible solutions for all of them.

关键词： constraint satisfaction heuristic methods scheduling combinatorial algorithms decision support

来源：评论

学校读者我要写书评

暂无评论

The number of evolutionary trees

引用

Systematic Zoology 1978年第1期27卷 71-78页

作者： Felsenstein, Joseph

Felsenstein, J. (Department of Genetics, University of Washington, Seattle, Washington 98195) 1978. The number of evolutionary trees. Syst. Zoo/. 27:27-33.-A simple method of counting the number of possible evolutionary trees is presented. The trees are assumed to be rooted, with labelled tips but unlabelled root and unlabelled interior nodes. The method allows multifurcations as well as bifurcations. It makes use of a simple recurrence relation for T(n, m), the number of trees with n labelled tips and m unlabelled interior nodes. A table of the total number of trees is presented up to n = 22. There are 282, 137, 824 different trees having 10 tip species, and over 8.87 × 10²³different trees having 20 tip species. The method is extended to count trees some of whose interior nodes may be labelled. The principal uses of these numbers will be to double-check algorithms and notation systems, and to frighten taxonomists. [Evolutionary trees;cladistic methods;combinatorial algorithms;graphs.]. © 1978 Oxford University Press.

关键词： Evolutionary trees cladistic methods combinatorial algorithms graphs

来源：评论

学校读者我要写书评

暂无评论

Base-Station Positioning for Heterogeneous Systems with Coverage, Capacity and Cost Criteria

Base-Station Positioning for Heterogeneous Systems with Cove...

引用

European Conference On Networks And Communications (EuCNC)

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

ISBN: (纸本)9781467373593

The problem of optimum base station positioning started with the deployment of the first cellular wireless systems, initially 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. The characteristic 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 in this paper has been developed for heterogeneous wireless systems, follows a combinatorial approach and the optimization analysis is based on coverage, capacity and cost criteria. Results demonstrate the flexible performance of the algorithm, as well as the tendency of the solutions towards the deployment of very small cells in order to satisfy the ever increasing capacity requirements.

关键词： Heterogeneous wireless systems Base-station positioning combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

Orientations of 1-Factors and the List Edge Coloring Conjecture 28th

Orientations of 1-Factors and the List Edge Coloring Conject...

引用

28th International Workshop on Combinational algorithms (IWOCA)

作者： Schauz, Uwe Xian Jiaotong Liverpool Univ Suzhou 215123 Peoples R China

ISBN: (纸本)9783319788258;9783319788241

As starting point, we formulate a corollary to the Quantitative combinatorial Nullstellensatz. This corollary does not require the consideration of any coefficients of polynomials, only evaluations of polynomial functions. In certain situations, our corollary is more directly applicable and more ready-to-go than the combinatorial Nullstellensatz itself. It is also of interest from a numerical point of view. We use it to explain a well-known connection between the sign of 1-factorizations (edge colorings) and the List Edge Coloring Conjecture. For efficient calculations and a better understanding of the sign, we then introduce and characterize the sign of single 1-factors. We show that the product over all signs of all the 1-factors in a 1-factorization is the sign of that 1-factorization. Using this result in an algorithm, we attempt to prove the List Edge Coloring Conjecture for all graphs with up to 10 vertices. This leaves us with some exceptional cases that need to be attacked with other methods.

关键词： combinatorial nullstellensatz One-factorizations Edge colorings List edge coloring conjecture combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal resilient sorting and searching in the presence of memory faults

Optimal resilient sorting and searching in the presence of m...

引用

33rd International Colloquium on Automata, Languages and Programming

作者： Finocchi, Irene Grandoni, Fabrizio Italiano, Giuseppe F. Univ Roma La Sapienza Dipartimento Informat I-00198 Rome Italy Univ Roma Tor Vergata Dipartimento Informat Sistemi & Prod I-00133 Rome Italy

ISBN: (纸本)3540359044

We investigate the problem of reliable computation in the presence of faults that may arbitrarily corrupt memory locations. In this framework, we consider the problems of sorting and searching in optimal time while tolerating the largest possible number of memory faults. In particular, we design an O(n log n) time sorting algorithm that can optimally tolerate up to O(root n log n) memory faults. In the special case of integer sorting, we present an algorithm with linear expected running time that can tolerate O(root n) faults. We also present a randomized searching algorithm that can optimally tolerate up to O(log n) memory faults in O(log n) expected time, and an almost optimal deterministic searching algorithm that can tolerate O((log n)(1-epsilon)) faults, for any small positive constant epsilon, in O(log n) worst-case time. All these results improve over previous bounds. (c) 2009 Elsevier B.V. All rights reserved.

关键词： combinatorial algorithms Sorting Searching Memory faults Memory models Computing with unreliable information

来源：评论

学校读者我要写书评

暂无评论

Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations 61

Analysis of Two-variable Recurrence Relations with Applicati...

引用

61st IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Kulik, Ariel Shachnai, Hadas Technion Comp Sci Dept Haifa Israel

ISBN: (纸本)9781728196213

In this paper we introduce randomized branching as a tool for parameterized approximation and develop the mathematical machinery for its analysis. Our algorithms substantially improve the best known running times of parameterized approximation algorithms for Vertex Cover and 3-Hitting Set for a wide range of approximation ratios. The running times of our algorithms are derived from an asymptotic analysis of a broad class of two-variable recurrence relations. Our main theorem gives a simple formula for this asymptotics. The formula can be efficiently calculated by solving a simple numerical optimization problem, and provides the mathematical insight required for the algorithm design. To this end, we show an equivalence between the recurrence and a stochastic process. We analyze this process using the method of types, by introducing an adaptation of Sanov's theorem to our setting. We believe our novel analysis of recurrence relations which is of independent interest is a main contribution of this paper.

关键词： Recurrences and difference equations combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

Das Automatisierte Bildschirmlayout: Ein Kombinatorisches Optimierungsproblem?

引用

Informatik Forschung und Entwicklung 1995年第1期10卷 1-13页

作者： Lüders, Peter Ernst, Rolf Institut für Datenverarbeitungsanlagen Technische Universität Braunschweig Braunschweig D-38 106 Hans-Sommer-Strasse 66 Germany

Die weite Verbreitung der fensterorientierten Benutzerschnittstelle führt zu einem zunehmend intensiven Gebrauch der Fenstertechnik durch komplexe Softwaresysteme etwa in den Bereichen Hypertext oder CAx. Der Benutzer ist einen Gutteil der Zeit damit beschäftigt, die Fenster auf dem Bildschirm zu plazieren und in der Größe anzupassen, damit sich ein jeweils akzeptables Bildschirmlayout ergibt. In diesem Beitrag stellen wir einen Ansatz zur automatisierten Berechnung des Bildschirmlayouts vor. Für verschiedene Layoutprobleme werden einheitliche Optimierungsalgorithmen verwendet, die durch anwendungsspezifische Bewertungsfunktionen gesteuert werden. Hierdurch wird ein hohes Maß an Flexibilität erreicht. Die erzielten Resultate zeigen, daß mit diesem Ansatz das automatisierte Bildschirmlayout in einer interaktiven Umgebung in naher Zukunft möglich ist. Damit könnte die Erstellung komplexer Benutzerschnittstellen erheblich vereinfacht werden. © 1995, Springer-Verlag Berlin Heidelberg. All rights reserved.

关键词： combinatorial algorithms Constrained optimization Graph algorithms Graphalgorithmen Hypertext navigation and maps Key words: Information interfaces and presentation Kombinatorische Algorithmen Mensch-Maschine-Schnittstelle Navigation in Hypertexten Optimierung unter Randbedingungen Schlüsselwörter: Darstellung in Informationssystemen User interfaces Window Manager. Window managers.

来源：评论

学校读者我要写书评

暂无评论

Determinant Maximization via Matroid Intersection algorithms 63

Determinant Maximization via Matroid Intersection Algorithms

引用

63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Brown, Adam Laddha, Aditi Pittu, Madhusudhan Singh, Mohit Tetali, Prasad Georgia Inst Technol Sch Math Atlanta GA 30332 USA Georgia Inst Technol Coll Comp Atlanta GA 30332 USA Carnegie Mellon Univ Sch Comp Sci Pittsburgh PA 15213 USA Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta GA 30332 USA Carnegie Mellon Univ Math Sci Pittsburgh PA 15213 USA

ISBN: (纸本)9781665455190

Determinant maximization problem gives a general framework that models problems arising in as diverse fields as statistics [1], convex geometry [2], fair allocations [3], combinatorics [4], spectral graph theory [5], network design, and random processes [6]. In an instance of a determinant maximization problem, we are given a collection of vectors U = {nu(1),..., nu(n)} subset of R-d, and a goal is to pick a subset S subset of U of given vectors to maximize the determinant of the matrix Sigma(i is an element of S) nu(i)nu(inverted perpendicular)(i). Often, the set S of picked vectors must satisfy additional combinatorial constraints such as cardinality constraint (|S| <= k) or matroid constraint ( S is a basis of a matroid defined on the vectors). In this paper, we give a polynomial-time deterministic algorithm that returns a r(O(r))-approximation for any matroid of rank r <= d. This improves previous results that give e(O(r2))-approximation algorithms relying on e(O(r))-approximate estimation algorithms [4], [7]-[9] for any r <= d. All previous results use convex relaxations and their relationship to stable polynomials and strongly log-concave polynomials or non-convex relaxations for the problem [10]. In contrast, our algorithm builds on combinatorial algorithms for matroid intersection, which iteratively improve any solution by finding an alternating negative cycle in the exchange graph defined by the matroids. While the det(.) function is not linear, we show that taking appropriate linear approximations at each iteration suffice to give the improved approximation algorithm.

关键词： Computations on discrete structures Linear approximation combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

The Label Based Concurrency Control in XML Databases

The Label Based Concurrency Control in XML Databases

引用

8th International Baltic Conference on Databases and Information Systems

作者： Sikorski, Andrzej Poznan Tech Univ IAiI PL-60965 Poznan Poland

ISBN: (纸本)9781586039394

We propose a label based technique for an effective management of structural locks in XML databases. In particular we consider two types of such locks, acquired by transactions on sets of nodes. These are path locks and range locks - the latter understood as some subset of document's nodes defined by a pair of labels, with the sub-tree lock being a special case of range lock. We put forward algorithms for consolidation of shared locks that define a continuous covering, a way of initial processing simplifying and accelerating the lock manager. Two algorithms for the lock manager are trained with the use of XML labels for both the 2PL protocol and the cooperative one. We also point to some interesting ties between the lock management and the shortest path problem. Our motivation is given in the context of the SEDNA native XML DB isolation rules, however, our technique is useful for most of the fine-granular lock protocols.

关键词： concurrency XML combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

A Method for Counting Models on Cubic Boolean Formulas 15th

A Method for Counting Models on Cubic Boolean Formulas

引用

15th Mexican Conference on Pattern Recognition (MCPR)

作者： Lopez-Medina, Marco A. Marcial-Romero, J. Raymundo Hernandez, Jose A. Morales-Hernandez, Sandra Univ Autonoma Estado Mexico Toluca Mexico

ISBN: (纸本)9783031337826;9783031337833

We present an algorithm based on heuristic variable selection for computing the number of models on two conjunctive normal form Boolean formulas whose restricted graph is represented by a cubic graph. For this class of formulas, we show that in most of the cases our proposal improves the time-complexity with respect of the current leader algorithm for counting models on two conjunctive form formulas of this kind.

关键词： #SAT 2SAT Models of Boolean formulas combinatorial algorithms Complexity theory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：