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

FEASIBLE OFFSET AND OPTIMAL OFFSET FOR GENERAL SINGLE-LAYER CHANNEL ROUTING

SIAM JOURNAL ON DISCRETE MATHEMATICS 1995年第4期8卷 543-554页

作者： GREENBERG, RI SHIH, JD KAOHSIUNG POLYTECH INST DEPT INFORMAT ENGNKAOHSIUNG 84008TAIWAN

This paper provides an efficient method to find all feasible offsets for a given separation in a very large-scale integration (VLSI) channel-routing problem in one layer. The previous literature considers this task only for problems with no single-sided nets. When single-sided nets are included, the worst-case solution time increases from theta(n) to Omega(n(2)), where n is the number of nets. But if the number of columns c is O(n), the problem can be solved in time O(n(1.5) Ign), which improves upon a ''naive'' O(cn) approach. As a corollary of this result, the same time bound suffices to find the optimal offset (the one that minimizes separation). Better running times result when there are no two-sided nets or all single-sided nets are on one side of the channel. This paper also gives improvements upon the naive approach for c not equivalent to O(n), including an algorithm with running time independent of c. An interesting algorithmic aspect of the paper is a connection to discrete convolution.

关键词： VLSI LAYOUT CHANNEL ROUTING SINGLE-LAYER WIRE ROUTING DISCRETE CONVOLUTION combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

Permutation Betting Markets: Singleton Betting with Extra Information 08

Permutation Betting Markets: Singleton Betting with Extra In...

引用

ACM Conference on Electronic Commerce

作者： Ghodsi, Mohammad Mahini, Hamid Mirrokni, Vahab S. Zadimoghaddam, Morteza Sharif Univ Technol Tehran Iran

ISBN: (纸本)9781605581699

We study permutation betting markets, introduced by Chen, Fortnow, Nikolova, and Pennock [3]. 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 [3]), 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. [3]. In order to identify solvable variants of the problem, we propose the singleton betting language which allows traders to bet an arbitrary value oil 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

来源：评论

学校读者我要写书评

暂无评论

Graph Theoretical and Algorithmic Characterizations of Positive Definite Symmetric Quasi-Cartan Matrices

引用

FUNDAMENTA INFORMATICAE 2016年第3期149卷 241-261页

作者： Abarca, M. Rivera, D. Univ Autonoma Estado Morelos Ctr Invest Ciencias Inst Invest Ciencias Basicas & Aplicadas Ave Univ 1001 Cuernavaca Morelos Mexico

A well known constructive proof for the ADE-classification of many mathematical objects, such as positive unit forms and their associated quasi-Cartan matrices, has lead to an Inflations Algorithm. However, this algorithm is not known to run in polynomial time. In this paper we use a so called flation transformation and show how its invariants can be used to characterize the Dynkin types A and D in the language of graph theory. Also, a polynomial-time algorithm for computing the Dynkin type is suggested.

关键词： Positive unit forms Dynkin-type edge-bipartite graphs combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

Upward planarity testing in practice: SAT formulations and comparative study

引用

ACM Journal of Experimental Algorithmics 2015年第1期20卷 1-27页

作者： Chimani, Markus Zeranski, Robert Theoretical Computer Science Osnabrück University Osnabrück 49076 Germany Institute of Computer Science Friedrich-Schiller-University Jena Jena 07743 Germany

A directed acyclic graph (DAG) is upward planar if it can be drawn without any crossings while all edges-when following them in their direction-are drawn with strictly monotonously increasing y-coordinates. Testing whether a graph allows such a drawing is known to be NP-complete, and while the problem is polynomial-time solvable for special graph classes, there is not much known about solving the problem for general graphs in practice. The only attempt so far has been a branch-and-bound algorithm over the graph's triconnectivity structure, which was able to solve small graphs. Furthermore, there are some known FPT algorithms to deal with the problem. In this article, we propose two fundamentally different approaches based on the seemingly novel concept of ordered embeddings and on the concept of a Hanani-Tutte-type characterization of monotone drawings. In both approaches, we model the problem as special SAT instances, that is, logic formulae for which we check satisfiability. Solving these SAT instances allows us to decide upward planarity for arbitrary graphs. For the first time, we give an extensive experimental comparison between virtually all known approaches to the problem. To this end, we also investigate implementation issues and different variants of the known algorithms as well as of our SAT approaches and evaluate all algorithms on real-world as well as on constructed *** also give a detailed performance study of the novel SAT *** show that the SAT formulations outperform all known approaches for graphs with up to 400 edges. For even larger graphs, a modified branch-and-bound algorithm becomes competitive. © Versita Sp. z o.o.

关键词： combinatorial algorithms Experimental evaluation Graph drawing Implementations SAT formulation Upward planarity

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT AUTOMATIC PART NESTING ON IRREGULAR AND INHOMOGENEOUS SURFACES

EFFICIENT AUTOMATIC PART NESTING ON IRREGULAR AND INHOMOGENE...

引用

4TH ANNUAL ACM-SIAM SYMP ON DISCRETE algorithms

作者： HEISTERMANN, J LENGAUER, T German Natl Research Cent for Computer Science (GMD) Germany

ISBN: (纸本)0898713137

The part-nesting problem is the problem of arranging a set of two-dimensional irregular shapes, the parts on a plane irregularly shaped surface, such that no shapes overlap and as much of the surface is covered as possible. This problem occurs in several applications in the textile business. One of the most challenging applications appear in the leather industry. This application is characterized by a high degree of inhomogeneity of the surface as well as the shapes and by severe restrictions on run time. We present an algorithmic method for computer-aided nesting in this context. The algorithm is characterized by selective data reduction, sequential part placement, a topological part fitting process, and a carefully tuned evaluation function for partial placements. Experiments show that the method is competitive with nestings done by man, for relatively nicely behaved part sets and surfaces. Our nesting algorithm has been in industrial use since June 1992.

关键词： combinatorial algorithms GREEDY METHOD 2-DIMENSIONAL PLACEMENT NESTING PROBLEM CUTTING-STOCK PROBLEM TRIM-LOSS PROBLEM

来源：评论

学校读者我要写书评

暂无评论

δγ - Parameterized Matching

引用

15th International Symposium on String Processing and Information Retrieval

作者： Lee, Inbok Mendivelso, Juan Pinzon, Yoan J. Hankuk Aviat Univ Sch Elect Telecommun & Comp Engn Koyang City Kyonggi Do South Korea Univ Nacl Colombia Dept Syst & Ind Engn Res Grp Algorithms & Combinatorics ALGOS UN Bogota Colombia

ISBN: (纸本)9783540890966

This paper defines a new pattern matching problem by combining two paradigms: delta gamma-matching and parameterized matching. The solution is essentially obtained by a combination of bitparallel techniques and a reductions to a graph matching problem. The time complexity of the algorithm is O(nm), assuming text size n, pattern size m and a constant size alphabet.

关键词： combinatorial algorithms delta-matching delta gamma-matching parameterized matching bipartite matching

来源：评论

学校读者我要写书评

暂无评论

Cyber Security Analysis of Power Networks by Hypergraph Cut algorithms

Cyber Security Analysis of Power Networks by Hypergraph Cut ...

引用

2014 IEEE International Conference on Smart Grid Communications (SmartGridComm)

作者： Yamaguchi, Yutaro Ogawa, Anna Takeda, Akiko Iwata, Satoru Univ Tokyo Dept Math Informat Tokyo Japan Keio Univ Dept Adm Engn Yokohama Kanagawa Japan

ISBN: (纸本)9781479949342

This paper presents exact solution methods for analyzing vulnerability of electric power networks to a certain kind of undetectable attacks known as false data injection attacks. We show that the problems of finding the minimum number of measurement points to be attacked undetectably reduce to minimum cut problems on hypergraphs, which admit efficient combinatorial algorithms. Experimental results indicate that our exact solution methods run as fast as the previous methods, most of which provide only approximate solutions. We also present the outline of an algorithm for enumerating all small cuts in a hypergraph, which can be used for finding vulnerable sets of measurement points.

关键词： distribution networks graph theory power system security transmission networks combinatorial algorithms cyber security analysis electric power networks false data injection attacks hypergraph cut algorithms solution methods Conferences Indexes Power measurement Security Smart grids Vectors Power grids electric power network transmission networks Smart grids Power system security Power measurement Graph theory hypergraph Network security

来源：评论

学校读者我要写书评

暂无评论

Exemplar longest common subsequence

Exemplar longest common subsequence

引用

2nd International Workshop on Bioinformatics Research and Applications

作者： Bonizzoni, Paola Della Vedova, Gianluca Dondi, Riccardo Fertin, Guillaume Rizzi, Raffaella Vialette, Stephane Univ Milano Bicocca Dipartimento Informat Sistemist & Comun I-20126 Milan Italy Univ Milano Bicocca Dipartimento Stat I-20126 Milan Italy Univ Bergamo Dipartimento Sci Linguaggi Comun & Culturali I-24129 Bergamo Italy Univ Nantes CNRS LINA FRE 2729 F-44322 Nantes 3 France Univ Paris 11 CNRS UMR 8623 LRI F-91405 Orsay France

In this paper, we investigate the computational and approximation complexity of the Exemplar Longest Common Subsequence (ELCS) of a set of sequences (ELCS problem), a generalization of the Longest Common Subsequence problem, where the input sequences are over the union of two disjoint sets of symbols, a set of mandatory symbols and a set of optional symbols. We show that different versions of the problem are APX-hard even for instances with two sequences. Moreover, we show that the related problem of determining the existence of a feasible solution of the ELCS of two sequences is NP-hard. On the positive side, we first present an efficient algorithm for the ELCS problem over instances of two sequences where each mandatory symbol can appear in total at most three times in the sequences. Furthermore, we present two fixed-parameter algorithms for the ELCS problem over instances of two sequences where the parameter is the number of mandatory symbols.

关键词： longest common subsequence comparative genomics algorithm design and analysis combinatorial algorithms analysis of algorithms problem complexity

来源：评论

学校读者我要写书评

暂无评论

Sufficient Conditions for Tuza's Conjecture on Packing and Covering Triangles 27th

Sufficient Conditions for Tuza's Conjecture on Packing and C...

引用

27th International Workshop on combinatorial algorithms (IWOCA)

作者： Chen, Xujin Diao, Zhuo Hu, Xiaodong Tang, Zhongzheng Chinese Acad Sci AMSS Inst Appl Math Beijing 100190 Peoples R China

ISBN: (纸本)9783319445434;9783319445427

Given a simple graph G = (V, E), a subset of E is called a triangle cover if it intersects each triangle of G. Let v(t)(G) and T-t(G) denote the maximum number of pairwise edge-disjoint triangles in G and the minimum cardinality of a triangle cover of G, respectively. Tuza conjectured in 1981 that T-t(G)/V-t(G) <= 2 holds for every graph G. In this paper, using a hypergraph approach, we design polynomial-time combinatorial algorithms for finding small triangle covers. These algorithms imply new sufficient conditions for Tuza's conjecture on covering and packing triangles. More precisely, suppose that the set TG of triangles covers all edges in G. We show that a triangle cover of G with cardinality at most 2V(t)(G) can be found in polynomial time if one of the following conditions is satisfied: (i) V-t(G)/vertical bar T-G vertical bar >= 1/3, (ii) V-t(G)/vertical bar E vertical bar >= 1/4, (iii) vertical bar E vertical bar/vertical bar T-G vertical bar >= 2.

关键词： Triangle cover Triangle packing Linear 3-uniform hypergraphs combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

Nearly Optimal List Labeling 65

Nearly Optimal List Labeling

引用

65th Symposium on Foundations of Computer Science

作者： Bender, Michael A. Conway, Alex Farach-Colton, Martin Komlos, Hanna Koucky, Michal Kuszmaul, William Saks, Michael SUNY Stony Brook Stony Brook NY 11794 USA RelationalAI Stony Brook NY 11790 USA Cornell Tech New York NY USA NYU New York NY USA Charles Univ Prague Prague Czech Republic Carnegie Mellon Univ Pittsburgh PA USA Rutgers State Univ Piscataway NJ USA

ISBN: (纸本)9798331516758;9798331516741

The list-labeling problem captures the basic task of storing a dynamically changing set of up to n elements in sorted order in an array of size m = (1+ Theta(1))n. The goal is to support insertions and deletions while moving around elements within the array as little as possible. Until recently, the best known upper bound stood at O(log(2) n) amortized cost. This bound, which was first established in 1981, was finally improved two years ago, when a randomized O(log(3/2) n) expected-cost algorithm was discovered. The best randomized lower bound for this problem remains O(log n), and closing this gap is considered to be a major open problem in data structures. In this paper, we present the See-Saw Algorithm, a randomized list-labeling solution that achieves a nearly optimal bound of O(log n polyloglog n) amortized expected cost. This bound is achieved despite at least three lower bounds showing that this type of result is impossible for large classes of solutions.

关键词： Data structures probabilistic algorithms combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：