Dürr, Christoph

Lade...
Vorschaubild
Preferred name
Dürr, Christoph
Official Name
Dürr, Christoph
ORCID

Einstellungen

Gerade angezeigt 1 - 2 von 2
  • Lade...
    Vorschaubild
    Some of the metrics are blocked by your 
    consent settings
    Item-typ:Veröffentlichung,
    Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty
    (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021)
    Bampis, Evripidis
    ;
    Dürr, Christoph
    ;
    Erlebach, Thomas
    ;
    de Lima, Murilo Santos
    ;
    Megow, Nicole
    Given a hypergraph with uncertain node weights following known probability distributions, we study the problem of querying as few nodes as possible until the identity of a node with minimum weight can be determined for each hyperedge. Querying a node has a cost and reveals the precise weight of the node, drawn from the given probability distribution. Using competitive analysis, we compare the expected query cost of an algorithm with the expected cost of an optimal query set for the given instance. For the general case, we give a polynomial-time f(α)-competitive algorithm, where f(α) ∈ [1.618+ε,2] depends on the approximation ratio α for an underlying vertex cover problem. We also show that no algorithm using a similar approach can be better than 1.5-competitive. Furthermore, we give polynomial-time 4/3-competitive algorithms for bipartite graphs with arbitrary query costs and for hypergraphs with a single hyperedge and uniform query costs, with matching lower bounds.
    Konferenzbeitrag
      48  29
  • Lade...
    Vorschaubild
    Some of the metrics are blocked by your 
    consent settings
    Item-typ:Veröffentlichung,
    An Adversarial Model for Scheduling with Testing
    (Springer, 2020-07-10)
    Dürr, Christoph
    ;
    Erlebach, Thomas
    ;
    Megow, Nicole
    ;
    Meißner, Julie
    We introduce a novel adversarial model for scheduling with explorable uncertainty. In this model, the processing time of a job can potentially be reduced (by an a priori unknown amount) by testing the job. Testing a job j takes one unit of time and may reduce its processing time from the given upper limit ̄pj (which is the time taken to execute the job if it is not tested) to any value between 0 and ̄pj . This setting is motivated e.g., by applications where a code optimizer can be run on a job before executing it. We consider the objective of minimizing the sum of completion times on a single machine. All jobs are available from the start, but the reduction in their processing times as a result of testing is unknown, making this an online problem that is amenable to competitive analysis. The need to balance the time spent on tests and the time spent on job executions adds a novel flavor to the problem. We give the first and nearly tight lower and upper bounds on the competitive ratio for deterministic and randomized algorithms. We also show that minimizing the makespan is a considerably easier problem for which we give optimal deterministic and randomized online algorithms.
    Wissenschaftlicher Artikel
    Band:82
      102  90