HDTenEightyP/NetNews huggingface dataset:
From: jos@and.nl (Jos Horsmeier)
Newsgroups: comp.theory
Subject: Re: On-line algorithms
Date: 11 Apr 92 14:59:47 GMT
Organization: AND Software BV Rotterdam

In article <1992Apr10.163024.16065@watson.ibm.com> mittle@watson.ibm.com (Josh Mittleman) writes:
|In article <1992Apr10.151344.559@watdragon.waterloo.edu>,
|wlfong@logos.waterloo.edu (Philip W. L. Fong) writes:
|> Does anyone know what on-line algorithm is?  And, any reference for this?
|
|An on-line algorithm is one which must process its data element-by-element
|in the order received, without looking ahead.  Thus, an on-line sort
|algorithm would have to maintain a sorted list of all the elements received
|so far, and update it as each new element was provided.  

I partly agree on your first sentence, but like to add: a fixed amount of
look-ahead is allowed (say k data items, where k has nothing to do with 
the total amount of data received.) I must disagree on the second
sentence: an online alogrithm has to start spitting out its output after
a finite amount of steps. In your example, the algorithm isn't capable
of producing its output, not after having read *all* of its input. Your
example is one of an algorithm that's `on the end of the line', not `on-line'.
Maybe a better example might be an LZW compression algorithm or most of the
Un*x ordinary filter programs. If your definition would've been valid, all
algorithms which process their input just once, are on-line algorithms ...

kind regards,

Jos aka jos@and.nl
From: floreen@cs.Helsinki.FI (Patrik Floreen)
Newsgroups: comp.theory
Subject: EQUAL SUBSET SUMS
Summary: NP-completeness of EQUAL SUBSET SUMS ?
Keywords: NP-completeness
Date: 8 Apr 92 14:27:27 GMT
Organization: University of Helsinki, Department of Computer Science

I have been struggling with the following problem that I suspect
to be NP-complete, but I have not been able to prove it:

  EQUAL SUBSET SUMS
  Given: a set of integers S = {a1,...,an}
  Question: are there two nonempty disjoint subsets of S with equal sums?

I would very much appreciate suggestions on how to prove the
(possible) NP-completeness. This problem is closely related to 
PARTITION, where the union of the subsets is the whole S, but I 
have not been able to invent a reduction from PARTITION or
any other problem in Garey & Johnson.

Thanks,

Patrik Floreen
University of Helsinki
Department of Computer Science
From: lgardner@mac.cc.macalstr.edu
Newsgroups: comp.theory
Subject: Re: Integer Linear Programming Package
Date: 9 Apr 92 03:12:48 GMT
Article-I.D.: mac.1992Apr8.211248.2403
Followup-To: comp.theory
Organization: Macalester College

In article <6569@lee.SEAS.UCLA.EDU>, swamy@edison.seas.ucla.edu (Shobana Swamy) writes:
> We are using a public domain Integer Linear Programming package for retiming
> synchronous circuits.  The package is called Minit(for Minimum Iterations).
> 
> The code was originally in Algol 60 and was published in Collected
> Algorithms from CACM (alg #333) by Rudolfo C. Salazar and Subrata
> K. Sen in 1968 under the title MINIT (MINimum ITerations) algorithm
> for Linear Programming.
> It was directly translated into C by Badri Lokanathan, Dept. of EE,
> University of Rochester.
> 
> We are using it on a Sun Sparc2, with about 350M swap space and it runs 
> out of memory at about 800 variables, 8000 constraints.
> 
> Does anybody on the net have a pointer to other public domain integer
> programming packages we could access, with better memory performance ?
> 
> Please reply by e-mail.
> 
> Thanks a lot,
> 
> Shobana.
Newsgroups: comp.theory
From: hhassler@iaik.tu-graz.ac.at (Hannes Hassler)
Subject: Re: EQUAL SUBSET SUMS
Keywords: NP-completeness
Organization: Institut fuer Angewandte Informationsverarbeitung, TU Graz
Date: Thu, 9 Apr 92 09:03:23 GMT

Some days ago, Patrik Floreen asked:

> I have been struggling with the following problem that I suspect
> to be NP-complete, but I have not been able to prove it:
>
>   EQUAL SUBSET SUMS
>   Given: a set of integers S = {a1,...,an}
>   Question: are there two nonempty disjoint subsets of S with equal sums?
>
> Patrik Floreen
> University of Helsinki
> Department of Computer Science

This problem has been recently investigated by G.J.Woeginger and 
Z.L.Yu.  The problem indeed is NP-complete, the reduction is from
EVEN-ODD-PARTITION.  The paper is called "On the Equal-Subset-Sum
Problem", and it will appear in Information Processing Letters in
summer 1992.

Woeginger's e-mail address is 
    gwoegi@igi.tu-graz.ac.at   or
    gwoegi@fiicm2ds01.tu-graz.ac.at   


========================================================================
  Hannes Hassler
========================================================================

Newsgroups: comp.theory
From: wenbo@cs.strath.ac.uk (Wenbo Mao)
Newsgroups: comp.theory
Subject: Question: the verification of algebraic processes
Keywords: Verification, CCS, testing equivalence, concurrency workbench
Date: 9 Apr 92 15:50:57 GMT
Organization: Comp. Sci. Dept., Strathclyde Univ., Glasgow, Scotland.

Dear Colleagues,

I have a technical problem in the area of the process algebras. I
gratefully thank you for your help.

My problem may be described as follows.

In the literature, I often find that when verifying a process
equivalence relation (testing equivalence of De Nicola and Hennessy,
for instance) by transition semantic approaches, a nondeterministic
problem is usually first transformed into a deterministic one prior to
proof. For example, in the Concurrency Workbench (CWB), nondeterministic
processes are transformed into "t-graphs" which are deterministic 
transition systems with the notion of acceptance sets (De Nicola and
Hennessy), and then a proof is conducted using the partitioning method.

Let's take an example. To verify the testing equivalence for the
following CCS processes P and Q:

P <= a.P + a.b + a.(P + b)

Q <= a.R,  R <= \tau.a.R + \tau.b

they are transformed (in CWB) respectively into the following t-graphs:

P' <= a.P1,  P1 <= a.P1 + b  and  P'.acc = {{a}}, P1.acc = {{a},{b}, {a,b}}

Q' <= a.R',  R' <= a.R' + b  and  Q'.acc = {{a}}, R'.acc = {{a},{b}}

Then P', Q' can be proved to be testing equivalent (using partitioning
method).

My questions are as follows:

(1) Is such a transformation from nondeterministic system to
    deterministic one necessary?

I believe that it is necessary if using partitioning method. Then:

(2) Why cannot we verify P =testing= Q by directly applying the
    testing equivalence definition? That is, by verifying that:

      P "less deterministic than" Q  and conversely
      Q "less deterministic than" P  as follows:

      P =s=> P'  then  Q =s=> Q'  and  acc(P') subsub acc(Q')
      Q =s=> Q'  then  P =s=> P'  and  acc(Q') subsub acc(P')

    where subsub denotes a relation between acceptance sets which
    characterises the notion of the testing "must".

Again, thank you very very much for your advice.

Wenbo Mao
+----------------------------------+--------------------------------+
|  Department of Computer Science  | phone: (+44) 41 552 4400 x3635 |
|  University of Strathclyde       | email: wenbo@uk.ac.strath.cs   |
|  Glasgow G1 1XH                  |                                |
|  UK                              | Networks all lands, unite!     | 
+----------------------------------+--------------------------------+
-- 
test
Newsgroups: comp.theory
From: wlfong@logos.waterloo.edu (Philip W. L. Fong)
Subject: On-line algorithms
Organization: University of Waterloo
Date: Fri, 10 Apr 1992 15:13:44 GMT

Does anyone know what on-line algorithm is?  And, any reference for this?

Philip Fong
From: madhu@kazoo.Berkeley.EDU (Madhu Sudan)
Newsgroups: comp.theory
Subject: Clarification on recent NYT article
Date: 15 Apr 92 19:57:13 GMT
Article-I.D.: agate.si1qpINNr3r
Organization: University of California, Berkeley
NNTP-Posting-Host: kazoo.berkeley.edu


   CLARIFICATION ABOUT THE RECENT RESULT ON CHECKING PROOFS
   ------------- ----- --- ------ ------ -- -------- ------

The recent article in the New York Times concerning  our  results
contained  several  inaccuracies despite our best efforts to keep
their  staff  informed.   This  brief   note   is   intended   to
express   our   regret   at these inaccuracies and to dispel  any
confusion   arising   from them.

Our result builds directly upon the techniques  of  another   (as
yet  unpublished)  result  due  to Sanjeev Arora and Shmuel Safra
which showed how to check a  proof  of  length  n   by   randomly
choosing   only  O(log  log n) bits in it to look at. This result
preceded ours by a month, and the improvement  we  show  is  that
looking   at   only   a constant  number  of  bits suffices (this
enabled us to show that approximating MAX-SNP -hard  problems  is
NP-hard).

We feel that  the  people  quoted  in   the   NYT   article  were
referring  to  both these papers, which was not made clear in the
article.  In particular, we regret that it fails  to  mention Dr.
Safra's contribution at all.

The NYT article also did not mention that the concept of "easily"
checkable proofs/computations described there was introduced in a
paper called "Checking computations in polylogarithmic  time"  by
L.Babai,  L.Fortnow,  L.Levin,  M.Szegedy in STOC'91.  This paper
was based upon the amazing sequence  of  results  on  interactive
proof  systems  presented  at  FOCS  '90,  especially  the result
"MIP=EXPTIME" by L.Babai, L.Fortnow, C.Lund. The  idea  of  using
these  techniques  to show hardness results for approximating the
clique number was intiated in the paper "Approximating Clique  is
almost  NP-complete"  by U.Feige, S.Goldwasser L.Lovasz, S.Safra,
M.Szegedy in FOCS'91.

[Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan,  Mario
Szegedy.]

(The  widest  possible  circulation  of   this   note   will   be
appreciated.)
Newsgroups: comp.theory
From: dondaing@glasses.Princeton.EDU (Donald D. Aingworth)
Subject: Re: P!=NP, or April fools...I don't know
Originator: news@ernie.Princeton.EDU
Organization: Princeton University
Date: Thu, 9 Apr 1992 05:08:07 GMT

In article <8dN=02Ln0fjp01@JUTS.ccc.amdahl.com> stevena@cs.berkeley.edu (Steven Alexander) writes:
>The researchers did NOT purport to have proven whether P=NP.
>
>What they showed is that for a certain class of problems, it is not
>true that for all (epsilon > 0), there is a polynomial time algorithm
>to APPROXIMATE the solution to the problem within a factor of
>(1 + epsilon) UNLESS P=NP.  For certain problems they have a constant
>epsilon_0 for which they have shown that no polynomial algorithm
>approximates within (1 + epsilon; epsilon < epsilon_0) (again unless
>P=NP).
>- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
>Steven Alexander
>CS Grad Studentstevena@cs.berkeley.edu

I am wondering if this will give rise to two new complexity classes:
NP-complete (non)approximatable?  It seems fully possible that just
because two problems are solution reducable, they would not be
approximation reducable (because small errors in one could cause
exponential errors in others).  What I am asking is how wide is this
class NPA?

thanks,
don.
From: eanv20@castle.ed.ac.uk (John Woods)
Newsgroups: comp.theory
Subject: binomial simulation
Date: 7 Apr 92 08:12:00 GMT
Distribution: comp
Organization: Edinburgh University

Hi.  I tried this on comp.programming recently without much success,
although the one respondent I got managed to work out what I was
trying to say and suggests it is best put like this:

Is there an algorithm to simulate a binomial random variable 
B(n,p) using fewer than O(n) random numbers (as required by
the naive, coin-tossing algorithm)?

		[Thanks to Gene Ressler]

So far I've attempted to do it by generating a single random variable
and interpolating it onto the cumulative binomial.  The interpolation
method I used was simple interval halving (I don't know the derivative
of the Cum. Bin. function, so I couldn't use Newton-Raphson).  But
even this gross approach seemed to surpass the coin tossing algorithm
at around n=100000.

				...John Woods

-- 
 /******* cut here ******* John Woods ******* cut here ********
 * Philosophy: Forsan et haec olim meminisse iuvabit (Virgil) *
 * Disclaimer: Every statement in this file is possibly !true *
 ******** cut here ******* John Woods ******* cut here *******/
Xref: sparky comp.theory:1064 sci.math:5799
From: yan-dicky@CS.YALE.EDU (Dicky Yan)
Newsgroups: comp.theory,sci.math
Subject: Combinatorial Optimization Problems on Line Graphs (Summary)
Keywords: Line Graphs, Combinatorial Optimization
Date: 9 Apr 92 10:34:55 GMT
Article-I.D.: cs.1992Apr9.103455.10611
Organization: Yale University, Department of Computer Science


I made a post earlier about information on combinatorial optimization
problems on Line Graphs. I want to thank the following people for 
respond to the post and now make a summary.
I shall also include some of the references I have found myself. 


	crippa@inf.ethz.ch      Davide Crippa
	rbk@theory.cs.psu.edu   Balaji Raghavachari
	soroker@shell.com       Danny Sorokerss
	srin@cs.cornell.edu     Aravind Srinivasan


   Thanks!!

1) Find (an isomorphic copy of) the root graph G, of a line graph L(G)
   References:
   P.Lehot, An optimal Algorithm to detect a line graph and
         output its root graph, J. of ACM 21 (1974)
                              and 
   N.Roussopoulos, A max{n,m} Algorithm for detecting the graph H
                from its line graph G, Inf. Process. Letters 2 (1973)
                              and 
   D.Degiorgi, A new linear algorithm to detect a line graph and
            output its root graph, Tech. Report 148 ETH Zurich.

2) The book ``Selected Topics in Graph Theory'', Beineke & Wilson eds. (1978)
   contains a chapter on Line Graphs and Digraphs.


3) Papers from the J. of Graph Theory:

   i) "On Hamiltonian Line Graphs", Lane Clark, Vol. 8, 303-7, (84)

  ii) "Contractions and Hamitonian Line Graphs", H. Lai, Vol.12, No.1,11-15(88)

 iii) "Which Line-Graphs Are Perfectly Orderable?", V. Chvatal,Vol.14.,No.5,
       page 555-558, (1990)


4) In additon, it was pointed out that the maximum independent problem on 
   a line graph L(G) is equivalent to the matching problem on its root
   graph G. Line graphs also  belong to the class of graphs that are 
   "Claws Free".

Dicky Yan.
[yan-dicky@cs.yale.edu]
Newsgroups: comp.theory
From: mittle@watson.ibm.com (Josh Mittleman)
Subject: Re: On-line algorithms
Date: Fri, 10 Apr 1992 16:30:24 GMT
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
Organization: IBM T.J. Watson Research Center

In article <1992Apr10.151344.559@watdragon.waterloo.edu>,
wlfong@logos.waterloo.edu (Philip W. L. Fong) writes:
> Does anyone know what on-line algorithm is?  And, any reference for this?

An on-line algorithm is one which must process its data element-by-element
in the order received, without looking ahead.  Thus, an on-line sort
algorithm would have to maintain a sorted list of all the elements received
so far, and update it as each new element was provided.  

===========================================================================
Josh Mittleman (mittle@watson.ibm.com)
J2-C28 T.J. Watson Research Center, PO Box 704, Yorktown Heights, NY  10598
From: selman@CS.BUFFALO.EDU (Alan Selman)
Newsgroups: comp.theory
Subject: 25th anniversary symposium at UB
Date: 16 Apr 92 18:21:16 GMT
Article-I.D.: castor.9204161740.AA21542
Reply-To: Alan Selman <selman@cs.Buffalo.EDU>


                State University of New York at Buffalo

                 25th ANNIVERSARY CELEBRATORY SYMPOSIUM

                     Sunday, May 3, 1992:  Banquet
                    Monday, May 4, 1992:  Symposium

                   Center for Tomorrow, North Campus

This academic year marks the 25th anniversary of the Department of Computer
Science at SUNY Buffalo.  Join in the celebration activities!

Sunday, May 3, 1992:

5:00-6:30 p.m.  Registration/Reception
6:30 p.m.       Banquet
                        ANTHONY RALSTON, Professor and Founding Chairman
                        "Twenty-Five Years at UB"

                        BRUCE SHRIVER, Ph.D. '71,
                        1992 President, IEEE Computer Society
                        "Recent Advances in Ultra-High Performance Systems"

Monday, May 4, 1992:

8:00-9:00 a.m.  Registration
9:00 a.m.       Welcome
                        WILLIAM  R. GREINER, President, University at Buffalo

9:30-10:30 a.m. SAUL AMAREL, Rutgers University
                "Artificial Intelligence and Problems of Design"

11:00-12 p.m.   JURIS HARTMANIS, Cornell University
                "From Goedel and von Neumann to P =? NP and Interactive Proofs:
                The Search for the Limits of Feasible Computability"

1:30-2:30 p.m.  DAVID PARNAS, McMaster University
                "Evaluation Standards for Safety-Critical Software"

3:00-4:00 p.m.  AZRIEL ROSENFELD, University of Maryland
                "Image Understanding: Advances, Benefits, and Challenges"

Additional Information:

Cost: $50.00 payable to "Research Foundation of SUNY"
(Additional banquet tickets $30.00)
Full-time graduate students: $10.00 symposium only.

Deadline for registration: Friday, April 24, 1992

Questions and response to: Elenora Heffner, Department of Computer Science,
228 Bell Hall, University at Buffalo, Buffalo, NY 14260 - 716-636-2464 -
heffner@cs.buffalo.edu.
From: xue@cs.umn.edu (Guo-Liang Xue)
Newsgroups: comp.theory
Subject: Lin and Kernighan heuristic for graph partition
Date: 17 Apr 92 11:38:58 GMT
Article-I.D.: cs.1992Apr17.113858.13409
Organization: University of Minnesota, Minneapolis, CSci dept.

Given an edge weighted graph G with even number of vertices.
We want to partition G into two subgraphs G1 and G2 with equal
number of vertices in each such that the total edge weight
between G1 and G2 is minimized.

There is a famous heuristic algorithm for solving the above
problem proposed by Lin and Kernighan (or Kernighan and Lin)
which stops after at most |G1| swaps.

I am looking for that paper. Can anybody kindly point out
the source please? Thank you.

Guo-Liang Xue
Newsgroups: comp.theory
From: berman@gboro.glassboro.edu (Mike Berman)
Subject: Set with O(1) initialization
Organization: Glassboro State College
Date: Thu, 9 Apr 1992 21:11:46 GMT

Recently I posted a request for a reference for a set data
structure with O(1) initialization and query time.  Thanks to
all those who replied.

The most complete reference I was pointed to is in the book
Lewis, Harry R. and Larry Denenberg, "Data Structures and
Their Algorithms", HarperCollins Publishers Inc., New York,
1991.  On pp. 136--138 they demonstrate the initialization
trick for a matrix, and on pp. 258--259 it's applied to sets. 
By the way, this appears to be quite a good book both as a
text and as a reference.

The data structure can also be found on pp 289--290 of
Mehlhorn, Kurt, "Data Structures and Algorithms 1: Sorting and
Searching", EATCS Monographs on Theoretical Computer Science,
Springer Verlag, Berlin/New York, 1984.

The problem has an interesting history.  It apparently
appeared first in print in Aho/Hopcroft/Ullman, "The Design
and Analysis of Computer Algorithms", 1974, as exercise
2.12 on p. 71.  Before the book was out, the problem was
independendly solved by Teofilo F. Gonzalez, and appeared as a
technical report from Univ. of Oklahoma in 1975.  In Horowitz,
Sahni, "Fundamentals of Data Structures", 1976 (?), the same
problem appears again as an exercise, with credit to Gonzalez.

Thanks to Teo Gonzalez, Balaji Raghavachari, John Valois,
Haijo Schipper, Bruce Parker, Pierre Kelsen, and Larry
Denenberg for their replies.

For those who don't have any of these books handy, here's my
solution.

Specification:

Represent a subset S of [1..N], where |S| <= n.
Support the following operations:

	initialize(S)
		precondition: true
		postcondition: S = {}

	add(S,x)
		precondition: S initialized & (1 <= x <= N) & 
				(x not in S) & (|S| < n)
		postcondition: S = previous S with x added to it

	inquery(S,x)
		precondition: S initialized & (1 <= x <= N)
		postcondition: returns true if x in S, else false

	delete(S,x)
		precondition: S initialized & x in S
		postcondition: S = previous S with x removed

Data structures:

	Array A[1..N]
	Array B[1..n]
	integer card

Implementation:

	initialize(S)
		card := 0

	add(S, x)
		card := card + 1
		A[x] := card
		B[card] := x

	inquery(S, x)
		return (A[x] <= card) and then B[A[x]] = x

	delete(S, x) -- exercise

(note: "and then" is the "short-circuited" and from Ada, equiv. to && in C)

Analysis:

	space: N + n + O(1)
	time:
		initialize: 	O(1)
		add:		O(1)
		inquery:	O(1)

Comment:  This can be extended using hashing to represent
larger ranges; it can also be used with an arbitrary vector or
matrix with minor adjustments.


-- 
===========================================================================
A. Michael Berman    Assistant Professor     Department of Computer Science
Glassboro State College, Glassboro NJ 08028 USA.     Voice: +1 609 863-6521 
Fax: +1 609 863-6553 Internet: berman@gboro.glassboro.edu 
Xref: sparky comp.theory:1083 sci.math:5967
From: lavinus@csgrad.cs.vt.edu (Joseph Lavinus)
Newsgroups: comp.theory,sci.math
Subject: References on Geometric Graphs?
Date: 12 Apr 92 02:47:30 GMT
Followup-To: comp.theory
Organization: VPI&SU Computer Science Department, Blacksburg, VA

Hello!

I'm looking for references to graphs which [JAMS89] refers to as "geometric
graphs".  These are a type of random graphs; the graph $U_{n,d}$ is generated
in the following way:

   For each of the $n$ vertices, assign $x$ and $y$ coordinates chosen from
      a uniform random distribution over the interval (0,1)

   In the graph, there exists an edge between two vertices if the Euclidean
      distance between the assigned points is less than $d$.

[JAMS89] cites no reference for these, but I find it difficult to believe that
they were invented in 1989.  If anyone knows of any references to graphs
similar to what I just described, please let me know.  I'll summarize if there
is a demand.

Note: There are graphs discussed in the literature, called "geometric graphs",
  which are not what I just described.  Conversely, there are probably
  discussions of the graphs I just described, but called something other
  than "geometric graphs".  i.e., the name "geometric graphs" is not especially
  meaningful.

Thanks in advance,

Joe


[JAMS89] Johnson, D.S., C.R. Aragon, L.A. McGeoch, and C. Schevon, 
  "Optimization by Simulated Annealing: Part I, Graph Partitioning",
  OPERATIONS RESEARCH, 37: 865-892
-- 
______________________________________________________________________________
 Joseph W. Lavinus, Virginia Tech   /o)\    email: lavinus@cstheory.cs.vt.edu
 1001 University City Blvd., #F-9   \(o/  Blacksburg, VA 24060 / 703-953-2678
 "Let me play with it first and I'll tell you what it is later" - Miles Davis