共查询到20条相似文献,搜索用时 31 毫秒
1.
Ning Chen 《Journal of Computer and System Sciences》2004,69(4):675-687
We consider complexity issues for a special type of combinatorial auctions, the single-minded auction, where every agent is interested in only one subset of the commodities.First, we present a matching bound on the communication complexity for the single-minded auction under a general communication model. Next, we prove that it is NP-hard to decide whether Walrasian equilibrium exists in a single-minded auction. Finally, we establish a polynomial size duality theorem for the existence of Walrasian equilibrium for the single-minded auction. 相似文献
2.
Computing the duplication history of a tandem repeated region is an important problem in computational biology (Fitch in Genetics
86:623–644, 1977; Jaitly et al. in J. Comput. Syst. Sci. 65:494–507, 2002; Tang et al. in J. Comput. Biol. 9:429–446, 2002). In this paper, we design a polynomial-time approximation scheme (PTAS) for the case where the size of the duplication block
is 1. Our PTAS is faster than the previously best PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002). For example, to achieve a ratio of 1.5, our PTAS takes O(n
5) time while the PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002) takes O(n
11) time. We also design a ratio-6 polynomial-time approximation algorithm for the case where the size of each duplication block
is at most 2. This is the first polynomial-time approximation algorithm with a guaranteed ratio for this case.
Part of work was done during a Z.-Z. Chen visit at City University of Hong Kong. 相似文献
3.
Lucas Champollion 《Journal of Logic, Language and Information》2011,20(3):343-359
An NP-hardness proof for non-local Multicomponent Tree Adjoining Grammar (MCTAG) by Rambow and Satta (1st International Workshop
on Tree Adjoining Grammers 1992), based on Dahlhaus and Warmuth (in J Comput Syst Sci 33:456–472, 1986), is extended to some linguistically relevant restrictions of that formalism. It is found that there are NP-hard grammars
among non-local MCTAGs even if any or all of the following restrictions are imposed: (i) lexicalization: every tree in the
grammar contains a terminal; (ii) dominance links: every tree set contains at most two trees, and in every such tree set,
there is a link between the foot node of one tree and the root node of the other tree, indicating that the former node must
dominate the latter in the derived tree. This is the version of MCTAG proposed in Becker et al. (Proceedings of the 5th conference
of the European chapter of the Association for Computational Linguistics 1991) to account for German long-distance scrambling. This result restricts the field of possible candidates for an extension
of Tree Adjoining Grammar that would be both mildly context-sensitive and linguistically adequate. 相似文献
4.
Gregory Gutin Eun Jung Kim Michael Lampis Valia Mitsou 《Theory of Computing Systems》2011,48(2):402-410
We study the well-known Vertex Cover problem parameterized above and below tight bounds. We show that two of the parameterizations
(both were suggested by Mahajan et al. in J. Comput. Syst. Sci. 75(2):137–153, 2009) are fixed-parameter tractable and two other parameterizations are W[1]-hard (one of them is, in fact, W[2]-hard). 相似文献
5.
Improved Results for a Memory Allocation Problem 总被引:1,自引:0,他引:1
We consider a memory allocation problem. This problem can be modeled as a version of bin packing where items may be split,
but each bin may contain at most two (parts of) items. This problem was recently introduced by Chung et al. (Theory Comput.
Syst. 39(6):829–849, 2006). We give a simple
\frac32\frac{3}{2}
-approximation algorithm for this problem which is in fact an online algorithm. This algorithm also has good performance for
the more general case where each bin may contain at most k parts of items. We show that this general case is strongly NP-hard for any k≥3. Additionally, we design an efficient approximation algorithm, for which the approximation ratio can be made arbitrarily
close to
\frac75\frac{7}{5}
. 相似文献
6.
We present an improved technique for data hiding in polygonal meshes, which is based on the work of Bogomjakov et al. (Comput.
Graph. Forum 27(2):637–642, 2008). Like their method, we use an arrangement on primitives relative to a reference ordering to embed a message. But instead
of directly interpreting the index of a primitive in the reference ordering as the encoded/decoded bits, our method slightly
modifies the mapping so that our modification doubles the chance of encoding an additional bit compared to Bogomjakov et al.’s
(Comput. Graph. Forum 27(2):637–642, 2008). We illustrate the inefficiency in the original mapping of Bogomjakov et al. (Comput. Graph. Forum 27(2):637–642, 2008) with an intuitive representation using a binary tree. 相似文献
7.
Lakshmi Manasa Shankara Narayanan Krishna Chinmay Jain 《Theory of Computing Systems》2011,48(3):648-679
Weighted timed automata (WTA), introduced in Alur et al. (Proceedings of HSCC’01, LNCS, vol. 2034, pp. 49–62, Springer, Berlin,
2001), Behrmann et al. (Proceedings of HSCC’01, LNCS, vol. 2034, pp. 147–161, Springer, Berlin, 2001) are an extension of Alur and Dill (Theor. Comput. Sci. 126(2):183–235, 1994) timed automata, a widely accepted formalism for the modelling and verification of real time systems. Weighted timed automata
extend timed automata by allowing costs on the locations and edges. There has been a lot of interest Bouyer et al. (Inf. Process.
Lett. 98(5):188–194, 2006), Bouyer et al. (Log. Methods Comput. Sci. 4(2):9, 2008), Brihaye et al. (Proceedings of FORMATS/FTRTFT’04, LNCS, vol. 3253, pp. 277–292, Springer, Berlin, 2004), Brihaye et al. (Inf. Comput. 204(3):408–433, 2006) in studying the model checking problem of weighted timed automata. The properties of interest are written using logic weighted
CTL (WCTL), an extension of CTL with costs. It has been shown Bouyer et al. (Log. Methods Comput. Sci. 4(2):9, 2008) that the problem of model checking WTAs with a single clock using WCTL with no external cost variables is decidable, while 3 clocks render the problem undecidable Bouyer et al. (Inf. Process. Lett. 98(5):188–194, 2006). The question of 2 clocks is open. In this paper, we introduce a subclass of weighted timed automata called weighted integer
reset timed automata (WIRTA) and study the model checking problem. We give a clock reduction technique for WIRTA. Given a
WIRTA A\mathcal{A} with n≥1 clocks, we show that a single clock WIRTA A¢\mathcal{A}' preserving the paths and costs of A\mathcal{A} can be obtained. This gives us the decidability of model checking WIRTA with n≥1 clocks and m≥1 costs using WCTL with no external cost variables. We then show that for a restricted version of WCTL with external cost variables, the model checking problem is undecidable for WIRTA with 3 stopwatch costs and 1 clock. Finally, we show that model checking
WTA with 2 clocks and 1 stopwatch cost against WCTL with no external cost variables is undecidable, thereby answering a question that has remained long open. 相似文献
8.
Hans L. Bodlaender Michael R. Fellows Michael A. Langston Mark A. Ragan Frances A. Rosamond Mark Weyer 《Algorithmica》2011,61(2):362-388
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). 相似文献
9.
We present a posteriori-residual analysis for the approximate time-dependent Stokes model Chorin-Temam projection scheme (Chorin
in Math. Comput. 23:341–353, 1969; Temam in Arch. Ration. Mech. Appl. 33:377–385, 1969). Based on the multi-step approach introduced in Bergam et al. (Math. Comput. 74(251):1117–1138, 2004), we derive error estimators, with respect to both time and space approximations, related to diffusive and incompressible
parts of Stokes equations. Using a conforming finite element discretization, we prove the equivalence between error and estimators
under specific conditions. 相似文献
10.
The steel mill slab design problem from the CSPLIB is a combinatorial optimization problem motivated by an application of the steel industry. It has been widely studied in
the constraint programming community. Several methods were proposed to solve this problem. A steel mill slab library was created
which contains 380 instances. A closely related binpacking problem called the multiple knapsack problem with color constraints,
originated from the same industrial problem, was discussed in the integer programming community. In particular, a simple integer
program for this problem has been given by Forrest et al. (INFORMS J Comput 18:129–134, 2006). The aim of this paper is to bring these different studies together. Moreover, we adapt the model of Forrest et al. (INFORMS
J Comput 18:129–134, 2006) for the steel mill slab design problem. Using this model and a state-of-the-art integer program solver all instances of the steel mill slab library can be solved efficiently to optimality. We improved, thereby, the solution values
of 76 instances compared to previous results (Schaus et al., Constraints 16:125–147, 2010). Finally, we consider a recently introduced variant of the steel mill slab design problem, where within all solutions which
minimize the leftover one is interested in a solution which requires a minimum number of slabs. For that variant we introduce
two approaches and solve all instances of the steel mill slab library with this slightly changed objective function to optimality. 相似文献
11.
The weighted essentially non-oscillatory (WENO) methods are a popular high-order spatial discretization for hyperbolic partial
differential equations. Recently Henrick et al. (J. Comput. Phys. 207:542–567, 2005) noted that the fifth-order WENO method by Jiang and Shu (J. Comput. Phys. 126:202–228, 1996) is only third-order accurate near critical points of the smooth regions in general. Using a simple mapping function to the
original weights in Jiang and Shu (J. Comput. Phys. 126:202–228, 1996), Henrick et al. developed a mapped WENO method to achieve the optimal order of accuracy near critical points. In this paper
we study the mapped WENO scheme and find that, when it is used for solving the problems with discontinuities, the mapping
function in Henrick et al. (J. Comput. Phys. 207:542–567, 2005) may amplify the effect from the non-smooth stencils and thus cause a potential loss of accuracy near discontinuities. This
effect may be difficult to be observed for the fifth-order WENO method unless a long time simulation is desired. However,
if the mapping function is applied to seventh-order WENO methods (Balsara and Shu in J. Comput. Phys. 160:405–452, 2000), the error can increase much faster so that it can be observed with a moderate output time. In this paper a new mapping
function is proposed to overcome this potential loss of accuracy. 相似文献
12.
We study a family of problems, called Maximum Solution (Max Sol), where the objective is to maximise a linear goal function over the feasible integer assignments to a set of variables subject
to a set of constraints. When the domain is Boolean (i.e. restricted to {0,1}), the maximum solution problem is identical
to the well-studied Max Ones problem, and the complexity and approximability is completely understood for all restrictions on the underlying constraints.
We continue this line of research by considering the Max Sol problem for relations defined by regular signed logic over finite subsets of the natural numbers; the complexity of
the corresponding decision problem has recently been classified by Creignou et al. (Theory Comput. Syst. 42(2):239–255, 2008). We give sufficient conditions for when such problems are polynomial-time solvable and we prove that they are APX-hard otherwise. Similar dichotomies are also obtained for variants of the Max Sol problem. 相似文献
13.
In this paper we provide the full spectral decomposition of the Multi-Class Lighthill Whitham Richards (MCLWR) traffic models
described in (Wong et al. in Transp. Res. Part A 36:827–841, 2002; Benzoni-Gavage and Colombo in Eur. J. Appl. Math. 14:587–612, 2003). Even though the eigenvalues of these models can only be found numerically, the knowledge of the spectral structure allows
the use of characteristic-based High Resolution Shock Capturing (HRSC) schemes. We compare the characteristic-based approach
to the component-wise schemes used in (Zhang et al. in J. Comput. Phys. 191:639–659, 2003), and propose two strategies to minimize the oscillatory behavior that can be observed when using the component-wise approach. 相似文献
14.
We study a crossing minimization problem of drawing a bipartite graph with a radial drawing of two orbits. Radial drawings are one of well-known drawing conventions in social network analysis and visualization, in
particular, displaying centrality indices of actors (Wasserman and Faust, Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge,
1994). The main problem in this paper is called the one-sided radial crossing minimization, if the positions of vertices in the outer orbit are fixed. The problem is known to be NP-hard (Bachmaier, IEEE Trans. Vis.
Comput. Graph. 13, 583–594, 2007), and a number of heuristics are available (Bachmaier, IEEE Trans. Vis. Comput. Graph. 13, 583–594, 2007). However, there is no approximation algorithm for the crossing minimization problem in radial drawings. We present the first polynomial time constant-factor approximation algorithm for the one-sided radial crossing minimization problem. 相似文献
15.
Amit Kumar Pushpinder Singh Parmpreet Kaur Amarpreet Kaur 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2011,15(7):1373-1381
Ranking of fuzzy numbers play an important role in decision making, optimization, forecasting etc. Fuzzy numbers must be ranked
before an action is taken by a decision maker. In this paper, with the help of several counter examples it is proved that
ranking method proposed by Chen and Chen (Expert Syst Appl 36:6833–6842, 2009) is incorrect. The main aim of this paper is to propose a new approach for the ranking of L–R type generalized fuzzy numbers. The proposed ranking approach is based on rank and mode so it is named as RM approach. The
main advantage of the proposed approach is that it provides the correct ordering of generalized and normal fuzzy numbers
and it is very simple and easy to apply in the real life problems. It is shown that proposed ranking function satisfies all
the reasonable properties of fuzzy quantities proposed by Wang and Kerre (Fuzzy Sets Syst 118:375–385, 2001). 相似文献
16.
Borodin et al. (Algorithmica 37(4):295–326, 2003) gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin (Algorithmica 40(4):271–291,
2004) extended their work to facility location and set cover problems. We generalize their model to include other optimization
problems, and apply the generalized framework to graph problems. Our goal is to define an abstract model that captures the
intrinsic power and limitations of greedy algorithms for various graph optimization problems, as Borodin et al. (Algorithmica
37(4):295–326, 2003) did for scheduling. We prove bounds on the approximation ratio achievable by such algorithms for basic graph problems such
as shortest path, weighted vertex cover, Steiner tree, and independent set. For example, we show that, for the shortest path
problem, no algorithm in the FIXED priority model can achieve any approximation ratio (even one dependent on the graph size),
but the well-known Dijkstra’s algorithm is an optimal ADAPTIVE priority algorithm. We also prove that the approximation ratio
for weighted vertex cover achievable by ADAPTIVE priority algorithms is exactly 2. Here, a new lower bound matches the known
upper bounds (Johnson in J. Comput. Syst. Sci. 9(3):256–278, 1974). We give a number of other lower bounds for priority algorithms, as well as a new approximation algorithm for minimum Steiner
tree problem with weights in the interval [1,2].
S. Davis’ research supported by NSF grants CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by
the NSF.
R. Impagliazzo’s research supported by NSF grant CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed
by the NSF. Some work done while at the Institute for Advanced Study, supported by the State of New Jersey. 相似文献
17.
An earlier time for inserting and/or accelerating tasks 总被引:1,自引:0,他引:1
Qian Guangming 《Real-Time Systems》2009,41(3):181-194
In a periodic real-time system scheduled by the EDF (Earliest Deadline First) algorithm (Liu and Layland, J. ACM 20(1), 40–61,
1973; Barauh, Proc. of the 27th IEEE International Real-Time Systems Symposium, 379–387, 2006; Buttazzo, J. Real-Time Syst. 29(1), 5–26, 2005), when new tasks have to be inserted into the system at run-time and/or current tasks request to increase their rates in
response to internal or external events, the new sum of the utilizations after the insertion and/or acceleration should be
limited, otherwise, one or more current tasks should usually be compressed (their periods being prolonged) in order to avoid
overload. Buttazzo offered a time from which on this kind of adjustment can be done without causing any deadline miss in the
system (Buttazzo et al., IEEE Trans. Comput. 51(3), 289–302, 2002). It is, however, not early enough. In this paper, an earlier time is given and formally proved.
相似文献
Qian GuangmingEmail: |
18.
Ontology-driven coordination model for multiagent-based mobile workforce brokering systems 总被引:1,自引:1,他引:0
Coordination has been recognized by many researchers as the most important feature of multi-agent systems. Coordination is
defined as managing interdependencies amongst activities (Malone and Crowston in ACM Comput. Surv. 26(1):87–119, 1994). The traditional approach of implementing a coordination mechanism is to hard-wire it into a coordination system at design
time. However, in dynamic and open environments, many attributes of the system cannot be accurately identified at the design
time. Therefore, dynamic coordination, capable of coordinating activities at run-time, has emerged. On the other hand, a successful
dynamic coordination model for multi-agent systems requires knowledge sharing as well as common vocabulary. Therefore, an
ontological approach is an appropriate way in proposing dynamic coordination models for multi-agent systems. In this paper,
an Ontology-Driven Dynamic Coordination Model (O-DC) for Multiagent-Based Mobile Workforce Brokering Systems (MWBS) (Mousavi
et al. in Int. J. Comput. Sci. 6:(5):557–565, 2010; Mousavi et al. in Proceedings of 4th IEEE international symposium on information technology, ITSim’10, Kuala Lumpur, Malaysia,
15–17 June 2010, vol. 3, pp. 1416–1421, 2010; Mousavi and Nordin in Proceedings of the IEEE international conference on electrical engineering and informatics, Bandung,
Indonesia, 17–19 June 2007, pp. 294–297, 2007) is proposed and formulated. Subsequently, the applicability of O-DC is examined via simulation based on a real-world scenario. 相似文献
19.
Susanne Albers 《Algorithmica》2010,58(2):461-477
We study web caching with request reordering. The goal is to maintain a cache of web documents so that a sequence of requests
can be served at low cost. To improve cache hit rates, a limited reordering of requests is allowed. Feder et al. (Proceedings
of the 13th ACM–SIAM Symposium on Discrete Algorithms, pp. 104–105, 2002), who recently introduced this problem, considered caches of size 1, i.e. a cache can store one document. They presented
an offline algorithm based on dynamic programming as well as online algorithms that achieve constant factor competitive ratios.
For arbitrary cache sizes, Feder et al. (Theor. Comput. Sci. 324:201–218, 2004) gave online strategies that have nearly optimal competitive ratios in several cost models. 相似文献
20.
Predicting air damping is crucial in the design of high Q microelectromechanical systems. In the past, air damping of rigid microbeam in free space at molecular regime is usually
estimated using the free molecular model proposed by Christian (Vacuum 16:175–178, 1966), air damping of flexible microbeam is estimated using the model proposed by Blom (J Vac Sci Technol B 10:19–26, 1992). The relation between the two models is Q
Blom = 3Q
Christian. In this paper, a general proof is presented that shows the Christian’s model is valid for the air damping of flexible microbeam
in free space at molecular regime. By comparing with the experimental results available in the literatures (Blom et al. in
J Vac Sci Technol B 10:19–26, 1992; Yasumura et al. in J Micromech Syst 9:117–125, 2000), we conclude that the Christian’s model is the best choice in predicting the air damping of flexible microbeam in free space
at the molecular regime. 相似文献