Search results for " Optimization"
showing 10 items of 2367 documents
Adjacent vertices can be hard to find by quantum walks
2018
Quantum walks have been useful for designing quantum algorithms that outperform their classical versions for a variety of search problems. Most of the papers, however, consider a search space containing a single marked element. We show that if the search space contains more than one marked element, their placement may drastically affect the performance of the search. More specifically, we study search by quantum walks on general graphs and show a wide class of configurations of marked vertices, for which search by quantum walk needs Ω(N) steps, that is, it has no speed-up over the classical exhaustive search. The demonstrated configurations occur for certain placements of two or more adjace…
Aggregation of Risk Level Assessments Based on Fuzzy Equivalence Relation
2017
The paper deals with the problem of aggregation of risk level assessments. We describe the technique of a risk level evaluation taking into account values of the risk level obtained for objects which are in some sense equivalent. For this purpose we propose to use the construction of a general aggregation operator based on the corresponding fuzzy equivalence relation. Numerical example of the investment risk level aggregation using an equivalence relation obtained on the basis of different macroeconomic factors for countries of one region is considered.
Exact, efficient, and complete arrangement computation for cubic curves
2006
AbstractThe Bentley–Ottmann sweep-line method can compute the arrangement of planar curves, provided a number of geometric primitives operating on the curves are available. We discuss the reduction of the primitives to the analysis of curves and curve pairs, and describe efficient realizations of these analyses for planar algebraic curves of degree three or less. We obtain a complete, exact, and efficient algorithm for computing arrangements of cubic curves. Special cases of cubic curves are conics as well as implicitized cubic splines and Bézier curves.The algorithm is complete in that it handles all possible degeneracies such as tangential intersections and singularities. It is exact in t…
Witness computation for solving geometric constraint systems
2014
International audience; In geometric constraint solving, the constraints are represented with an equation system F(U, X) = 0, where X denotes the unknowns and U denotes a set of parameters. The target solution for X is noted XT. A witness is a couple (U_W, X_W) such that F(U_W, X_W) = 0. The witness is not the target solution, but they share the same combinatorial features, even when the witness and the target lie on two distinct connected components of the solution set of F(U, X) = 0. Thus a witness enables the qualitative study of the system: the detection of over- and under-constrained systems, the decomposition into irreducible subsystems, the computation of subsystems boundaries. This …
General duality in vector optimization
1993
Vector minimization of a relation F valued in an ordered vector space under a constraint A consists in finding x 0 ∊ A w,0 ∊ Fx$0 such that w,0 is minimal in FA. To a family of vector minimization problemsminimize , one associates a Lagrange relation where ξ belongs to an arbitrary class Ξ of mappings, the main purpose being to recover solutions of the original problem from the vector minimization of the Lagrange relation for an appropriate ξ. This ξ turns out to be a solution of a dual vector maximization problem. Characterizations of exact and approximate duality in terms of vector (generalized with respect to Ξ) convexity and subdifferentiability are given. They extend the theory existin…
Coupled fixed point, F-invariant set and fixed point of N-order
2010
In this paper, we establish some new coupled fixed point theorems in complete metric spaces, using a new concept of $F$-invariant set. We introduce the notion of fixed point of $N$-order as natural extension of that of coupled fixed point. As applications, we discuss and adapt the presented results to the setting of partially ordered cone metric spaces. The presented results extend and complement some known existence results from the literature.
Logical definability of NP-optimisation problems with monadic auxiliary predicates
1993
Given a first-order formula ϕ with predicate symbols e1...el, so,...,sr, an NP-optimisation problem on -structures can be defined as follows: for every -structure G, a sequence of relations on G is a feasible solution iff satisfies ϕ, and the value of such a solution is defined to be ¦S0¦. In a strong sense, every polynomially bounded NP-optimisation problem has such a representation, however, it is shown here that this is no longer true if the predicates s1, ...,sr are restricted to be monadic. The result is proved by an Ehrenfeucht-Fraisse game and remains true in several more general situations.
On the hardness of optimization in power-law graphs
2008
Our motivation for this work is the remarkable discovery that many large-scale real-world graphs ranging from Internet and World Wide Web to social and biological networks appear to exhibit a power-law distribution: the number of nodes y"i of a given degree i is proportional to i^-^@b where @b>0 is a constant that depends on the application domain. There is practical evidence that combinatorial optimization in power-law graphs is easier than in general graphs, prompting the basic theoretical question: Is combinatorial optimization in power-law graphs easy? Does the answer depend on the power-law exponent @b? Our main result is the proof that many classical NP-hard graph-theoretic optimizati…
Balls into non-uniform bins
2014
Balls-into-bins games for uniform bins are widely used to model randomized load balancing strategies. Recently, balls-into-bins games have been analysed under the assumption that the selection probabilities for bins are not uniformly distributed. These new models are motivated by properties of many peer-to-peer (P2P) networks, which are not able to perfectly balance the load over the bins. While previous evaluations try to find strategies for uniform bins under non-uniform bin selection probabilities, this paper investigates heterogeneous bins, where the "capacities" of the bins might differ significantly. We show that heterogeneous environments can even help to distribute the load more eve…
Hoffman's Error Bound, Local Controllability, and Sensitivity Analysis
2000
Our aim is to present sufficient conditions ensuring Hoffman's error bound for lower semicontinuous nonconvex inequality systems and to analyze its impact on the local controllability, implicit function theorem for (non-Lipschitz) multivalued mappings, generalized equations (variational inequalities), and sensitivity analysis and on other problems like Lipschitzian properties of polyhedral multivalued mappings as well as weak sharp minima or linear conditioning. We show how the information about our sufficient conditions can be used to provide a computable constant such that Hoffman's error bound holds. We also show that this error bound is nothing but the classical Farkas lemma for linear …