The ADM Seminar typically meets on Thursdays, 3:30-4:30, in Martin M-102.
* denotes special time and/or place
TITLE:
Rank Tolerance Graph Classes
SPEAKER:
Robert E. Jamison
AFFILIATION: Clemson University
ABSTRACT:
The objects of study in this talk arise from a natural extension of
ideas that have grown out of the now classical notion of interval graph.
In an interval graph, each vertex is associated with an interval on the
real line with two vertices adjacent if and only if their associated intervals
intersect. In 1982 Golumbic and others suggested associating "tolerances"
with each interval so that now two vertices are joined if and only
if the length of the intersection of their associated intervals is at least
the minimum of the two tolerances. In 1987 McMorris and others proposed
replacing the min function above by other joint tolerance functions, such
as max or sum, and even by an arbitrary function phi. In the investigation
of phi-tolerance interval graphs, a particular case appeared to be of recurring
interest ---namely, when all the intervals are nested to form a chain under
inclusion. In this case, the length of the intersection is just the
minimum of the two lengths, and only the lengths, and not the actual intervals
play a role in determining adjacency. One can thus think of a phi-tolerance
chain interval graph as arising from the assignment of two numbers t_v
and r_v to each vertex v of the graph. The first of these, t_v, is
just a tolerance at the vertex v as before. The second, r_v, represents
a rank (or size) associated with the vertex v. Then two vertices
v and w are adjacent provided the minimum of their two ranks exceeds their
joint tolerance --- that is, phi(t_v,t_w) \leq
min(r_v,r_w). In this paper we will explore the extension that arises
when the min on the right is also allowed to be replaced by a more general
function rho.
This is joint work with Martin Charles Golumbic of the Caesarea Rothschild Institute of Computer Science, University of Haifa, Israel.
TITLE:
Semigroups of Triples of Points on Hermitian Curves
SPEAKER:
Gretchen L. Matthews
AFFILIATION: Clemson University
ABSTRACT:
Given a curve X over a field k, an object classically studied is the
Weierstrass semigroup of a k-rational point P of X. This semigroup consists
of those nonnegative integers n such that there is a rational function
on X with a pole of order n at P and no other poles. This definition was
generalized by Arbarello, Cornalba, Griffiths, and Harris to the Weierstrass
semigroup of a pair of k-rational points on X. More recently, Ballico and
Kim introduced the notion of the Weierstrass semigroup of an m-tuple of
k-rational points on X. Weierstrass semigroups have proven useful in the
construction of algebraic geometry codes.
In this talk, we restrict our attention to Hermitian curves, that is, curves defined by the equation y^q+y=x^{q+1} over the finite field with q^2 elements. The Weierstrass semigroups of any rational point and of any pair of rational points on this curve are known. We explore Weierstrass semigroups of triples of rational points on Hermitian curves. In particular, we determine the Weierstrass semigroup of any triple of collinear points on such a curve. Using the automorphism group, we determine the maximum number of distinct semigroups that arise as the Weierstrass semigroup of some triple of points on a Hermitian curve.
TITLE:
A New Algorithm for Primality Testing
SPEAKER:
Kevin James
AFFILIATION: Clemson University
ABSTRACT:
Since ancient times mathematicians have been fascinated by questions
involving prime numbers. One of the most fundamental such questions is
that of determining if a given number is prime or composite. The oldest
algorithm for answering this question is the Sieve of Eratosthenes. To
determine if n is a prime the sieve takes time proportional to nlog(log(n)).
This running time is said to be exponential since the input is of size
log(n). (It takes log(n) bits to store n.) Since the time of Eratosthenes
there have been many improvements in the area of primality testing. There
are some algorithms which are quite fast but unfortunately nondeterministic.
The best deterministic algorithm prior to the one being discussed in this
talk is the APR test which has a running time which is subexponential but
still not polynomial. In this talk we will discuss a new primality testing
algorithm which is deterministic and has polynomial running time.
TITLE:
REU in Computational Number Theory and Combinatorics
SPEAKER:
Neil Calkin & Kevin James
AFFILIATION: Clemson University
ABSTRACT:
In this talk, we discuss the NSF Research Experiences for Undergraduates
in Computational Number Theory and Combinatorics held at Clemson during
Summer 2002.
TITLE:
Small Sets of Even Type in Finite Projective Planes of Even Order
SPEAKER:
Jirapha Limbupasiriporn
AFFILIATION: Clemson University
ABSTRACT:
A set of points in a finite projective plane is of even type if every
line of the plane meets it evenly. The incidence vector of such a
set will be in the dual of the binary code of the plane. We consider
here sets of q+t points in planes of even order that are met in 0, 2, or
t 2 points by the lines of the plane. It follows that t divides q.
Korchmaros and Marzzocca gave a construction and a canonical form for such
sets in the desarguesian plane of even order q. They showed that
sets of size q+4 of type (0,2,4) (i.e., met by lines in 0, 2, or 4 points)
always exist in the desarguesian plane of order q=4,8,16.
In this talk, we discuss some of the work of Korchmaros and Marzzocca and then investigate the existence of sets of size q+t of type (0,2,t) for t=4,8 in the desarguesian plane of even order q.
TITLE:
An Examination of Affine Variety Codes with an Improved Minimum Distance
Bound
SPEAKER: Gary Salazar
AFFILIATION: Trinity University
ABSTRACT:
A brief introduction to affine variety codes will be presented.
We will investigate the strengths and weaknesses of the commonly implemented
Feng-Rao bound on minimum distance. We present an alternate bound
which is at least as good as the Feng-Rao bound along with many examples
to illustrate their similarities and differences.
TITLE:
Multivariate polynomial interpolation and decoding of algebraic geometric
codes
SPEAKER: Shuhong
Gao
AFFILIATION: Clemson University
ABSTRACT:
We present a new algorithm for multivariate polynomial interpolation.
It is a natural generalization of Newton's (or Garner's) algorithm for
univariate polynomials, and it computes simultaneously a Newton basis for
the interpolation space and a Grobner basis for the vanishing ideal of
given points. This algorithm is suitable for numerical and symbolic computation.
In particular, we show how it yields an online algorithm for decoding algebraic
geometric codes.
TITLE:
Stochastic Minimum Spanning Trees
SPEAKER:
Kevin Hutson & Doug Shier
AFFILIATION: Furman University
ABSTRACT:
The minimum spanning tree (MST) problem is a classical network optimization
problem in which the nodes of an edge-weighted graph are to be connected
at minimum total cost or weight. Such problems are encountered in a variety
of applications, from the planning of distribution systems and the design
of circuit boards, to the analysis of clustering data.
The standard network model assumes that all edge weight data are known with certainty. In this talk we discuss a stochastic version of the MST problem in which edges assume a finite number of states (with different edge weights) according to a known probability distribution. The problem of determining the resulting distribution of the weight w(T) of a minimum spanning tree T now becomes considerably more difficult.
First we review some standard topics related to spanning trees in graphs (fundamental cutsets and cycles) as well as the classical optimality conditions for the deterministic MST problem. These ideas are then combined to develop stochastically larger and stochastically smaller distributions that bound the unknown distribution of w(T). As a result we are able to generalize some existing approaches in the literature; in the process we obtain approximations to the expected weight E[w(T)] of a stochastic MST. Computational results are also presented to show that for certain classes of problems, we can obtain reasonable approximations to the unknown distribution of w(T) with only a modest computational effort.
TITLE:
Self-Stabilizing Graph Algorithms
SPEAKER: Wayne Goddard
AFFILIATION: Computer Science, Clemson University
ABSTRACT:
A distributed algorithm is designed to run on a computer network where
each processor in the network has only local information and can communicate
directly only with its neighbors. In a distributed graph algorithm,
the nodes are supposed to solve some problem based on the arbitrary topology
of the entire network, even though there is no global coordinator nor global
clock. It is furthermore self-stabilizing if the nodes' memories can start
with arbitrary values and the algorithm
is still guaranteed to work. The talk is designed to be an introduction
to self-stabilizing graph algorithms. We will consider algorithms for problems
such as maximal independent set, spanning trees, domination and colorings.
This includes joint work with S.T. Hedetniemi, D.P. Jacobs and P.K. Srimani.
TITLE:
Multivariate polynomial interpolation and decoding of algebraic geometric
codes II
SPEAKER: Shuhong
Gao
AFFILIATION: Clemson University
ABSTRACT:
We present a new algorithm for multivariate polynomial interpolation.
It is a natural generalization of Newton's (or Garner's) algorithm for
univariate polynomials, and it computes simultaneously a Newton basis for
the interpolation space and a Grobner basis for the vanishing ideal of
given points. This algorithm is suitable for numerical and symbolic computation.
In particular, we show how it yields an online algorithm for decoding algebraic
geometric codes.
TITLE:
Using Genetic Algorithms to Minimize Total Weighted Tardiness on Parallel
Batch-Processing Machine
SPEAKER: Mary
E. Kurz
AFFILIATION: Industrial Engineering, Clemson University
ABSTRACT:
A recent area of interest in machine scheduling focuses on parallel
batch-processing machines. A batch processing machine is one in which
jobs are grouped together into batches and processed simultaneously on
a machine. This occurs in the semi-conductor industry where wafers
must be ?baked? in ovens during a key operation, diffusion. Individual
wafers are grouped into lots, which may be grouped further into batches
that can be loaded into the ovens together. As the production process
for wafers is re-entrant, the wafers revisit this operation several times;
each batch requires on the order of 10 hours of baking per visit.
Due in part to the long processing time, several parallel ovens are often
used. Though the diffusion ovens are not intended to be the bottleneck
tool group, poor utilization of the ovens can induce this tool group to
become the bottleneck in the system. One possible objective when
scheduling these parallel batch processing machines is minimizing the total
weighted tardiness for all jobs, which penalizes jobs for completing after
their assigned due dates in a manner consistent with their relative importances.
The problem of interest is minimizing total weighted tardiness on parallel batch processing machines, where the jobs are not available at the same time. Because this problem has several NP-hard problems as generalizations, we use a particular type of genetic algorithm to provide approximate solutions to this problem. In this seminar, we will discuss methods to decode a chromosome into a problem solution, consisting of an assignment of jobs to batches, batches to machines and the ordering of the batches on these machines.