 Mi,8.5.2002
|
Alex Hall
NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source
Unsplittable Min-Cost Flow
|
We consider the version of broadcast scheduling where a server can
transmit one message of a given set at each time-step, answering
previously made requests for that message. The goal is to minimize the
average response time if the amount of requests is known in advance for
each time-step and message. We prove that this problem is NP-hard, thus
answering an open question stated by Kalyanasundaram, Pruhs and
Velauthapillai (Proceedings of ESA 2000, LNCS 1879, 2000, pp.\ 290--301).
Furthermore, we present an approximation algorithm that is allowed to send several messages at once. Using 6 channels for
transmissions, the algorithm achieves an average response time that is at
least as good as the optimal solution using one channel. The best previous
approximation algorithm achieved ratio 1.5 with 6 channels and reached
ratio 1 only in the case where there are as many channels as messages.
From the NP-hardness of broadcast scheduling we derive a new
inapproximability result of $(2 - \varepsilon, 1)$ for the
(congestion,cost) bicriteria version of the single source unsplittable
min-cost flow problem, for arbitrary $\varepsilon > 0$. The result holds
even in the often considered case where the maximum demand is less than or
equal to the minimum edge capacity ($d_{\max} \le u_{\min}$), a case for
which an algorithm with ratio $(3, 1)$ was presented by Skutella.
Our results were published in SODA 2002.
|
|
|
Mi,29.5.2002
|
Nicolas Fournier
Insights into local search for SAT
|
Lokale Suchalgorithmen und verwandte Heuristiken, wie zum Beispiel
Evolutionäre Algorithmen, Tabu-Suche, Simmulated Annealing, u.Ä., haben
Dank ihrer Robustheit und Effizienz in den letzten Jahren zunehmend an
Beliebtheit gewonnen. Jedoch um zu wissen ob und wie gut ein solcher
Algorithmus funktioniert, bleibt zur Zeit meist nichts anderes übrig als
ihn zu implementieren und laufen zu lassen, denn das theoretische
Verständnis dieser Algorithmen ist noch rudimentär.
Der Vortrag diese Woche geht einen Schritt in Richtung eines besseren
Verständnisses lokaler Suchalgorithmen. Präsentiert wird zuerst eine
Analyse der lokalen Struktur des Suchraums kombinatorischer Probleme, am
Beispiel des SATISFIABILITY Problems. Auf dieser Struktur aufbauend kann
ein Markov Prozess definiert werden, der es erlaubt lokale Suchalgorithmen
zu modellieren. Der Vergleich mit experimentellen Ergebnissen zeigt, dass
der Markov Prozess die erwartete Laufzeit einer Reihe an randomisierten
lokalen Suchalgorithmen auf zufälligen SAT-Instanzen gut beschreibt. Dies
unterstützt die These, dass die lokale Struktur allein ausreicht um die
durchschnittliche Laufzeit der Algorithmen zu beschreiben, und dass keine
weitere globale Strukturen in Betracht gezogen werden müssen.
|
|
|
Do,20.6.2002
|
S. Arun-Kumar (IIT Delhi)
Reflecting BDDs in Coq
|
|
We describe an implementation and a proof of correctness of binary
decision diagrams (BDDs), completely formalized in Coq. This allows us
to run BDD-based algorithms inside Coq and paves the way for a smooth
integration of symbolic model checking in the Coq proof assistant by
using reflection. It also gives us, by Coq's extraction mechanism,
certified BDD algorithms implemented in Caml. We have also implemented
and proved correct, a garbage collector for our implementation of BDDs
inside Coq. Our experiments show that this approach works in
practice, and is able to solve both relatively hard propositional
problems and actual industrial hardware verification tasks.
|
|
|
Mi,3.7.2002
|
Klaus Holzapfel
The complexity of finding dense subgraphs
|
|
We study the complexity of finding a subgraph of certain
size and certain density, where density is measured by
the average degree. Let \gamma >= 0 be any fixed
rational (which may depend on an argument). Then \gamma-Cluster is the
problem of deciding, given an undirected graph G and natural number
k, whether there is a subgraph of G on k vertices which has average
degree at least $\gamma(k)$. For \gamma =k-1, this problem becomes the
well-known clique problem, and is thus NP-complete. We ask for the
possible values of \gamma such that \gamma-Cluster remains NP-complete or
becomes solvable in polynomial time. We show \gamma-Cluster is N-complete
if \gamma= 2+\Theta(1/k^{1-\epsilon}) for some 0<
\epsilon <2 and has a polynomial-time algorithm for \gamma=2+O(1/k).
|
|
|
Mi,10.7.2002
|
Michal Mnuk
On Complexity of Computation with Modules over Polynomial Rings
|
|
Based on algorithms for Gröbner bases and syzygies we present an
EXPSPACE upper bound for computing a finite free resolution of a
module over the ring of polynomials. Furthermore, we show that tensor
product, Hom-functor, Tor and Ext modules can be computed within the
same bound. This sheds more light on the complexity of a large number
of algorithms in commutative algebra and algebraic geometry built on
these notions.
|
|
|
