Arrow Research search

Author name cluster

Rainer Feldmann

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers
2 author rows

Possible papers

3

MFCS Conference 2003 Invited Paper

Selfish Routing in Non-cooperative Networks: A Survey

  • Rainer Feldmann
  • Martin Gairing
  • Thomas Lücking 0001
  • Burkhard Monien
  • Manuel Rode

Abstract We study the problem of n users selfishly routing traffics through a shared network. Users route their traffics by choosing a path from their source to their destination of the traffic with the aim of minimizing their private latency. In such an environment Nash equilibria represent stable states of the system: no user can improve its private latency by unilaterally changing its strategy. In the first model the network consists only of a single source and a single destination which are connected by m parallel links. Traffics are unsplittable. Users may route their traffics according to a probability distribution over the links. The social optimum minimizes the maximum load of a link. In the second model the network is arbitrary, but traffics are splittable among several paths leading from their source to their destination. The goal is to minimize the sum of the edge latencies. Many interesting problems arise in such environments: A first one is the problem of analyzing the loss of efficiency due to the lack of central regulation, expressed in terms of the coordination ratio. A second problem is the Nashification problem, i. e. the problem of converting any given non-equilibrium routing into a Nash equilibrium without increasing the social cost. The Fully Mixed Nash Equilibrium Conjecture ( FMNE Conjecture) states that a Nash equilibrium, in which every user routes along every possible edge with probability greater than zero, is a worst Nash equilibrium with respect to social cost. A third problem is to exactly specify the sub-models in which the FMNE Conjecture is valid. The well-known Braess’s Paradox shows that there exist networks, such that strict sub-networks perform better when users are selfish. A natural question is the following network design problem: Given a network, which edges should be removed to obtain the best possible Nash equilibrium. We present complexity results for various problems in this setting, upper and lower bounds for the coordination ratio, and algorithms solving the problem of Nashification. We survey results on the validity of the FMNE Conjecture in the model of unsplittable flows, and for the model of splittable flows we survey results for the network design problem.

Details

AAAI Conference 2000 Conference Paper

A Distributed Algorithm to Evaluate Quantified Boolean Formulae

  • Rainer Feldmann
  • and Stefan Schamberger

In this paper, we present PQSOLVE, a distributed theorem-prover for Quantified Boolean Formulae. First, we introduce our sequential algorithm QSOLVE, which uses new heuristics and improves the use of known heuristics to prune the search tree. As a result, QSOLVE is more efficient than the QSAT-solvers previously known. We have parallelized QSOLVE. The resulting distributed QSAT-solver PQSOLVE uses parallel search techniques, which we have developed for distributed game tree search. PQSOLVE runs efficiently on distributed systems, i. e. parallel systems without any shared memory. We briefly present experiments that show a speedup of about 114 on 128 processors. To the best of our knowledge we are the first to introduce an efficient parallel QSAT-solver.

PDF Details

MFCS Conference 1992 Conference Paper

The Shuffle Exchange Network has a Hamiltonian Path

  • Rainer Feldmann
  • Peter Mysliwietz

Abstract The problem to determine whether a network contains a Hamiltonian path has been a. fundamental problem in graph theory. We prove the existence of a Hamiltonian path in the Shuffle Exchange network SX(n). This problem has been posed as an open problem by Leighton in [8] and Samatham and Pradhan in [11].

Details