432 Result(s)
-
Chapter
Duality
Let us take a linear program in standard form and try to derive lower bounds on the optimal cost (if it exists).
-
Chapter
Karmarkar’s Algorithm
The appearance in 1984 of Karmarkar’s Algorithm for linear programming generated much excitement in the mathematical community. Also known as the projective transformation method, Karmarkar’s Algorithm was the fi...
-
Chapter
The Simplex Algorithm
Designed in 1947 by G. Dantzig, the Simplex Algorithm was the method of choice used to solve linear programs for decades. Though not a polynomial-time algorithm in the worst case, the Simplex Algorithm is remarka...
-
Chapter
The Ellipsoid Algorithm
The first polynomial-time linear programming algorithm, the Ellipsoid Algorithm was constructed by Soviet mathematicians, L. G. Khachiyan providing the final details in 1979. It is sometimes known as Khachiyan’s ...
-
Chapter
The Basics
Linear Programming is the process of minimizing a linear objective function subject to a finite number of linear equality and inequality constraints. When airlines schedule their crews, when factory managers comp...
-
Chapter
Undecidability and Definability for Parametrized Polynomial Time m-Reducibilities
In the setting of the parametrized reducibilities introduced by the second author and Mike Fellows, we prove a number of decidability and definability results. In particular the undecidability of the relevant m-d...
-
Chapter
Partial Automata and Finitely Generated Congruences: An Extension of Nerode’s Theorem
Let T Σ, be the set of ground terms over a finite ranked alphabet Σ. We define partial automata on T Σ and prove that the finitely generated congruences on T Σ are in one...
-
Chapter
Multiple Agent Autonomous Control A Hybrid Systems Architecture
Hybrid systems are systems in which a digital control automaton receives sampled sense data about the state of a continuous plant and, occasionally, issues a change in the control law for a plant controller. T...
-
Chapter
A Bird’s-Eye View of Twilight Combinatorics
Ordinary combinatorics deals with finite sets of numbers (nonnegative integers) and with finite collections of objects which can be coded by numbers. Many principles of ordinary combinatorics, e.g., the sum ru...
-
Chapter
Intuitionistic L
The goal of this paper is to develop the basics of IL, that is, L under intuitionistic reasoning. The highlights are that (under IZF) IL is a model of V = L and also of IZF. While these are not exciting result...
-
Chapter
Dempster-Shafer Logic Programs and Stable Semantics
Many researchers (e.g. Baldwin [2] and Ishizuka [19]) have observed that the Dempster-Shafer rule of combination, which is at the heart of Dempster-Shafer theory, exhibits non-monotonic behaviour. However, as ...
-
Chapter
Polynomial Time Categoricity and Linear Orderings
Let ℒ = < {ci}i∈S, {Ri}i∈T, {fi}i∈U> be a recursive language, i.e. assume that S, T and U are initial segments of the natural numbers N = (0, 1, 2, ,…), ci is a constant symbol for each i ∈ S, and there are parti...
-
Chapter
On the strength of Fraïssé’s conjecture
We show that Fraïssé’s conjecture that the class of linear orderings is well-quasiordered under embedability is proof theoretically strong. Indeed, even special cases of its restriction to wellorderings implie...
-
Chapter
Embedding Distributive Lattices Preserving 1 below a Nonzero Recursively Enumerable Turing Degree
One way to try to gain an understanding of the various degree-theoretic structures which recursion theorists study is to see what lattices can be embedded into them. Lattice embeddings have been used to show t...
-
Chapter
Index Sets in Recursive Combinatorics
Many theorems in infinite combinatorics have noneffective proofs. Nerode’s recursive mathematics program [10] involves looking at noneffective proofs and seeing if they can be made effective. The framework is ...
-
Chapter
Problem Solving Strategies for the Derivation of Programs
Methods and principles inspired in problem solving strategies for program synthesis are presented. This approach complements the calculational style of programming, emphasizing the consideration of ...
-
Chapter
Recursive Properties of Intervals of Recursive Linear Orders
We investigate the possible recursive properties of intervals, and other suborderings, of recursive linear orders. Let A be a recursive linear order with a co-r.e. interval P. We characterize those (A, P) for whi...
-
Chapter
An integer lattice arising in the model theory of wreath products
While attempting to find methods of some generality for computing a model-theoretic invariant of finite structures (the arity, as defined in §1), we found it useful to compute a number of examples by making us...
-
Chapter
The Combinatorics of the Friedberg-Muchnick Theorem
The complexity of priority proofs in recursion theory has been growing since the first priority proofs in [1] and [7]. Refined versions of classic priority proofs can be found in [11]. To this date, this part ...
-
Chapter
Extracting programs from proofs by an extension of the Curry-Howard process
In this paper we provide a general framework for extracting programs from proofs in the language of first order predicate calculus directly, that is to say, without first going through a transformation into se...
