Skip to main content

Research Repository

Advanced Search

Outputs (671)

Planar tautologies hard for resolution (2001)
Presentation / Conference Contribution
Dantchev, S., & Riis, S. (2001, October). Planar tautologies hard for resolution. Presented at 42nd IEEE Symposium of Foundations of Computer Science, Las Vegas, Nev

We prove exponential lower bounds on the resolution proofs of some tautologies, based on rectangular grid graphs. More specifically, we show a 2/sup /spl Omega/(n)/ lower bound for any resolution proof of the mutilated chessboard problem on a 2n/spl... Read More about Planar tautologies hard for resolution.

Tree resolution proofs of the weak pigeon-hole principle (2001)
Presentation / Conference Contribution
Dantchev, S., & Riis, S. (2001, June). Tree resolution proofs of the weak pigeon-hole principle. Presented at 16th Annual IEEE Conference on Computational Complexity, Chicago, Ill

We prove that any optimal tree resolution proof of PHPn m is of size 2&thetas;(n log n), independently from m, even if it is infinity. So far, only a 2Ω(n) lower bound has been known in the general case. We also show that any, not necessarily optimal... Read More about Tree resolution proofs of the weak pigeon-hole principle.

Two extensions of the Shapley value for cooperative games (2001)
Journal Article
Driessen, T., & Paulusma, D. (2001). Two extensions of the Shapley value for cooperative games. Mathematical Methods of Operations Research, 53(1), 35-49. https://doi.org/10.1007/s001860000099

Two extensions of the Shapley value are given. First we consider a probabilistic framework in which certain consistent allocation rules such as the Shapley value are characterized. The second generalization of the Shapley value is an extension to the... Read More about Two extensions of the Shapley value for cooperative games.

The new FIFA rules are hard: complexity aspects of sports competitions (2001)
Journal Article
Kern, W., & Paulusma, D. (2001). The new FIFA rules are hard: complexity aspects of sports competitions. Discrete Applied Mathematics, 108(3), 317-323. https://doi.org/10.1016/s0166-218x%2800%2900241-9

Consider a soccer competition among various teams playing against each other in pairs (matches) according to a previously determined schedule. At some stage of the competition one may ask whether a particular team still has a (theoretical) chance to... Read More about The new FIFA rules are hard: complexity aspects of sports competitions.

The complexity of maximal constraint languages (2001)
Presentation / Conference Contribution
Bulatov, A., Krokhin, A., & Jeavons, P. (2001, December). The complexity of maximal constraint languages. Presented at 33rd ACM Symposium on the Theory of Computing(STOC), Crete, Greece

Many combinatorial search problems can be expressed as “constraint satisfaction problems” using an appropriate “constraint language”, that is, a set of relations over some fixed finite set of values. It is well-known that there is a trade-off between... Read More about The complexity of maximal constraint languages.

Infinite parallel job allocation (extended abstract) (2000)
Presentation / Conference Contribution
Berenbrink, P., Czumaj, A., Friedetzky, T., & Vvedenskaya, N. D. (2000, December). Infinite parallel job allocation (extended abstract). Presented at Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures - SPAA '00

Note on the computational complexity of least core concepts for min-cost spanning tree games (2000)
Journal Article
Faigle, U., Kern, W., & Paulusma, D. (2000). Note on the computational complexity of least core concepts for min-cost spanning tree games. Mathematical Methods of Operations Research, 52(1), 23-38. https://doi.org/10.1007/s001860000059

Various least core concepts including the classical least core of cooperative games are discussed. By a reduction from minimum cover problems, we prove that computing an element in these least cores is in general NP-hard for minimum cost spanning tre... Read More about Note on the computational complexity of least core concepts for min-cost spanning tree games.

Randomized and adversarial load balancing (1999)
Presentation / Conference Contribution
Berenbrink, P., Friedetzky, T., & Steger, A. (1999, December). Randomized and adversarial load balancing. Presented at Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures - SPAA '99

Parallel continuous randomized load balancing (extended abstract) (1998)
Presentation / Conference Contribution
Berenbrink, P., Friedetzky, T., & Mayr, E. W. (1998, December). Parallel continuous randomized load balancing (extended abstract). Presented at Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures - SPAA '98