共查询到20条相似文献,搜索用时 15 毫秒
1.
Programming models for distributed systems often construct a task graph for the program to be executed on a distributed system of processors. While the topology of the task graph can be constructed from the program structure, often the task execution times and data transfer costs between tasks depend on the input data, or more specifically, on the particular problem instance. Though this indicates that the optimal schedule of a task graph cannot be determined until the input data is available, it is possible to estimate theworst caseprocessor requirement for the optimal schedule of a program solely from the topology of its task graph. In this paper, we study the problem of estimating worst case processor requirements for scheduling (with cloning) layered task graphs based on their topology. We show that computing an accurate processor bound for layered graphs is NP hard (even for two layers) and present a polynomial time algorithm which computes an upper bound on the processor requirement. We show that the algorithm provides tight bounds for several common classes of layered task graphs. 相似文献
2.
Hans-Joachim Bockenhauer Juraj Hromkovic Joachim Kneis Joachim Kupke 《Theory of Computing Systems》2007,41(3):431-444
Modern algorithm theory includes numerous techniques to attack hard problems, such as approximation algorithms on the one
hand and parameterized complexity on the other hand. However, it is still uncommon to use these two techniques simultaneously,
which is unfortunate, as there are natural problems that cannot be solved using either technique alone, but rather well if
we combine them. The problem to be studied here is not only natural, but also practical: Consider TSP, generalized as follows.
We impose deadlines on some of the vertices, effectively constraining them to be visited prior to a given point of time.
The resulting problem DlTSP (a special case of the well-known TSP with time windows) inherits its hardness from classical
TSP, which is both well known from practice and renowned to be one of the hardest problems with respect to approximability:
Within polynomial time, not even a polynomial approximation ratio (let alone a constant one) can be achieved (unless P = NP).
We will show that DlTSP is even harder than classical TSP in the following sense. Classical TSP, despite its hardness, admits
good approximation algorithms if restricted to metric (or near-metric) inputs. Not so DlTSP (and hence, neither TSP with
time windows): We will prove that even for metric inputs, no constant approximation ratio can ever be achieved (unless P =
NP). This is where parameterization becomes crucial: By combining methods from
the field of approximation algorithms with ideas from the theory of parameterized complexity, we apply the concept of parameterized
approximation. Thereby, we obtain a 2.5-approximation algorithm for DlTSP with a running time of k! · poly(|G|), where k
denotes the number of deadlines. Furthermore, we prove that there is no
fpt-algorithm with an approximation guarantee of 2-ε for any ε > 0, unless P = NP. Finally, we show that, unlike TSP, DlTSP
becomes much harder when relaxing the triangle inequality. More precisely, for an arbitrary small violation of the triangle
inequality, DlTSP does not admit an fpt-algorithm with approximation guarantee ((1-ε)/2)|V| for any ε > 0, unless P = NP. 相似文献
3.
When donating money to a (say, charitable) cause, it is possible to use the contemplated donation as a bargaining chip to induce other parties interested in the charity to donate more. Such negotiation is usually done in terms of matching offers, where one party promises to pay a certain amount if others pay a certain amount. However, in their current form, matching offers allow for only limited negotiation. For one, it is not immediately clear how multiple parties can make matching offers at the same time without creating circular dependencies. Also, it is not immediately clear how to make a donation conditional on other donations to multiple charities when the donor has different levels of appreciation for the different charities. In both these cases, the limited expressiveness of matching offers causes economic loss: it may happen that an arrangement that all parties (donors as well as charities) would have preferred cannot be expressed in terms of matching offers and will therefore not occur.In this paper, we introduce a bidding language for expressing very general types of matching offers over multiple charities. We formulate the corresponding clearing problem (deciding how much each bidder pays, and how much each charity receives), and show that it cannot be approximated to any ratio in polynomial time unless P = NP, even in very restricted settings. We give a mixed integer program formulation of the clearing problem, and show that for concave bids, the program reduces to a linear program. We then show that the clearing problem for a subclass of concave bids is at least as hard as the decision variant of linear programming. We also consider the case where each charity has a target amount, and bidders? willingness-to-pay functions are concave. Here, we show that the optimal surplus can be approximated to a ratio m, the number of charities, in polynomial time (and no significantly better approximation is possible in polynomial time unless P = NP); no polynomial-time approximation ratio is possible for maximizing the total donated, unless P = NP. Subsequently, we show that the clearing problem is much easier when bids are quasilinear—for maximizing surplus, the problem decomposes across charities, and for maximizing the total donated, a greedy approach is optimal if the bids are concave (although this latter problem is weakly NP-hard when the bids are not concave). For the quasilinear setting, we study the mechanism design question. We show that an ex-post efficient mechanism is impossible even with only one charity and a very restricted class of bids. We also show that there can be benefits to linking the charities from a mechanism design standpoint. Finally, we discuss an experiment in which we used this methodology to collect money for victims of the 2004 Indian Ocean Tsunami. 相似文献
4.
The problem of finding a largest stable matching where preference lists may include ties and unacceptable partners (MAX SMTI) is known to be NP-hard. It cannot be approximated within 33/29 (>1.1379) unless P=NP, and the current best approximation algorithm achieves the ratio of 1.5. MAX SMTI remains NP-hard even when preference lists of one side do not contain ties, and it cannot be approximated within 21/19 (>1.1052) unless P=NP. However, even under this restriction, the best known approximation ratio is still 1.5. In this paper, we improve it to 25/17 (<1.4706). 相似文献
5.
Koki Hamada 《Information Processing Letters》2009,109(18):1036-1841
In the stable marriage problem that allows incomplete preference lists, all stable matchings for a given instance have the same size. However, if we ignore the stability, there can be larger matchings. Biró et al. defined the problem of finding a maximum cardinality matching that contains minimum number of blocking pairs. They proved that this problem is not approximable within some constant δ>1 unless P=NP, even when all preference lists are of length at most 3. In this paper, we improve this constant δ to n1−ε for any ε>0, where n is the number of men in an input. 相似文献
6.
黄金贵 《计算机工程与应用》2009,45(4):4-8
研究多处理机任务调度模型Pm|fix,pj=1|Cmax,即在m个处理机系统中调度n个时间长度都为1的多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行。这类问题在网络并行计算、多播系统及工程规划等领域都有广泛的应用,但早已被证明为NP难问题,而且也不存在常数近似算法。基于团划分方法构造了该问题的多项式时间近似算法,通过模拟实验进行了验证,和最大宽度优先(LWF)算法相比,该算法花费时间较长,近似比性能要好。 相似文献
7.
经典Ramsey数DNA计算模型(Ⅱ):基于位序列的DNA计算模型 总被引:1,自引:1,他引:0
Ramsey数问题是组合数学乃至整个数学中最具魅力的研究领域,也是最困难的数学问题之一.对于经典Ramsey数,至今只有9个Ramsey数得到解决.按照传统的算法,其搜索空间太大,当前的电子计算机无法胜任.研究表明,DNA计算在求解困难的NP-完全问题上优于电子计算机.目前已经建立了众多求解NP-完全问题的DNA计算模型,但未见到用于求解Ramsey数的DNA计算模型.作者建立了一种新颖的DNA计算模型,用于一般经典Ramsey数的求解.全文共分两篇,该文属第二篇,在首篇工作的基础上,建立了所谓的经典Ramsey数位序列DNA计算模型,文中对模型的存储库的建立、解的检测子系统以及运算子系统等问题展开了较为详细地讨论,并给出了使用该模型求解经典Ramsey数详细的方法与步骤. 相似文献
8.
We revisit a well studied linear algebraic problem, computing the rank and determinant of matrices, in order to obtain completeness
results for small complexity classes. In particular, we prove that computing the rank of a class of diagonally dominant matrices
is complete for
L\textsf{L}
. We show that computing the permanent and determinant of tridiagonal matrices over ℤ is in
Gap NC1\textsf {Gap} \textsf {NC}^{1}
and is hard for
NC1\textsf {NC}^{1}
. We also initiate the study of computing the rigidity of a matrix: the number of entries that needs to be changed in order
to bring the rank of a matrix below a given value. We show that some restricted versions of the problem characterize small
complexity classes. We also look at a variant of rigidity where there is a bound on the amount of change allowed. Using ideas
from the linear interval equations literature, we show that this problem is
NP\textsf {NP}
-hard over ℚ and that a certain restricted version is
NP\textsf {NP}
-complete. Restricting the problem further, we obtain variations which can be computed in
PL\textsf {PL}
and are hard for
C=L\textsf {C}_{=}\textsf {L}
. 相似文献
9.
In this paper, we consider a differentiated service inventory problem with multiple demand classes. Given that the demand from each class is stochastic, we apply a continuous review policy with dynamic threshold curves to provide differentiated services to the demand classes in order to optimize both the cost and the service level. The difficult features associated with the problem are the huge search space, the multi-objective problem which requires finding a non-dominated set of solutions and the accuracy in estimating the parameters. To address the above issues, we propose an approach that uses simulation to estimate the performance, nested partitions (NP) method to search for promising solutions, and multi-objective optimal computing budget allocation (MOCBA) algorithm to identify the non-dominated solutions and to efficiently allocate the simulation budget. Some computational experiments are carried out to test the effectiveness and performance of the proposed solution framework. 相似文献
10.
Felix Brandt Markus Brill Felix Fischer Jan Hoffmann 《Theory of Computing Systems》2011,49(1):139-161
We study the computational aspects of weak saddles, an ordinal set-valued solution concept proposed by Shapley. F. Brandt
et al. recently gave a polynomial-time algorithm for computing weak saddles in a subclass of matrix games, and showed that
certain problems associated with weak saddles of bimatrix games are NP-hard. The important question of whether weak saddles
can be found efficiently was left open. We answer this question in the negative by showing that finding weak saddles of bimatrix games
is NP-hard, under polynomial-time Turing reductions. We moreover prove that recognizing weak saddles is coNP-complete, and
that deciding whether a given action is contained in some weak saddle is hard for parallel access to NP and thus not even
in NP unless the polynomial hierarchy collapses. Most of our hardness results are shown to carry over to a natural weakening
of weak saddles. 相似文献
11.
经典Ramsey数DNA计算模型(Ⅰ):位序列计算模型 总被引:2,自引:2,他引:0
Ramsey数问题是组合数学乃至整个数学中最具魅力的研究领域,也是最困难的数学问题之一.对于经典Ramsey数,至今只有9个Ramsey数得到解决.按照传统的算法,其搜索空间太大,当前的电子计算机无法胜任.研究表明,DNA计算在求解困难的NP一完全问题上优于电子计算机.目前已经建立了众多求解NP-完全问题的DNA计算模型,但未见到用于求解Ramsey数的DNA计算模型.作者建立了一种新颖的DNA计算模型,用于一般经典Ramsey数的求解.全文共分两篇,该文属首篇,建立了一种可适用于DNA计算模式的所谓的求解Ramsey数的位序列计算模型,其中的位序列是以图的相邻矩阵下三角阵中行从左到右、列从上到下的排列次序.文中重点对该模型的机理与使用方法进行了分析研究. 相似文献
12.
Fernandez-Baca D. 《IEEE transactions on pattern analysis and machine intelligence》1989,15(11):1427-1436
The author studies the complexity of the problem of allocating modules to processes in a distributed system to minimize total communication and execution costs. He shows that unless P=NP, there can be no polynomial-time ϵ-approximate algorithm for the problem, nor can there exist a local search algorithm that requires polynomial time per iteration and yields an optimum assignment. Both results hold even if the communication graph is planar and bipartite. On the positive side, it is shown that if the communication graph is a partial k -tree or an almost-tree with parameter k , the module allocation problem can be solved in polynomial time 相似文献
13.
In traditional multi-commodity flow theory, the task is to send a
certain amount of each commodity from its start to its target node,
subject to capacity constraints on the edges. However, no
restriction is imposed on the number of paths used for delivering
each commodity; it is thus feasible to spread the flow over a large
number of different paths. Motivated by routing problems arising in
real-life applications, e.g., telecommunication, unsplittable
flows have moved into the focus of research. Here, the demand of
each commodity may not be split but has to be sent along a single
path. In this paper a generalization of this problem is studied. In the
considered flow model, a commodity can be split into a bounded
number of chunks which can then be routed on different paths. In
contrast to classical (splittable) flows and unsplittable flows,
the single-commodity case of this problem is already NP-hard and
even hard to approximate. We present approximation algorithms for
the single- and multi-commodity case and point out strong
connections to unsplittable flows. Moreover, results on the
hardness of approximation are presented. In particular, we show
that some of our approximation results are in fact best possible,
unless P = NP. 相似文献
14.
Ranieri Baraglia Renato Ferrini Pierluigi Ritrovato 《Concurrency and Computation》2005,17(13):1579-1605
In order to minimize the execution time of a parallel application running on a heterogeneously distributed computing system, an appropriate mapping scheme is needed to allocate the application tasks to the processors. The general problem of mapping tasks to machines is a well‐known NP‐hard problem and several heuristics have been proposed to approximate its optimal solution. In this paper we propose a static graph‐based mapping algorithm, called Heterogeneous Multi‐phase Mapping (HMM), which permits suboptimal mapping of a parallel application onto a heterogeneous computing distributed system by using a local search technique together with a tabu search meta‐heuristic. HMM allocates parallel tasks by exploiting the information embedded in the parallelism forms used to implement an application, and considering an affinity parameter, that identifies which machine in the heterogeneous computing system is most suitable to execute a task. We compare HMM with some leading techniques and with an exhaustive mapping algorithm. We also give an example of mapping of two real applications using HMM. Experimental results show that HMM performs well demonstrating the applicability of our approach. Copyright © 2005 John Wiley & Sons, Ltd. 相似文献
15.
We investigate the parameterized computational complexity of the satisfiability problem for modal logic and attempt to pinpoint relevant structural parameters which cause the problem??s combinatorial explosion, beyond the number of propositional variables v. To this end we study the modality depth, a natural measure which has appeared in the literature, and show that, even though modal satisfiability parameterized by v and the modality depth is FPT, the running time??s dependence on the parameters is a tower of exponentials (unless P = NP). To overcome this limitation we propose possible alternative parameters, namely diamond dimension and modal width. We show fixed-parameter tractability results using these measures where the exponential dependence on the parameters is much milder (doubly and singly exponential respectively) than in the case of modality depth thus leading to FPT algorithms for modal satisfiability with much more reasonable running times. We also give lower bound arguments which prove that our algorithms cannot be improved significantly unless the Exponential Time Hypothesis fails. 相似文献
16.
单位处理时间的多处理机任务调度近似算法 总被引:2,自引:1,他引:1
黄金贵 《计算机工程与应用》2008,44(32):26-28
研究多处理机任务调度模型Pm|fix,pj=1|Cmax,即在m个处理机系统中调度n个时间长度都为1的多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行。其更一般的问题是Pm|fix|Cmax,在网络并行计算、多播系统及工程规划等领域都有广泛的应用。该问题早已证明为NP难问题,而且也不存在常数近似算法。基于部分调度和宽度优先原则构造了该问题的一个多项式时间近似算法,并从理论上证明了该算法在最坏情况下的近似比为2m+1,优于已有文献中2m的目前最好结果。 相似文献
17.
Given a set of monomials, the Minimum AND-Circuit problem asks for a circuit that computes these monomials using AND-gates of fan-in two and being of minimum size. We prove that the problem is not polynomial-time approximable within a factor of less than 1.0051 unless \(\mathsf{P}=\mathsf{NP}\), even if the monomials are restricted to be of degree at most three. For the latter case, we devise several efficient approximation algorithms, yielding an approximation ratio of 1.278. For the general problem, we achieve an approximation ratio of d?3/2, where d is the degree of the largest monomial. In addition, we prove that the problem is fixed parameter tractable with the number of monomials as parameter. Finally, we discuss generalizations of the Minimum AND-Circuit problem and relations to addition chains and grammar-based compression. 相似文献
18.
Ruth F. Curtain Mark R. Opmeer 《Mathematics of Control, Signals, and Systems (MCSS)》2011,23(1-3):101-115
We solve the problem of robust stabilization with respect to right-coprime factor perturbations for irrational discrete-time transfer functions. The key condition is that the associated dynamical system and its dual should satisfy a finite-cost condition so that two optimal cost operators exist. We obtain explicit state space formulas for a robustly stabilizing controller in terms of these optimal cost operators and the generating operators of the realization. Along the way we also obtain state space formulas for Bezout factors. 相似文献
19.
We prove that the exact versions of the domatic number problem are complete
for the levels of the boolean hierarchy over NP. The domatic number
problem, which arises in the area of computer networks, is the problem of
partitioning a given graph into a maximum number of disjoint dominating
sets. This number is called the domatic number of the graph. We prove that
the problem of determining whether or not the domatic number of a given
graph is exactly one of k given values is complete for
BH2k(NP), the 2kth level of the boolean hierarchy over NP. In
particular, for k = 1, it is DP-complete to determine whether or not
the domatic number of a given graph equals exactly a given integer. Note
that DP = BH2(NP). We obtain similar results for the exact versions
of generalized dominating set problems and of the conveyor flow shop
problem. Our reductions apply Wagner's conditions sufficient to prove
hardness for the levels of the boolean hierarchy over NP. 相似文献
20.
This note presents the first direct adaptive control structure for nonminimum phase systems where controller parameter identification can be posed as a standard linear parameter estimation problem. In particular, a linear equation error model is formulated for estimating both the controller parameters and some additional auxiliary parameters. The key idea involves insertion of the Bezout polynomial identity into the polynomial design equation which arises in arbitrary pole placement. 相似文献