共查询到20条相似文献,搜索用时 15 毫秒
1.
Matrix models are ubiquitous for constraint problems. Many such problems have a matrix of variables $\mathcal{M}$ , with the same constraint C defined by a finite-state automaton $\mathcal{A}$ on each row of $\mathcal{M}$ and a global cardinality constraint $\mathit{gcc}$ on each column of $\mathcal{M}$ . We give two methods for deriving, by double counting, necessary conditions on the cardinality variables of the $\mathit{gcc}$ constraints from the automaton $\mathcal{A}$ . The first method yields linear necessary conditions and simple arithmetic constraints. The second method introduces the cardinality automaton, which abstracts the overall behaviour of all the row automata and can be encoded by a set of linear constraints. We also provide a domain consistency filtering algorithm for the conjunction of lexicographic ordering constraints between adjacent rows of $\mathcal{M}$ and (possibly different) automaton constraints on the rows. We evaluate the impact of our methods in terms of runtime and search effort on a large set of nurse rostering problem instances. 相似文献
2.
Gábor Wiener 《Algorithmica》2013,67(3):315-323
A set system $\mathcal{H} \subseteq2^{[m]}$ is said to be separating if for every pair of distinct elements x,y∈[m] there exists a set $H\in\mathcal{H}$ such that H contains exactly one of them. The search complexity of a separating system $\mathcal{H} \subseteq 2^{[m]}$ is the minimum number of questions of type “x∈H?” (where $H \in\mathcal{H}$ ) needed in the worst case to determine a hidden element x∈[m]. If we receive the answer before asking a new question then we speak of the adaptive complexity, denoted by $\mathrm{c} (\mathcal{H})$ ; if the questions are all fixed beforehand then we speak of the non-adaptive complexity, denoted by $\mathrm{c}_{na} (\mathcal{H})$ . If we are allowed to ask the questions in at most k rounds then we speak of the k-round complexity of $\mathcal{H}$ , denoted by $\mathrm{c}_{k} (\mathcal{H})$ . It is clear that $|\mathcal{H}| \geq\mathrm{c}_{na} (\mathcal{H}) = \mathrm{c}_{1} (\mathcal{H}) \geq\mathrm{c}_{2} (\mathcal{H}) \geq\cdots\geq\mathrm{c}_{m} (\mathcal{H}) = \mathrm{c} (\mathcal{H})$ . A group of problems raised by G.O.H. Katona is to characterize those separating systems for which some of these inequalities are tight. In this paper we are discussing set systems $\mathcal{H}$ with the property $|\mathcal{H}| = \mathrm{c}_{k} (\mathcal{H}) $ for any k≥3. We give a necessary condition for this property by proving a theorem about traces of hypergraphs which also has its own interest. 相似文献
3.
Roberto Bruttomesso Alessandro Cimatti Anders Franzen Alberto Griggio Roberto Sebastiani 《Annals of Mathematics and Artificial Intelligence》2009,55(1-2):63-99
Most state-of-the-art approaches for Satisfiability Modulo Theories $(SMT(\mathcal{T}))$ rely on the integration between a SAT solver and a decision procedure for sets of literals in the background theory $\mathcal{T} (\mathcal{T}{\text {-}}solver)$ . Often $\mathcal{T}$ is the combination $\mathcal{T}_1 \cup \mathcal{T}_2$ of two (or more) simpler theories $(SMT(\mathcal{T}_1 \cup \mathcal{T}_2))$ , s.t. the specific ${\mathcal{T}_i}{\text {-}}solvers$ must be combined. Up to a few years ago, the standard approach to $SMT(\mathcal{T}_1 \cup \mathcal{T}_2)$ was to integrate the SAT solver with one combined $\mathcal{T}_1 \cup \mathcal{T}_2{\text {-}}solver$ , obtained from two distinct ${\mathcal{T}_i}{\text {-}}solvers$ by means of evolutions of Nelson and Oppen’s (NO) combination procedure, in which the ${\mathcal{T}_i}{\text {-}}solvers$ deduce and exchange interface equalities. Nowadays many state-of-the-art SMT solvers use evolutions of a more recent $SMT(\mathcal{T}_1 \cup \mathcal{T}_2)$ procedure called Delayed Theory Combination (DTC), in which each ${\mathcal{T}_i}{\text {-}}solver$ interacts directly and only with the SAT solver, in such a way that part or all of the (possibly very expensive) reasoning effort on interface equalities is delegated to the SAT solver itself. In this paper we present a comparative analysis of DTC vs. NO for $SMT(\mathcal{T}_1 \cup \mathcal{T}_2)$ . On the one hand, we explain the advantages of DTC in exploiting the power of modern SAT solvers to reduce the search. On the other hand, we show that the extra amount of Boolean search required to the SAT solver can be controlled. In fact, we prove two novel theoretical results, for both convex and non-convex theories and for different deduction capabilities of the ${\mathcal{T}_i}{\text {-}}solvers$ , which relate the amount of extra Boolean search required to the SAT solver by DTC with the number of deductions and case-splits required to the ${\mathcal{T}_i}{\text {-}}solvers$ by NO in order to perform the same tasks: (i) under the same hypotheses of deduction capabilities of the ${\mathcal{T}_i}{\text {-}}solvers$ required by NO, DTC causes no extra Boolean search; (ii) using ${\mathcal{T}_i}{\text {-}}solvers$ with limited or no deduction capabilities, the extra Boolean search required can be reduced down to a negligible amount by controlling the quality of the $\mathcal{T}$ -conflict sets returned by the ${\mathcal{T}_i}{\text {-}}solvers$ . 相似文献
4.
5.
Javad Mohammadpour Velni Mona Meisami-Azad Karolos M. Grigoriadis 《Structural and Multidisciplinary Optimization》2009,38(4):377-387
The paper presents a linear matrix inequality (LMI)-based approach for the simultaneous optimal design of output feedback control gains and damping parameters in structural systems with collocated actuators and sensors. The proposed integrated design is based on simplified $\mathcal{H}^2$ and $\mathcal{H}^{\infty}$ norm upper bound calculations for collocated structural systems. Using these upper bound results, the combined design of the damping parameters of the structural system and the output feedback controller to satisfy closed-loop $\mathcal{H}^2$ or $\mathcal{H}^{\infty}$ performance specifications is formulated as an LMI optimization problem with respect to the unknown damping coefficients and feedback gains. Numerical examples motivated from structural and aerospace engineering applications demonstrate the advantages and computational efficiency of the proposed technique for integrated structural and control design. The effectiveness of the proposed integrated design becomes apparent, especially in very large scale structural systems where the use of classical methods for solving Lyapunov and Riccati equations associated with $\mathcal{H}^2$ and $\mathcal{H}^{\infty}$ designs are time-consuming or intractable. 相似文献
6.
Hifsi Altinok Rifat ?olak Yavuz Altin 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2012,16(6):1029-1034
In this study, we introduce the sets $\left[ V,\lambda ,p\right] _{\Updelta }^{{\mathcal{F}}},\left[ C,1,p\right] _{\Updelta }^{{\mathcal{F}}}$ and examine their relations with the classes of $ S_{\lambda }\left( \Updelta ,{\mathcal{F}}\right)$ and $ S_{\mu }\left( \Updelta ,{\mathcal{F}}\right)$ of sequences for the sequences $\left( \lambda _{n}\right)$ and $\left( \mu _{n}\right) , 0<p<\infty $ and difference sequences of fuzzy numbers. 相似文献
7.
Lars Grasedyck Ronald Kriemann Sabine Le Borne 《Computing and Visualization in Science》2008,11(4-6):273-291
Hierarchical ( $\mathcal {H}$ -) matrices provide a data-sparse way to approximate fully populated matrices. The two basic steps in the construction of an $\mathcal {H}$ -matrix are (a) the hierarchical construction of a matrix block partition, and (b) the blockwise approximation of matrix data by low rank matrices. In the context of finite element discretisations of elliptic boundary value problems, $\mathcal {H}$ -matrices can be used for the construction of preconditioners such as approximate $\mathcal {H}$ -LU factors. In this paper, we develop a new black box approach to construct the necessary partition. This new approach is based on the matrix graph of the sparse stiffness matrix and no longer requires geometric data associated with the indices like the standard clustering algorithms. The black box clustering and a subsequent $\mathcal {H}$ -LU factorisation have been implemented in parallel, and we provide numerical results in which the resulting black box $\mathcal {H}$ -LU factorisation is used as a preconditioner in the iterative solution of the discrete (three-dimensional) convection-diffusion equation. 相似文献
8.
V. Rybakov 《Theory of Computing Systems》2008,43(2):254-271
This paper is intended as an attempt to describe logical consequence in branching time logics. We study temporal branching time logics $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ which use the standard operations Until and Next and dual operations Since and Previous (LTL, as standard, uses only Until and Next). Temporal logics $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ are generated by semantics based on Kripke/Hinttikka structures with linear frames of integer numbers $\mathcal {Z}$ with a single node (glued zeros). For $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ , the permissible branching of the node is limited by α (where 1≤α≤ω). We prove that any logic $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ is decidable w.r.t. admissible consecutions (inference rules), i.e. we find an algorithm recognizing consecutions admissible in $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ . As a consequence, it implies that $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ itself is decidable and solves the satisfiability problem. 相似文献
9.
We study certain properties of Rényi entropy functionals $H_\alpha \left( \mathcal{P} \right)$ on the space of probability distributions over ?+. Primarily, continuity and convergence issues are addressed. Some properties are shown to be parallel to those known in the finite alphabet case, while others illustrate a quite different behavior of the Rényi entropy in the infinite case. In particular, it is shown that for any distribution $\mathcal{P}$ and any r ∈ [0,∞] there exists a sequence of distributions $\mathcal{P}_n$ converging to $\mathcal{P}$ with respect to the total variation distance and such that $\mathop {\lim }\limits_{n \to \infty } \mathop {\lim }\limits_{\alpha \to 1 + } H_\alpha \left( {\mathcal{P}_n } \right) = \mathop {\lim }\limits_{\alpha \to 1 + } \mathop {\lim }\limits_{n \to \infty } H_\alpha \left( {\mathcal{P}_n } \right) + r$ . 相似文献
10.
11.
The parallel complexity class $\textsf{NC}$ 1 has many equivalent models such as polynomial size formulae and bounded width branching programs. Caussinus et al. (J. Comput. Syst. Sci. 57:200–212, 1992) considered arithmetizations of two of these classes, $\textsf{\#NC}$ 1 and $\textsf{\#BWBP}$ . We further this study to include arithmetization of other classes. In particular, we show that counting paths in branching programs over visibly pushdown automata is in $\textsf{FLogDCFL}$ , while counting proof-trees in logarithmic width formulae has the same power as $\textsf{\#NC}$ 1. We also consider polynomial-degree restrictions of $\textsf{SC}$ i , denoted $\textsf{sSC}$ i , and show that the Boolean class $\textsf{sSC}$ 1 is sandwiched between $\textsf{NC}$ 1 and $\textsf{L}$ , whereas $\textsf{sSC}$ 0 equals $\textsf{NC}$ 1. On the other hand, the arithmetic class $\textsf{\#sSC}$ 0 contains $\textsf{\#BWBP}$ and is contained in $\textsf{FL}$ , and $\textsf{\#sSC}$ 1 contains $\textsf{\#NC}$ 1 and is in $\textsf{SC}$ 2. We also investigate some closure properties of the newly defined arithmetic classes. 相似文献
12.
Given a range space $(X,\mathcal{R})$ , where $\mathcal{R}\subset2^{X}$ , the hitting set problem is to find a smallest-cardinality subset H?X that intersects each set in $\mathcal{R}$ . We present near-linear-time approximation algorithms for the hitting set problem in the following geometric settings: (i)? $\mathcal{R}$ is a set of planar regions with small union complexity. (ii)? $\mathcal{R}$ is a set of axis-parallel d-dimensional boxes in ? d . In both cases X is either the entire ? d , or a finite set of points in ? d . The approximation factors yielded by the algorithm are small; they are either the same as, or within very small factors off the best factors known to be computable in polynomial time. 相似文献
13.
A C-coloured graph is a graph, that is possibly directed, where the edges are coloured with colours from the set C. Clique-width is a complexity measure for C-coloured graphs, for finite sets C. Rank-width is an equivalent complexity measure for undirected graphs and has good algorithmic and structural properties. It is in particular related to the vertex-minor relation. We discuss some possible extensions of the notion of rank-width to C-coloured graphs. There is not a unique natural notion of rank-width for C-coloured graphs. We define two notions of rank-width for them, both based on a coding of C-coloured graphs by ${\mathbb{F}}^{*}$ -graphs— $\mathbb {F}$ -coloured graphs where each edge has exactly one colour from $\mathbb{F}\setminus \{0\},\ \mathbb{F}$ a field—and named respectively $\mathbb{F}$ -rank-width and $\mathbb {F}$ -bi-rank-width. The two notions are equivalent to clique-width. We then present a notion of vertex-minor for $\mathbb{F}^{*}$ -graphs and prove that $\mathbb{F}^{*}$ -graphs of bounded $\mathbb{F}$ -rank-width are characterised by a list of $\mathbb{F}^{*}$ -graphs to exclude as vertex-minors (this list is finite if $\mathbb{F}$ is finite). An algorithm that decides in time O(n 3) whether an $\mathbb{F}^{*}$ -graph with n vertices has $\mathbb{F}$ -rank-width (resp. $\mathbb{F}$ -bi-rank-width) at most k, for fixed k and fixed finite field $\mathbb{F}$ , is also given. Graph operations to check MSOL-definable properties on $\mathbb{F}^{*}$ -graphs of bounded $\mathbb{F}$ -rank-width (resp. $\mathbb{F}$ -bi-rank-width) are presented. A specialisation of all these notions to graphs without edge colours is presented, which shows that our results generalise the ones in undirected graphs. 相似文献
14.
Roman Kuznets 《Theory of Computing Systems》2010,46(4):636-661
This paper is devoted to the study of self-referential proofs and/or justifications, i.e., valid proofs that prove statements about these same proofs. The goal is to investigate whether such self-referential justifications are present in the reasoning described by standard modal epistemic logics such as $\mathsf{S4}$ . We argue that the modal language by itself is too coarse to capture this concept of self-referentiality and that the language of justification logic can serve as an adequate refinement. We consider well-known modal logics of knowledge/belief and show, using explicit justifications, that $\mathsf{S4}$ , $\mathsf{D4}$ , $\mathsf{K4}$ , and $\mathsf{T}$ with their respective justification counterparts $\mathsf{LP}$ , $\mathsf{JD4}$ , $\mathsf{J4}$ , and $\mathsf{JT}$ describe knowledge that is self-referential in some strong sense. We also demonstrate that self-referentiality can be avoided for $\mathsf{K}$ and $\mathsf{D}$ . In order to prove the former result, we develop a machinery of minimal evidence functions used to effectively build models for justification logics. We observe that the calculus used to construct the minimal functions axiomatizes the reflected fragments of justification logics. We also discuss difficulties that result from an introduction of negative introspection. 相似文献
15.
A Unified Approach to Approximating Partial Covering Problems 总被引:1,自引:0,他引:1
An instance of the generalized partial cover problem consists of a ground set U and a family of subsets ${\mathcal{S}}\subseteq 2^{U}$ . Each element e??U is associated with a profit p(e), whereas each subset $S\in \mathcal{S}$ has a cost c(S). The objective is to find a minimum cost subcollection $\mathcal{S}'\subseteq \mathcal{S}$ such that the combined profit of the elements covered by $\mathcal{S}'$ is at least P, a specified profit bound. In the prize-collecting version of this problem, there is no strict requirement to cover any element; however, if the subsets we pick leave an element e??U uncovered, we incur a penalty of ??(e). The goal is to identify a subcollection $\mathcal{S}'\subseteq \mathcal{S}$ that minimizes the cost of $\mathcal{S}'$ plus the penalties of uncovered elements. Although problem-specific connections between the partial cover and the prize-collecting variants of a given covering problem have been explored and exploited, a more general connection remained open. The main contribution of this paper is to establish a formal relationship between these two variants. As a result, we present a unified framework for approximating problems that can be formulated or interpreted as special cases of generalized partial cover. We demonstrate the applicability of our method on a diverse collection of covering problems, for some of which we obtain the first non-trivial approximability results. 相似文献
16.
The behavior of total quantum correlations (discord) in dimers consisting of dipolar-coupled spins 1/2 are studied. We found that the discord $Q=0$ at absolute zero temperature. As the temperature $T$ increases, the quantum correlations in the system increase at first from zero to its maximum and then decrease to zero according to the asymptotic law $T^{-2}$ . It is also shown that in absence of external magnetic field $B$ , the classical correlations $C$ at $T\rightarrow 0$ are, vice versa, maximal. Our calculations predict that in crystalline gypsum $\hbox {CaSO}_{4}\cdot \hbox {2H}_{2}{\hbox {O}}$ the value of natural $(B=0)$ quantum discord between nuclear spins of hydrogen atoms is maximal at the temperature of 0.644 $\upmu $ K, and for 1,2-dichloroethane $\hbox {H}_{2}$ ClC– $\hbox {CH}_{2}{\hbox {Cl}}$ the discord achieves the largest value at $T=0.517~\upmu $ K. In both cases, the discord equals $Q\approx 0.083$ bit/dimer what is $8.3\,\%$ of its upper limit in two-qubit systems. We estimate also that for gypsum at room temperature $Q\sim 10^{-18}$ bit/dimer, and for 1,2-dichloroethane at $T=90$ K the discord is $Q\sim 10^{-17}$ bit per a dimer. 相似文献
17.
Carmen Chiri?? 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2012,16(6):979-987
In this paper we introduce the polyadic tense $\theta$ -valued $\L$ ukasiewicz–Moisil algebras (=polyadic tense $\hbox{LM}_{\theta}$ -algebras), as a common generalization of polyadic tense Boolean algebras and polyadic $\hbox{LM}_{\theta}$ -algebras. Our main result is a representation theorem for polyadic tense $\hbox{LM}_{\theta}$ -algebras. 相似文献
18.
We relate the exponential complexities 2 s(k)n of $\textsc {$k$-sat}$ and the exponential complexity $2^{s(\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf}))n}$ of $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ (the problem of evaluating quantified formulas of the form $\forall\vec{x} \exists\vec{y} \textsc {F}(\vec {x},\vec{y})$ where F is a 3-cnf in $\vec{x}$ variables and $\vec{y}$ variables) and show that s(∞) (the limit of s(k) as k→∞) is at most $s(\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf}))$ . Therefore, if we assume the Strong Exponential-Time Hypothesis, then there is no algorithm for $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ running in time 2 cn with c<1. On the other hand, a nontrivial exponential-time algorithm for $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ would provide a $\textsc {$k$-sat}$ solver with better exponent than all current algorithms for sufficiently large k. We also show several syntactic restrictions of the evaluation problem $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ have nontrivial algorithms, and provide strong evidence that the hardest cases of $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ must have a mixture of clauses of two types: one universally quantified literal and two existentially quantified literals, or only existentially quantified literals. Moreover, the hardest cases must have at least n?o(n) universally quantified variables, and hence only o(n) existentially quantified variables. Our proofs involve the construction of efficient minimally unsatisfiable $\textsc {$k$-cnf}$ s and the application of the Sparsification lemma. 相似文献
19.
S. S. Li P. Brucker C. T. Ng T. C. E. Cheng N. V. Shakhlevich J. J. Yuan 《Journal of Scheduling》2013,16(4):417-422
The inverse and reverse counterparts of the single-machine scheduling problem $1||L_{\max }$ are studied in [2], in which the complexity classification is provided for various combinations of adjustable parameters (due dates and processing times) and for five different types of norm: $\ell _{1},\ell _{2},\ell _{\infty },\ell _{H}^{\Sigma } $ , and $\ell _{H}^{\max }$ . It appears that the $O(n^{2})$ -time algorithm for the reverse problem with adjustable due dates contains a flaw. In this note, we present the structural properties of the reverse model, establishing a link with the forward scheduling problem with due dates and deadlines. For the four norms $\ell _{1},\ell _{\infty },\ell _{H}^{\Sigma }$ , and $ \ell _{H}^{\max }$ , the complexity results are derived based on the properties of the corresponding forward problems, while the case of the norm $\ell _{2}$ is treated separately. As a by-product, we resolve an open question on the complexity of problem $1||\sum \alpha _{j}T_{j}^{2}$ . 相似文献
20.
The discrete logarithm problem modulo a composite??abbreviate it as DLPC??is the following: given a (possibly) composite integer n??? 1 and elements ${a, b \in \mathbb{Z}_n^*}$ , determine an ${x \in \mathbb{N}}$ satisfying a x ?=?b if one exists. The question whether integer factoring can be reduced in deterministic polynomial time to the DLPC remains open. In this paper we consider the problem ${{\rm DLPC}_\varepsilon}$ obtained by adding in the DLPC the constraint ${x\le (1-\varepsilon)n}$ , where ${\varepsilon}$ is an arbitrary fixed number, ${0 < \varepsilon\le\frac{1}{2}}$ . We prove that factoring n reduces in deterministic subexponential time to the ${{\rm DLPC}_\varepsilon}$ with ${O_\varepsilon((\ln n)^2)}$ queries for moduli less or equal to n. 相似文献