12 Search Results for "D�rfler, Monika"

Document
DOI: 10.4230/LIPIcs.ISAAC.2022.30
List Locally Surjective Homomorphisms in Hereditary Graph Classes

Authors: Pavel Dvořák, Tomáš Masařík, Jana Novotná, Monika Krawczyk, Paweł Rzążewski, and Aneta Żuk

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
A locally surjective homomorphism from a graph G to a graph H is an edge-preserving mapping from V(G) to V(H) that is surjective in the neighborhood of each vertex in G. In the list locally surjective homomorphism problem, denoted by LLSHom(H), the graph H is fixed and the instance consists of a graph G whose every vertex is equipped with a subset of V(H), called list. We ask for the existence of a locally surjective homomorphism from G to H, where every vertex of G is mapped to a vertex from its list. In this paper, we study the complexity of the LLSHom(H) problem in F-free graphs, i.e., graphs that exclude a fixed graph F as an induced subgraph. We aim to understand for which pairs (H,F) the problem can be solved in subexponential time. We show that for all graphs H, for which the problem is NP-hard in general graphs, it cannot be solved in subexponential time in F-free graphs for F being a bounded-degree forest, unless the ETH fails. The initial study reveals that a natural subfamily of bounded-degree forests F, that might lead to some tractability results, is the family 𝒮 consisting of forests whose every component has at most three leaves. In this case, we exhibit the following dichotomy theorem: besides the cases that are polynomial-time solvable in general graphs, the graphs H ∈ {P₃,C₄} are the only connected ones that allow for a subexponential-time algorithm in F-free graphs for every F ∈ 𝒮 (unless the ETH fails).
Cite as

Pavel Dvořák, Tomáš Masařík, Jana Novotná, Monika Krawczyk, Paweł Rzążewski, and Aneta Żuk. List Locally Surjective Homomorphisms in Hereditary Graph Classes. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.ISAAC.2022.30,
  author =	{Dvo\v{r}\'{a}k, Pavel and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Novotn\'{a}, Jana and Krawczyk, Monika and Rz\k{a}\.{z}ewski, Pawe{\l} and \.{Z}uk, Aneta},
  title =	{{List Locally Surjective Homomorphisms in Hereditary Graph Classes}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{30:1--30:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.30},
  URN =		{urn:nbn:de:0030-drops-173154},
  doi =		{10.4230/LIPIcs.ISAAC.2022.30},
  annote =	{Keywords: Homomorphism, Hereditary graphs, Subexponential-time algorithms}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2021.124
Faster Algorithms for Bounded Liveness in Graphs and Game Graphs

Authors: Krishnendu Chatterjee, Monika Henzinger, Sagar Sudhir Kale, and Alexander Svozil

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
Graphs and games on graphs are fundamental models for the analysis of reactive systems, in particular, for model-checking and the synthesis of reactive systems. The class of ω-regular languages provides a robust specification formalism for the desired properties of reactive systems. In the classical infinitary formulation of the liveness part of an ω-regular specification, a "good" event must happen eventually without any bound between the good events. A stronger notion of liveness is bounded liveness, which requires that good events happen within d transitions. Given a graph or a game graph with n vertices, m edges, and a bounded liveness objective, the previous best-known algorithmic bounds are as follows: (i) O(dm) for graphs, which in the worst-case is O(n³); and (ii) O(n² d²) for games on graphs. Our main contributions improve these long-standing algorithmic bounds. For graphs we present: (i) a randomized algorithm with one-sided error with running time O(n^{2.5} log n) for the bounded liveness objectives; and (ii) a deterministic linear-time algorithm for the complement of bounded liveness objectives. For games on graphs, we present an O(n² d) time algorithm for the bounded liveness objectives.
Cite as

Krishnendu Chatterjee, Monika Henzinger, Sagar Sudhir Kale, and Alexander Svozil. Faster Algorithms for Bounded Liveness in Graphs and Game Graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 124:1-124:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.ICALP.2021.124,
  author =	{Chatterjee, Krishnendu and Henzinger, Monika and Kale, Sagar Sudhir and Svozil, Alexander},
  title =	{{Faster Algorithms for Bounded Liveness in Graphs and Game Graphs}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{124:1--124:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.124},
  URN =		{urn:nbn:de:0030-drops-141930},
  doi =		{10.4230/LIPIcs.ICALP.2021.124},
  annote =	{Keywords: Graphs, Game Graphs, B\"{u}chi}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.28
Escaping the Curse of Spatial Partitioning: Matchings with Low Crossing Numbers and Their Applications

Authors: Mónika Csikós and Nabil H. Mustafa

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
Given a set system (X, S), constructing a matching of X with low crossing number is a key tool in combinatorics and algorithms. In this paper we present a new sampling-based algorithm which is applicable to finite set systems. Let n = |X|, m = | S| and assume that X has a perfect matching M such that any set in 𝒮 crosses at most κ = Θ(n^γ) edges of M. In the case γ = 1- 1/d, our algorithm computes a perfect matching of X with expected crossing number at most 10 κ, in expected time Õ (n^{2+(2/d)} + mn^(2/d)). As an immediate consequence, we get improved bounds for constructing low-crossing matchings for a slew of both abstract and geometric problems, including many basic geometric set systems (e.g., balls in ℝ^d). This further implies improved algorithms for many well-studied problems such as construction of ε-approximations. Our work is related to two earlier themes: the work of Varadarajan (STOC '10) / Chan et al. (SODA '12) that avoids spatial partitionings for constructing ε-nets, and of Chan (DCG '12) that gives an optimal algorithm for matchings with respect to hyperplanes in ℝ^d. Another major advantage of our method is its simplicity. An implementation of a variant of our algorithm in C++ is available on Github; it is approximately 200 lines of basic code without any non-trivial data-structure. Since the start of the study of matchings with low-crossing numbers with respect to half-spaces in the 1980s, this is the first implementation made possible for dimensions larger than 2.
Cite as

Mónika Csikós and Nabil H. Mustafa. Escaping the Curse of Spatial Partitioning: Matchings with Low Crossing Numbers and Their Applications. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{csikos_et_al:LIPIcs.SoCG.2021.28,
  author =	{Csik\'{o}s, M\'{o}nika and Mustafa, Nabil H.},
  title =	{{Escaping the Curse of Spatial Partitioning: Matchings with Low Crossing Numbers and Their Applications}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{28:1--28:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.28},
  URN =		{urn:nbn:de:0030-drops-138273},
  doi =		{10.4230/LIPIcs.SoCG.2021.28},
  annote =	{Keywords: Matchings, crossing numbers, approximations}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.51
Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles

Authors: Monika Henzinger, Stefan Neumann, and Andreas Wiese

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
Independent set is a fundamental problem in combinatorial optimization. While in general graphs the problem is essentially inapproximable, for many important graph classes there are approximation algorithms known in the offline setting. These graph classes include interval graphs and geometric intersection graphs, where vertices correspond to intervals/geometric objects and an edge indicates that the two corresponding objects intersect. We present dynamic approximation algorithms for independent set of intervals, hypercubes and hyperrectangles in d dimensions. They work in the fully dynamic model where each update inserts or deletes a geometric object. All our algorithms are deterministic and have worst-case update times that are polylogarithmic for constant d and ε>0, assuming that the coordinates of all input objects are in [0, N]^d and each of their edges has length at least 1. We obtain the following results: - For weighted intervals, we maintain a (1+ε)-approximate solution. - For d-dimensional hypercubes we maintain a (1+ε)2^d-approximate solution in the unweighted case and a O(2^d)-approximate solution in the weighted case. Also, we show that for maintaining an unweighted (1+ε)-approximate solution one needs polynomial update time for d ≥ 2 if the ETH holds. - For weighted d-dimensional hyperrectangles we present a dynamic algorithm with approximation ratio (1+ε)log^{d-1}N.
Cite as

Monika Henzinger, Stefan Neumann, and Andreas Wiese. Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.SoCG.2020.51,
  author =	{Henzinger, Monika and Neumann, Stefan and Wiese, Andreas},
  title =	{{Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{51:1--51:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.51},
  URN =		{urn:nbn:de:0030-drops-122094},
  doi =		{10.4230/LIPIcs.SoCG.2020.51},
  annote =	{Keywords: Dynamic algorithms, independent set, approximation algorithms, interval graphs, geometric intersection graphs}
}
Document
DOI: 10.4230/LIPIcs.GISCIENCE.2018.6
Outlier Detection and Comparison of Origin-Destination Flows Using Data Depth

Authors: Myeong-Hun Jeong, Junjun Yin, and Shaowen Wang

Published in: LIPIcs, Volume 114, 10th International Conference on Geographic Information Science (GIScience 2018)

Abstract
Advances in location-aware technology have resulted in massive trajectory data. Origin-destination (OD) trajectories provide rich information on urban flow and transport demand. This study describes a new method for detecting OD flows outliers and conducting hypothesis testing between two OD flow datasets in terms of the variations of spatial extent, that is, spread. The proposed method is based on data depth, which measures the centrality and outlyingness of a point with respect to a given dataset in R^d. Based on the center-outward ordering property, the proposed method analyzes the underlying characteristics of OD flows, such as location, outlyingness, and spread. The ability of the method to detect OD anomalies is compared with that of the Mahalanobis distance approach, and an F-test is used to verify the difference in scale. Empirical evaluation has demonstrated that our method effectively identifies OD flows outliers in an interactive way. Furthermore, the method can provide new perspectives such as spatial extent by considering the overall structure of data when comparing two different OD flows in terms of scale.
Cite as

Myeong-Hun Jeong, Junjun Yin, and Shaowen Wang. Outlier Detection and Comparison of Origin-Destination Flows Using Data Depth. In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{jeong_et_al:LIPIcs.GISCIENCE.2018.6,
  author =	{Jeong, Myeong-Hun and Yin, Junjun and Wang, Shaowen},
  title =	{{Outlier Detection and Comparison of Origin-Destination Flows Using Data Depth}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-083-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{114},
  editor =	{Winter, Stephan and Griffin, Amy and Sester, Monika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.6},
  URN =		{urn:nbn:de:0030-drops-93341},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.6},
  annote =	{Keywords: Movement Analysis, Trajectory Data Mining, Data Depth, Outlier Detection}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GISCIENCE.2018.22
Design for Geospatially Enabled Climate Modeling and Alert System (CLIMSYS): A Position Paper (Short Paper)

Authors: Devanjan Bhattacharya and Marco Painho

Published in: LIPIcs, Volume 114, 10th International Conference on Geographic Information Science (GIScience 2018)

Abstract
The paper brings the focus on to multi-disciplinary approach of presenting climate analysis studies, taking help of interdisciplinary fields to structure the information. The system CLIMSYS provides the crucial element of spatially enabling climate data processing. Even though climate change is a matter of great scientific relevance and of broad general interest, there are some problems related to its communication. Its a fact that finding practical, workable and cost-efficient solutions to the problems posed by climate change is now a world priority and one which links government and non-government organizations in a way not seen before. An approach that should suffice is to create an accessible intelligent system that houses prior knowledge and curates the incoming data to deliver meaningful results. The objective of the proposed research is to develop a generalized system for climate data analysis that facilitates open sharing, central implementation, integrated components, knowledge creation, data format understanding, inferencing and ultimately optimal solution delivery, by the way of geospatial enablement.
Cite as

Devanjan Bhattacharya and Marco Painho. Design for Geospatially Enabled Climate Modeling and Alert System (CLIMSYS): A Position Paper (Short Paper). In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 22:1-22:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.GISCIENCE.2018.22,
  author =	{Bhattacharya, Devanjan and Painho, Marco},
  title =	{{Design for Geospatially Enabled Climate Modeling and Alert System (CLIMSYS): A Position Paper}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{22:1--22:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-083-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{114},
  editor =	{Winter, Stephan and Griffin, Amy and Sester, Monika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.22},
  URN =		{urn:nbn:de:0030-drops-93504},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.22},
  annote =	{Keywords: Spatial enablement, climate modeling, natural hazards, spatial data infrastructure, sensor web}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GISCIENCE.2018.37
How Do Texture and Color Communicate Uncertainty in Climate Change Map Displays? (Short Paper)

Authors: Irene M. Johannsen, Sara Irina Fabrikant, and Mariele Evers

Published in: LIPIcs, Volume 114, 10th International Conference on Geographic Information Science (GIScience 2018)

Abstract
We report on an empirical study with over hundred online participants where we investigated how texture and color value, two popular visual variables used to convey uncertainty in maps, are understood by non-domain-experts. Participants intuit denser dot textures to mean greater attribute certainty; irrespective of whether the dot pattern is labeled certain or uncertain. With this additional empirical evidence, we hope to further improve our understanding of how non-domain experts interpret uncertainty information depicted in map displays. This in turn will allow us to more clearly and legibly communicate uncertainty information in climate change maps, so that these displays can be unmistakably understood by decision-makers and the general public.
Cite as

Irene M. Johannsen, Sara Irina Fabrikant, and Mariele Evers. How Do Texture and Color Communicate Uncertainty in Climate Change Map Displays? (Short Paper). In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 37:1-37:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{johannsen_et_al:LIPIcs.GISCIENCE.2018.37,
  author =	{Johannsen, Irene M. and Fabrikant, Sara Irina and Evers, Mariele},
  title =	{{How Do Texture and Color Communicate Uncertainty in Climate Change Map Displays?}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{37:1--37:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-083-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{114},
  editor =	{Winter, Stephan and Griffin, Amy and Sester, Monika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.37},
  URN =		{urn:nbn:de:0030-drops-93655},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.37},
  annote =	{Keywords: uncertainty visualization, empirical study, visual variables, climate change}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.39
Faster Algorithms for Mean-Payoff Parity Games

Authors: Krishnendu Chatterjee, Monika Henzinger, and Alexander Svozil

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
Graph games provide the foundation for modeling and synthesis of reactive processes. Such games are played over graphs where the vertices are controlled by two adversarial players. We consider graph games where the objective of the first player is the conjunction of a qualitative objective (specified as a parity condition) and a quantitative objective (specified as a mean-payoff condition). There are two variants of the problem, namely, the threshold problem where the quantitative goal is to ensure that the mean-payoff value is above a threshold, and the value problem where the quantitative goal is to ensure the optimal mean-payoff value; in both cases ensuring the qualitative parity objective. The previous best-known algorithms for game graphs with n vertices, m edges, parity objectives with d priorities, and maximal absolute reward value W for mean-payoff objectives, are as follows: O(n^(d+1)·m·W) for the threshold problem, and O(n^(d+2)·m·W) for the value problem. Our main contributions are faster algorithms, and the running times of our algorithms are as follows: O(n^(d-1)·m·W) for the threshold problem, and O(n^d·m·W·log(n·W)) for the value problem. For mean-payoff parity objectives with two priorities, our algorithms match the best-known bounds of the algorithms for mean-payoff games (without conjunction with parity objectives). Our results are relevant in synthesis of reactive systems with both functional requirement (given as a qualitative objective) and performance requirement (given as a quantitative objective).
Cite as

Krishnendu Chatterjee, Monika Henzinger, and Alexander Svozil. Faster Algorithms for Mean-Payoff Parity Games. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 39:1-39:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.MFCS.2017.39,
  author =	{Chatterjee, Krishnendu and Henzinger, Monika and Svozil, Alexander},
  title =	{{Faster Algorithms for Mean-Payoff Parity Games}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{39:1--39:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.39},
  URN =		{urn:nbn:de:0030-drops-80809},
  doi =		{10.4230/LIPIcs.MFCS.2017.39},
  annote =	{Keywords: graph games, mean-payoff parity games}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.48
Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning

Authors: Monika Henzinger and Stefan Neumann

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
During the last 10 years it has become popular to study dynamic graph problems in a emergency planning or sensitivity setting: Instead of considering the general fully dynamic problem, we only have to process a single batch update of size d; after the update we have to answer queries. In this paper, we consider the dynamic subgraph connectivity problem with sensitivity d: We are given a graph of which some vertices are activated and some are deactivated. After that we get a single update in which the states of up to $d$ vertices are changed. Then we get a sequence of connectivity queries in the subgraph of activated vertices. We present the first fully dynamic algorithm for this problem which has an update and query time only slightly worse than the best decremental algorithm. In addition, we present the first incremental algorithm which is tight with respect to the best known conditional lower bound; moreover, the algorithm is simple and we believe it is implementable and efficient in practice.
Cite as

Monika Henzinger and Stefan Neumann. Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 48:1-48:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.ESA.2016.48,
  author =	{Henzinger, Monika and Neumann, Stefan},
  title =	{{Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{48:1--48:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.48},
  URN =		{urn:nbn:de:0030-drops-63607},
  doi =		{10.4230/LIPIcs.ESA.2016.48},
  annote =	{Keywords: connectivity, emergency planning, sensitivity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2463
Sponsored Search, Market Equilibria, and the Hungarian Method

Authors: Paul Dütting, Monika Henzinger, and Ingmar Weber

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
Two-sided matching markets play a prominent role in economic theory. A prime example of such a market is the sponsored search market where $n$ advertisers compete for the assignment of one of $k$ sponsored search results, also known as ``slots'', for certain keywords they are interested in. Here, as in other markets of that kind, market equilibria correspond to stable matchings. In this paper, we show how to modify Kuhn's Hungarian Method (Kuhn, 1955) so that it finds an optimal stable matching between advertisers and advertising slots in settings with generalized linear utilities, per-bidder-item reserve prices, and per-bidder-item maximum prices. The only algorithm for this problem presented so far (Aggarwal et al., 2009) requires the market to be in ``general position''. We do not make this assumption.
Cite as

Paul Dütting, Monika Henzinger, and Ingmar Weber. Sponsored Search, Market Equilibria, and the Hungarian Method. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 287-298, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{dutting_et_al:LIPIcs.STACS.2010.2463,
  author =	{D\"{u}tting, Paul and Henzinger, Monika and Weber, Ingmar},
  title =	{{Sponsored Search, Market Equilibria, and the Hungarian Method}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{287--298},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2463},
  URN =		{urn:nbn:de:0030-drops-24636},
  doi =		{10.4230/LIPIcs.STACS.2010.2463},
  annote =	{Keywords: Stable matching, truthful matching mechanism, general position}
}
Document
DOI: 10.4230/DagSemProc.08492.7
Representation of Operators in the Time-Frequency Domain and Generalzed Gabor Multipliers

Authors: Monika Dörfler and Bruno Torrésani

Published in: Dagstuhl Seminar Proceedings, Volume 8492, Structured Decompositions and Efficient Algorithms (2009)

Abstract
Starting from a general operator representation in the time-frequency domain, this paper addresses the problem of approximating linear operators by operators that are diagonal or band-diagonal with respect to Gabor frames. A haracterization of operators that can be realized as Gabor multipliers is given and necessary conditions for the existence of (Hilbert-Schmidt) optimal Gabor multiplier approximations are discussed and an efficient method for the calculation of an operator's best approximation by a Gabor multiplier is derived. The spreading function of Gabor multipliers yields new error estimates for these approximations. Generalizations (multiple Gabor multipliers) are introduced for better approximation of overspread operators. The Riesz property of the projection operators involved in generalized Gabor multipliers is characterized, and a method for obtaining an operator's best approximation by a multiple Gabor multiplier is suggested. Finally, it is shown that in certain situations, generalized Gabor multipliers reduce to a finite sum of regular Gabor multipliers with adapted windows.
Cite as

Monika Dörfler and Bruno Torrésani. Representation of Operators in the Time-Frequency Domain and Generalzed Gabor Multipliers. In Structured Decompositions and Efficient Algorithms. Dagstuhl Seminar Proceedings, Volume 8492, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{dorfler_et_al:DagSemProc.08492.7,
  author =	{D\"{o}rfler, Monika and Torr\'{e}sani, Bruno},
  title =	{{Representation of Operators in the Time-Frequency Domain and Generalzed Gabor Multipliers}},
  booktitle =	{Structured Decompositions and Efficient Algorithms},
  pages =	{1--28},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8492},
  editor =	{Stephan Dahlke and Ingrid Daubechies and Michal Elad and Gitta Kutyniok and Gerd Teschke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08492.7},
  URN =		{urn:nbn:de:0030-drops-18808},
  doi =		{10.4230/DagSemProc.08492.7},
  annote =	{Keywords: Operator approximation, generalized Gabor multipliers, spreading function, twisted convolution}
}
Document
DOI: 10.4230/DagSemProc.06101.2
06101 Report – Spatial Data: mining, processing and communicating

Authors: Jörg-Rüdiger Sack, Monika Sester, Michael Worboys, and Peter van Oosterom

Published in: Dagstuhl Seminar Proceedings, Volume 6101, Spatial Data: mining, processing and communicating (2006)

Abstract
This workshop has been organized as a successor to four preceding ones. The major goal has been to bring together experts from digital cartography, spatial modelling, computational geometry and cognitive science to meet with professionals from data mining and data interpretation. This has lead to a fruitful exchange of different – but very close – disciplines and hopefully to the creation of new collaborations. The Dagstuhl seminar has not only posed R&D problems, but provided crucial incentives and directions shaping the entire field. The group of participants was diverse both w.r.t. to their academic discipline and their professional background. Researchers and developers from within industry, government, and universities (senior and young) sha-red their latest topics, problems, doubts, and investigations.
Cite as

Jörg-Rüdiger Sack, Monika Sester, Michael Worboys, and Peter van Oosterom. 06101 Report – Spatial Data: mining, processing and communicating. In Spatial Data: mining, processing and communicating. Dagstuhl Seminar Proceedings, Volume 6101, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{sack_et_al:DagSemProc.06101.2,
  author =	{Sack, J\"{o}rg-R\"{u}diger and Sester, Monika and Worboys, Michael and van Oosterom, Peter},
  title =	{{06101 Report – Spatial Data: mining, processing and communicating}},
  booktitle =	{Spatial Data: mining, processing and communicating},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6101},
  editor =	{J\"{o}rg-R\"{u}diger Sack and Monika Sester and Peter van Oosterom and Michael Worboys},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06101.2},
  URN =		{urn:nbn:de:0030-drops-5908},
  doi =		{10.4230/DagSemProc.06101.2},
  annote =	{Keywords: Data mining, digital cartography, data interpretation, spatial data}
}
  • Refine by Author
  • 5 Henzinger, Monika
  • 2 Chatterjee, Krishnendu
  • 2 Neumann, Stefan
  • 2 Svozil, Alexander
  • 1 Bhattacharya, Devanjan
  • Show More...

  • Refine by Classification
  • 2 Information systems → Geographic information systems
  • 2 Theory of computation → Computational geometry
  • 1 Computing methodologies → Anomaly detection
  • 1 Human-centered computing → Contextual design
  • 1 Human-centered computing → Empirical studies in visualization
  • Show More...

  • Refine by Keyword
  • 1 Büchi
  • 1 Data Depth
  • 1 Data mining
  • 1 Dynamic algorithms
  • 1 Game Graphs
  • Show More...

  • Refine by Type
  • 12 document

  • Refine by Publication Year
  • 3 2018
  • 2 2021
  • 1 2006
  • 1 2009
  • 1 2010
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact