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

Approximation Algorithms for 3D Orthogonal Knapsack

Journal of Computer Science & Technology 2008年第5期23卷 749-762页

作者： Florian Diedrich Rolf Harren Klaus Jansen Ralf Thle Henning Thomas Institute of Computer Science University of Kiel Max-Planck-Institut für Informatik Campus E1466123 Saarbrücken Germany Department of Computer Science ETH ZurichZurich Switzerland

We study non-overlapping axis-parallel packings of 3D boxes with profits into a dedicated bigger box where rotation is either forbidden or permitted, and we wish to maximize the total profit. Since this optimization problem is NP-hard, we focus on approximation algorithms. We obtain fast and simple algorithms for the non-rotational scenario with approximation ratios 9 ＋ ε and 8 ＋ ε, as well as an algorithm with approximation ratio 7 ＋ ε that uses more sophisticated techniques; these are the smallest approximation ratios known for this problem. Furthermore, we show how the used techniques can be adapted to the case where rotation by 90° either around the z-axis or around all axes is permitted, where we obtain algorithms with approximation ratios 6 ＋ ε and 5 ＋ ε, respectively. Finally our methods yield a 3D generalization of a packability criterion and a strip packing algorithm with absolute approximation ratio 29/4, improving the previously best known result of 45/4.

关键词： approximation algorithm computational and structural complexity geometric configurations

来源：评论

学校读者我要写书评

暂无评论

Nonerasing, counting, and majority over the linear time hierarchy

引用

INFORMATION AND COMPUTATION 2002年第2期174卷 132-142页

作者： Durand, A More, M Univ Paris 12 Dept Informat LACL F-94010 Creteil France Univ Auvergne Dept Informat IUT LLAIC F-63172 Aubiere France

In this paper, we investigate several extensions of the linear time hierarchy (denoted by LTH). We first prove that it is not necessary to erase the oracle tape between two successive oracle calls, thereby lifting a common restriction on LTH machines. We also define a natural counting extension of LTH and show that it corresponds to a robust notion of counting bounded arithmetic predicates. Finally, we show that the computational power of the majority operator is equivalent to that of the exact counting operator in both contexts. (C) 2002 Elsevier Science (USA).

关键词： computational and structural complexity logic in computer science rudimentary relations counting classes

来源：评论

学校读者我要写书评

暂无评论

Splitting NP-complete sets

引用

SIAM JOURNAL ON COMPUTING 2008年第5期37卷 1517-1535页

作者： Glasser, Christian Pavan, A. Selman, Alan L. Zhang, Liyu Univ Wurzburg Lehrstuhl Informat 4 D-97074 Wurzburg Germany Iowa State Univ Dept Comp Sci Ames IA 50010 USA SUNY Buffalo Dept Comp Sci Buffalo NY 14260 USA Univ Texas Brownsville Dept Comp Sci & Informat Syst Brownsville TX 78520 USA

We show that a set is m-autoreducible if and only if it is m-mitotic. This solves a long-standing open question in a surprising way. As a consequence of this unconditional result and recent work by Glaber et al., complete sets for all of the following complexity classes are m-mitotic: NP, coNP, circle plus P, PSPACE, and NEXP, as well as all levels of PH, MODPH, and the Boolean hierarchy over NP. In the cases of NP, PSPACE, NEXP, and PH, this at once answers several well-studied open questions. These results tell us that complete sets share a redundancy that was not known before. In particular, every NP-complete set A splits into two NP-complete sets A(1) and A(2). We disprove the equivalence between autoreducibility and mitoticity for all polynomial-time-bounded reducibilities between 3-tt-reducibility and Turing-reducibility: There exists a sparse set in EXP that is polynomial-time 3-tt-autoreducible, but not weakly polynomial-time T-mitotic. In particular, polynomial-time T-autoreducibility does not imply polynomial-time weak T-mitoticity, which solves an open question by Buhrman and Torenvliet.

关键词： computational and structural complexity NP-complete sets autoreducibility mitoticity

来源：评论

学校读者我要写书评

暂无评论

Extended skew partition problem

引用

DISCRETE MATHEMATICS 2006年第19-20期306卷 2438-2449页

作者： Dantas, Simone de Figueiredo, Celina M. H. Gravier, Sylvain Klein, Sulamita Univ Fed Rio de Janeiro COPPE BR-21941 Rio De Janeiro Brazil Univ Fed Rio de Janeiro Inst Matemat BR-21941 Rio De Janeiro Brazil CNRS Lab Leibniz F-75700 Paris France

A skew partition as defined by Chvatal is a partition of the vertex set of a graph into four nonempty parts A(1), A(2), B-1, B-2 such that there are all possible edges between A(1) and A(2), and no edges between B-1 and B-2. We introduce the concept of (n(1), n(2))-extended skew partition which includes all partitioning problems into n(1) + n(2) nonempty parts A(1),..., An(1), B-1,...,Bn-2, such that there are all possible edges between the A(i) parts, no edges between the B-j parts, i is an element of (1, ..., n(1)}, j is an element of {1,..., n(2)}, which generalizes the skew partition. We present a polynomial-time algorithm for testing whether a graph admits an (n(1), n(2))-extended skew partition. As a tool to complete this task we also develop a generalized 2-SAT algorithm, which by itself may have application to other partition problems. (c) 2006 Elsevier B.V. All rights reserved.

关键词： algorithms and data structures computational and structural complexity skew partition 2-SAT

来源：评论

学校读者我要写书评

暂无评论

On the ultimate complexity of factorials

引用

THEORETICAL COMPUTER SCIENCE 2004年第1-3期326卷 419-429页

作者： Cheng, Q Univ Oklahoma Sch Comp Sci Norman OK 73019 USA

It has long been observed that certain factorization algorithms provide a way to write the product of many different integers succinctly. In this paper, we study the problem of representing the product of all integers from 1 to n (i.e. n!) by straight-line programs. Formally, we say that a sequence of integers a(n) is ultimately f(n)-computable, if there exists a nonzero integer sequence m(n) such that for any n, a(n)m(n) can be computed by a straight-line program (using only additions, subtractions and multiplications) of length at most f(n). Shub and Smale [12] showed that if n! is ultimately hard to compute, then the algebraic version of NP not equal P is true. Assuming a widely believed number theory conjecture concerning smooth numbers in a short interval, a subexponential upper bound (exp(crootlog n log log n)) for the ultimate complexity of n! is proved in this paper, and a randomized subexponential algorithm constructing such a short straight-line program is presented as well. (C) 2004 Elsevier B.V. All rights reserved.

关键词： computational and structural complexity

来源：评论

学校读者我要写书评

暂无评论

The shuffling buffer

引用

INTERNATIONAL JOURNAL OF computational GEOMETRY & APPLICATIONS 2001年第5期11卷 555-572页

作者： Devillers, O Guigue, P INRIA Sophia Antipolis F-06902 Sophia Antipolis France

The complexity of randomized incremental algorithms is analyzed with the assumption of a random order of the input. To guarantee this hypothesis, the n data have to be known in advance in order to be mixed what contradicts with the on-line nature of the algorithm. We present the shuffling buffer technique to introduce sufficient randomness to guarantee an improvement on the worst case complexity by knowing only k data in advance. Typically, an algorithm with O(n(2)) worst-case complexity and O(n) or O(n log n) randomized complexity has an O(n(2)logk/k) complexity for the shuffling buffer. We illustrate this with binary search trees, the number of Delaunay triangles or the number of trapezoids in a trapezoidal map created during an incremental construction.

关键词： computational and structural complexity randomized algorithms on-line algorithms computational geometry

来源：评论

学校读者我要写书评

暂无评论

The Boolean functions computed by random Boolean formulas OR how to grow the right function

引用

RANDOM STRUCTURES & ALGORITHMS 2005年第4期27卷 490-519页

作者： Brodsky, A Pippenger, N Univ Toronto Dept Comp Sci Toronto ON M5S 3G4 Canada Princeton Univ Dept Comp Sci Princeton NJ 08544 USA Univ British Columbia Dept Comp Sci Vancouver BC V5Z 1M9 Canada

We characterize growth processes (probabilistic amplification) by their initial conditions to derive conditions under which results such as Valiant's [J Algorithms 5 (1984), 363-366] hold. We completely characterize growth processes that use linear connectives and generalize Savick 's [Discrete Math 147 (1990), 95-103] analysis to characterize growth processes that use monotone connectives. Additionally, we obtain explicit bounds on the convergence rates of several growth processes, including the growth process studied in Savicky. (c) 2005 Wiley Periodicals, Inc.

关键词： computational and structural complexity growth processes probabilistic amplification random Boolean functions

来源：评论

学校读者我要写书评

暂无评论

Deadlock prevention by acyclic orientations

引用

DISCRETE APPLIED MATHEMATICS 2003年第1期129卷 31-47页

作者： Bermond, JC Di Ianni, M Flammini, M Pérennès, S Univ Nice Sophia antipolis MASCOTTE Project I3S CNRS INRIA F-06902 Sophia Antipolis France Univ Roma Tor Vergata Dipartimento Matemat I-00133 Rome Italy Univ Aquila Dipartimento Informat I-67100 Laquila Italy

Deadlock prevention for routing messages has a central role in communication networks, since it directly influences the correctness of parallel and distributed systems. In this paper, we extend some of the computational results presented in Second Colloquium on structural Information and Communication complexity (SIROCCO), Carleton University Press, 1995, pp. 1-12 on acyclic orientations for the determination of optimal deadlock-free routing schemes. In this context, minimizing the number of buffers needed to prevent deadlocks for a set of communication requests is related to finding an acyclic orientation of the network which minimizes the maximum number of changes of orientations on the dipaths realizing the communication requests. The corresponding value is called the rank of the set of dipaths. We first show that the problem of minimizing the rank is NP-hard if all shortest paths between the couples of nodes wishing to communicate have to be represented and even not approximable if only one shortest path between each couple has to tie represented. This last result holds even if we allow an error which is any sublinear function in the number of couples to be connected. We then improve some of the known lower and upper bounds on the rank of all possible shortest dipaths between any couple of vertices for particular topologies, such as grids and hypercubes, and we find tight results for tori. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： computational and structural complexity parallel algorithms routing and communication in interconnection networks

来源：评论

学校读者我要写书评

暂无评论

Path-Constrained Relaxed Schedulability Analysis

Path-Constrained Relaxed Schedulability Analysis

引用

9th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing

作者： Andrei, Stefan Chakraborty, Samarjit Lamar Univ Dept Comp Sci Beaumont TX 77710 USA Natl Univ Singapore Sch Comp Singapore Singapore 117548 Singapore

ISBN: (纸本)9780769530789

The schedulability analysis problem for many realistic task models is known to be hard (NP or coNP). As this severely restricts the application of these task models, recently there has been a considerable amount of interest in relaxed or approximate notions of schedulability, with the hope that they can be checked more efficiently. In this paper we introduce yet another natural notion Of relaxed schedulability, which is parameterized in terms of the number of paths in a task set. In the model we consider, each task is represented by a directed acyclic graph where the nodes of such a graph are annotated with execution times and deadlines. Our proposed notion of schedulability allows a certain number of paths from each task graph to be non-schedulable. For describing the relaxed schedulability analysis, we formally define a measure called pseudo-K-schedulability, which corresponds to the situation when the task set has exactly K schedulable paths. At one extreme is the classical notion of schedulability analysis, where the problem is NP hard in our and many other task models. At the other extreme of this spectrum we have the trivial notion of schedulability analysis, where no path needs to be schedulable. Problems in between allow for a flexible notion of schedulability. This paper studies the relaxed schedulability because not all paths in a code are executed. This paper shows a fundamental result, namely the membership of the pseudoschedulability problem to the class of #P-hard problems.

关键词： computational and structural complexity scheduling feasibility analysis SAT problem

来源：评论

学校读者我要写书评

暂无评论

Periodicity in Tilings

Periodicity in Tilings

引用

14th International Conference on Developments in Language Theory

作者： Jeandel, Emmanuel Vanier, Pascal Aix Marseille Univ CNRS LIF F-13013 Marseille France

Things and tiling systems are an abstract concept that arise both as a computational model and as a dynamical system. In this paper, we prove an analog of the theorems of Fagin [9] and Selman and Jones [14] by charact... 详细信息

ISBN: (纸本)9783642144547

关键词： computational and structural complexity tilings dynamical systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：