513 research outputs found
Recommended from our members
[Letter from Karen Edmonds to D. Jack Davis, July 13, 1987, with attachments]
No full textA letter from Karen Edmonds to D. Jack Davis dated July 13, 1987, regarding the enclosed "Learning to Look and Create: The SPECTRA Program" brochure and sample lesson
Exponentiality of the exchange algorithm for finding another room-partitioning
No full textLet T be a triangulated surface given by the list of vertex-triples of its triangles, called rooms. A room-partitioning for T is a subset R of the rooms such that each vertex of T is in exactly one room in R. Given a room-partitioning R for T, the exchange algorithm walks from room to room until it finds a second different room-partitioning R′. In fact, this algorithm generalizes the Lemke-Howson algorithm for finding a Nash equilibrium for two-person games. In this paper, we show that the running time of the exchange algorithm is not polynomial relative to the number of rooms, by constructing a sequence of (planar) instances, in which the algorithm walks from room to room an exponential number of times. We also show a similar result for the problem of finding a second perfect matching in Eulerian graphs. © 2012 Elsevier B.V. All rights reserved
On finding another room-partitioning of the vertices
No full textLet T be a triangulated surface given by the list of vertex-triples of its triangles, called rooms. A room-partitioning of T is a subset R of the rooms such that each vertex of T is in exactly one room in R. We prove that if T has a room-partitioning R, then there is another room-partitioning of T which is different from R. The proof is a simple algorithm which walks from room to room, which however we show to be exponential by constructing a sequence of (planar) instances, where the algorithm walks from room to room an exponential number of times relative to the number of rooms in the instance. We unify the above theorem with Nash’s theorem stating that a 2-person game has an equilibrium, by proving a combinatorially simple common generalization
Margaret Edmonds sings Irish and Irish Australian folk songs, c1963
No full textThe Robert Michell Collection consists of Papers relating to the Queensland Folk Federation and folk festivals: correspondence; posters; newspaper clippings; song lyrics; record lists; business correspondence of Queensland Folk Festival; minutes of meetings; miscellaneous folk festival programmes; audio tapes of oral history interviews and performances
Non-Beatles’ perspectives on non-Edmonds graphs
No full textIn 1965, at the height of Beatlemania, Jack Edmonds published his groundbreaking characterization of the perfect matching polytope of a graph G = (V,E), i.e., the convex hull P of the characteristic vectors of the perfect matchings in G. Edmonds described P polyhedrally as the set of nonnegative vectors in ℝE satisfying two families of constraints: \u27saturation\u27 and \u27blossom\u27. Graphs for which the latter constraints are implied by the former are now called non-Edmonds graphs. As it turns out, this graph class interacts interestingly with more familiar classes. For example, bipartite graphs are non-Edmonds, and this assertion is equivalent to the Birkhoff–von Neumann Theorem on doubly-stochastic matrices. This talk will explore several connections of this nature and will be accessible to non-experts
Folder 03: "Tahiti Island of Dreams. A story of disaster and death for challenging a curse."
No full textIncludes author credit "By Ernest Edmonds"Chapter
FACES OF MATCHING POLYHEDRA
No full textLet G = (V, E, ~) be a finite loopless graph, let
b=(bi:ieV) be a vector of positive integers. A
feasible matching is a vector X = (x.: j e: E)
J
of nonnegative
integers such that for each node i of G, the sum of the
over the edges j of G incident with i is no
greater than bi. The matching polyhedron P(G, b) is the
convex hull of the set of feasible matchings.
In Chapter 3 we describe a version of Edmonds' blossom
algorithm which solves the problem of maximizing C • X
over P (G, b) where c =. (c.: j e: E)
J
is an arbitrary real
vector. This algorithm proves a theorem of Edmonds which
gives a set of linear inequalities sufficient to define
P(G, b).
In Chapter 4 we prescribe the unique subset of these
inequalities which are necessary to define P(G, b), that
is, we characterize the facets of P(G, b). We also
characterize the vertices of P(G, b), thus describing the
structure possessed by the members of the minimal set X
of feasible matchings of G such that for any real vector
c = (c.: j e: E), c • x is maximized over P(G, b)
J
member of X.
by a
In Chapter 5 we present a generalization of the blossom
algorithm which solves the problem: maximize c • x over
a face F of P(G, b) for any real vector c = (c.: j e: E).
J
In other words, we find a feasible matching x of G which
satisfies the constraints obtained by replacing an arbitrary
subset of the inequalities which define P(G, b) by equations and which maximizes c • x subject to this
restriction. We also describe an application of this
algorithm to matching problems having a hierarchy of objective
functions, so called ''multi-optimization'' problems.
In Chapter 6 we show how the blossom algorithm can be
combined with relatively simple initialization algorithms
to give an algorithm which solves the following postoptimality
problem. Given that we know a matching 0 x £ P(G, b)
maximizes c · x over P(G, b), we wish to utilize 0
X
which
to
find a feasible matching x' £ P(G, b') which maximizes
c • x over P(G, b'), where b' = (b!: i £ V)
]_
vector of positive integers and
arbitrary real vector.
c=(c.:j£E)
J
is a
is an
In Chapter 7 we describe a computer implementation of
the blossom algorithm described herein
Maynard to James E. Edmonds (12 April 1893)
No full textDiscusses history of Sir James\u27s plantation and the town\u27s history and connection with the Choctaw.https://egrove.olemiss.edu/edmonds/1006/thumbnail.jp
Lloyd Edmonds and other members of his Regiment de Tren squadron
No full textTop row, left to right: Sam Aarons, Henry Weiss, Lloyd Edmonds; Far left by himself: [Veikko Olavi] Lindfors; 2 rows seated, left to right, top row: Steitzer, [Harry] John Day, [Wayland Davis] 'Curley' Hewlett; bottom row: [James Bernard] 'Bunny' Rucker, Morris Sennett, Jack Koble; 3 standing, left to right: Jack Shillman, Irving Portrou, Ard Harris; lying down: Mike Raddock (?). The Regiment de Tren was a transportation unit providing support to the Republican forces
Generative Systems Art: the Work of Ernest Edmonds
No full textIn this book, the author explores the history of pioneering computer art and its contribution to art history by way of examining Ernest Edmonds’ art from the late 1960s to the present day. Edmonds’ inventions of new concepts, tools and forms of art, along with his close involvement with the communities of computer artists, Systems artists and computer technologists, provide the context for discussion of the origins and implications of the relationship between art and technology. Drawing on interviews with Edmonds and primary research in archives of his work, the book offers a new contribution to the history of the development of digital art and places Edmonds’ work in the context of contemporary art history
- …
