55 citations · 145 across the 14 of their papers we have counts for
4 papers · 1 filter
Maximizing a Submodular Function with Viability Constraints
Wolfgang Dvořák, Monika Henzinger, David P. Williamson
We study the problem of maximizing a monotone submodular function with viability constraints. This problem originates from computational biology, where we are given a phylogenetic…
Conditionally Optimal Algorithms for Generalized Büchi Games
Krishnendu Chatterjee, Wolfgang Dvořák, Monika Henzinger +1
Games on graphs provide the appropriate framework to study several central problems in computer science, such as the verification and synthesis of reactive systems. One of the most…
Online Ad Assignment with an Ad Exchange
Wolfgang Dvořák, Monika Henzinger
Ad exchanges are becoming an increasingly popular way to sell advertisement slots on the internet. An ad exchange is basically a spot market for ad impressions. A publisher who has…
Model and Objective Separation with Conditional Lower Bounds: Disjunction is Harder than Conjunction
Krishnendu Chatterjee, Wolfgang Dvořák, Monika Henzinger +1
Given a model of a system and an objective, the model-checking question asks whether the model satisfies the objective. We study polynomial-time problems in two classical models, g…