Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR95-016 | 2nd February 1995
U. Faigle, S.P. Fekete, W. Hochstättler, W. Kern

On approximately fair cost allocation in Euclidean TSP games

We consider the problem of fair cost allocation for traveling
salesman games for which the triangle inequality holds. We
give examples showing that the core of such games may be
empty, even for the case of Euclidean distances. On the
positive side, we develop an LP-based ... more >>>


TR95-015 | 6th February 1995
Bshouty, Cleve, Gavalda, Kannan, Tamon.

Oracles and queries that are sufficient for exact learning

We show what happen to learning if the learner can use NP-oracle.
A consequence of our results we show that
If NP\subset P/poly then the polynomial Hierarchy collapses to ZPP^NP

END_OF_DESCRIPTION
Contact: bshouty@cpsc.ucalgary.ca (Nader Bshouty)

more >>>

TR95-014 | 27th January 1995
U. Faigle, W. Kern, M. Streng

Note On the Computational Complexity of $j$-Radii of Polytopes in ${\Re}^n$

We show that, for fixed dimension $n$, the approximation of
inner and outer $j$-radii of polytopes in ${\Re}^n$, endowed
with the Euclidean norm, is polynomial.

more >>>


previous PreviousNext next


ISSN 1433-8092 | Imprint