8 Search Results for "Mai, Tung"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.63
A Note on Approximating Weighted Nash Social Welfare with Additive Valuations

Authors: Yuda Feng and Shi Li

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We give the first O(1)-approximation for the weighted Nash Social Welfare problem with additive valuations. The approximation ratio we obtain is e^{1/e} + ε ≈ 1.445 + ε, which matches the best known approximation ratio for the unweighted case [Barman et al., 2018]. Both our algorithm and analysis are simple. We solve a natural configuration LP for the problem, and obtain the allocation of items to agents using a randomized version of the Shmoys-Tardos rounding algorithm developed for unrelated machine scheduling problems [Shmoys and Tardos, 1993]. In the analysis, we show that the approximation ratio of the algorithm is at most the worst gap between the Nash social welfare of the optimum allocation and that of an EF1 allocation, for an unweighted Nash Social Welfare instance with identical additive valuations. This was shown to be at most e^{1/e} ≈ 1.445 by Barman et al. [Barman et al., 2018], leading to our approximation ratio.
Cite as

Yuda Feng and Shi Li. A Note on Approximating Weighted Nash Social Welfare with Additive Valuations. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 63:1-63:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.ICALP.2024.63,
  author =	{Feng, Yuda and Li, Shi},
  title =	{{A Note on Approximating Weighted Nash Social Welfare with Additive Valuations}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{63:1--63:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.63},
  URN =		{urn:nbn:de:0030-drops-202068},
  doi =		{10.4230/LIPIcs.ICALP.2024.63},
  annote =	{Keywords: Nash Social Welfare, Configuration LP, Approximation Algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.96
Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets

Authors: Yasushi Kawase, Koichi Nishimura, and Hanna Sumita

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We study the problem of minimizing a given symmetric strictly convex function over the Minkowski sum of an integral base-polyhedron and an M-convex set. This problem has a hybrid of continuous and discrete structures. This emerges from the problem of allocating mixed goods, consisting of both divisible and indivisible goods, to agents with binary valuations so that the fairness measure, such as the Nash welfare, is maximized. It is known that both an integral base-polyhedron and an M-convex set have similar and nice properties, and the non-hybrid case can be solved in polynomial time. While the hybrid case lacks some of these properties, we show the structure of an optimal solution. Moreover, we exploit a proximity inherent in the problem. Through our findings, we demonstrate that our problem is NP-hard even in the fair allocation setting where all indivisible goods are identical. Moreover, we provide a polynomial-time algorithm for the fair allocation problem when all divisible goods are identical.
Cite as

Yasushi Kawase, Koichi Nishimura, and Hanna Sumita. Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 96:1-96:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kawase_et_al:LIPIcs.ICALP.2024.96,
  author =	{Kawase, Yasushi and Nishimura, Koichi and Sumita, Hanna},
  title =	{{Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{96:1--96:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.96},
  URN =		{urn:nbn:de:0030-drops-202393},
  doi =		{10.4230/LIPIcs.ICALP.2024.96},
  annote =	{Keywords: Integral base-polyhedron, Fair allocation, Matroid}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.79
From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP

Authors: Leonid Gurvits, Nathan Klein, and Jonathan Leake

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We give simply exponential lower bounds on the probabilities of a given strongly Rayleigh distribution, depending only on its expectation. This resolves a weak version of a problem left open by Karlin-Klein-Oveis Gharan in their recent breakthrough work on metric TSP, and this resolution leads to a minor improvement of their approximation factor for metric TSP. Our results also allow for a more streamlined analysis of the algorithm. To achieve these new bounds, we build upon the work of Gurvits-Leake on the use of the productization technique for bounding the capacity of a real stable polynomial. This technique allows one to reduce certain inequalities for real stable polynomials to products of affine linear forms, which have an underlying matrix structure. In this paper, we push this technique further by characterizing the worst-case polynomials via bipartitioned forests. This rigid combinatorial structure yields a clean induction argument, which implies our stronger bounds. In general, we believe the results of this paper will lead to further improvement and simplification of the analysis of various combinatorial and probabilistic bounds and algorithms.
Cite as

Leonid Gurvits, Nathan Klein, and Jonathan Leake. From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 79:1-79:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gurvits_et_al:LIPIcs.ICALP.2024.79,
  author =	{Gurvits, Leonid and Klein, Nathan and Leake, Jonathan},
  title =	{{From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{79:1--79:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.79},
  URN =		{urn:nbn:de:0030-drops-202229},
  doi =		{10.4230/LIPIcs.ICALP.2024.79},
  annote =	{Keywords: traveling salesman problem, strongly Rayleigh distributions, polynomial capacity, probability lower bounds, combinatorial lower bounds}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.19
A Structural and Algorithmic Study of Stable Matching Lattices of "Nearby" Instances, with Applications

Authors: Rohith Reddy Gangam, Tung Mai, Nitya Raju, and Vijay V. Vazirani

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
Recently [Mai and Vazirani, 2018] identified and initiated work on a new problem, namely understanding structural relationships between the lattices of solutions of two "nearby" instances of stable matching. They also gave an application of their work to finding a robust stable matching. However, the types of changes they allowed in going from instance A to B were very restricted, namely any one agent executes an upward shift. In this paper, we allow any one agent to permute its preference list arbitrarily. Let M_A and M_B be the sets of stable matchings of the resulting pair of instances A and B, and let ℒ_A and ℒ_B be the corresponding lattices of stable matchings. We prove that the matchings in M_A ∩ M_B form a sublattice of both ℒ_A and ℒ_B and those in M_A ⧵ M_B form a join semi-sublattice. These properties enable us to obtain a polynomial time algorithm for not only finding a stable matching in M_A ∩ M_B, but also for obtaining the partial order, as promised by Birkhoff’s Representation Theorem [Birkhoff, 1937]. As a result, we can generate all matchings in this sublattice. Our algorithm also helps solve a version of the robust stable matching problem. We discuss another potential application, namely obtaining new insights into the incentive compatibility properties of the Gale-Shapley Deferred Acceptance Algorithm.
Cite as

Rohith Reddy Gangam, Tung Mai, Nitya Raju, and Vijay V. Vazirani. A Structural and Algorithmic Study of Stable Matching Lattices of "Nearby" Instances, with Applications. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 19:1-19:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gangam_et_al:LIPIcs.FSTTCS.2022.19,
  author =	{Gangam, Rohith Reddy and Mai, Tung and Raju, Nitya and Vazirani, Vijay V.},
  title =	{{A Structural and Algorithmic Study of Stable Matching Lattices of "Nearby" Instances, with Applications}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{19:1--19:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.19},
  URN =		{urn:nbn:de:0030-drops-174114},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.19},
  annote =	{Keywords: stable matching, robust solutions, finite distributive lattice, Birkhoff’s Representation Theorem}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.59
Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets

Authors: Vijay V. Vazirani and Mihalis Yannakakis

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
In 1979, Hylland and Zeckhauser [Hylland and Zeckhauser, 1979] gave a simple and general scheme for implementing a one-sided matching market using the power of a pricing mechanism. Their method has nice properties - it is incentive compatible in the large and produces an allocation that is Pareto optimal - and hence it provides an attractive, off-the-shelf method for running an application involving such a market. With matching markets becoming ever more prevalent and impactful, it is imperative to finally settle the computational complexity of this scheme. We present the following partial resolution: 1) A combinatorial, strongly polynomial time algorithm for the dichotomous case, i.e., 0/1 utilities, and more generally, when each agent’s utilities come from a bi-valued set. 2) An example that has only irrational equilibria, hence proving that this problem is not in PPAD. 3) A proof of membership of the problem in the class FIXP. 4) A proof of membership of the problem of computing an approximate HZ equilibrium in the class PPAD. We leave open the (difficult) questions of determining if computing an exact HZ equilibrium is FIXP-hard and an approximate HZ equilibrium is PPAD-hard.
Cite as

Vijay V. Vazirani and Mihalis Yannakakis. Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 59:1-59:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{vazirani_et_al:LIPIcs.ITCS.2021.59,
  author =	{Vazirani, Vijay V. and Yannakakis, Mihalis},
  title =	{{Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{59:1--59:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.59},
  URN =		{urn:nbn:de:0030-drops-135987},
  doi =		{10.4230/LIPIcs.ITCS.2021.59},
  annote =	{Keywords: Hyland-Zeckhauser scheme, one-sided matching markets, mechanism design, dichotomous utilities, PPAD, FIXP}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2020.21
Stability-Preserving, Time-Efficient Mechanisms for School Choice in Two Rounds

Authors: Karthik Gajulapalli, James A. Liu, Tung Mai, and Vijay V. Vazirani

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract
We address the following dynamic version of the school choice question: a city, named City, admits students in two temporally-separated rounds, denoted R₁ and R₂. In round R₁, the capacity of each school is fixed and mechanism M₁ finds a student optimal stable matching. In round R₂, certain parameters change, e.g., new students move into the City or the City is happy to allocate extra seats to specific schools. We study a number of Settings of this kind and give polynomial time algorithms for obtaining a stable matching for the new situations. It is well established that switching the school of a student midway, unsynchronized with her classmates, can cause traumatic effects. This fact guides us to two types of results: the first simply disallows any re-allocations in round R₂, and the second asks for a stable matching that minimizes the number of re-allocations. For the latter, we prove that the stable matchings which minimize the number of re-allocations form a sublattice of the lattice of stable matchings. Observations about incentive compatibility are woven into these results. We also give a third type of results, namely proofs of NP-hardness for a mechanism for round R₂ under certain settings.
Cite as

Karthik Gajulapalli, James A. Liu, Tung Mai, and Vijay V. Vazirani. Stability-Preserving, Time-Efficient Mechanisms for School Choice in Two Rounds. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gajulapalli_et_al:LIPIcs.FSTTCS.2020.21,
  author =	{Gajulapalli, Karthik and Liu, James A. and Mai, Tung and Vazirani, Vijay V.},
  title =	{{Stability-Preserving, Time-Efficient Mechanisms for School Choice in Two Rounds}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.21},
  URN =		{urn:nbn:de:0030-drops-132626},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.21},
  annote =	{Keywords: stable matching, mechanism design, NP-Hardness}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.60
Finding Stable Matchings That Are Robust to Errors in the Input

Authors: Tung Mai and Vijay V. Vazirani

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
In this paper, we introduce the issue of finding solutions to the stable matching problem that are robust to errors in the input and we obtain the first algorithmic results on this topic. In the process, we also initiate work on a new structural question concerning the stable matching problem, namely finding relationships between the lattices of solutions of two "nearby" instances. Our main algorithmic result is the following: We identify a polynomially large class of errors, D, that can be introduced in a stable matching instance. Given an instance A of stable matching, let B be the instance that results after introducing one error from D, chosen via a discrete probability distribution. The problem is to find a stable matching for A that maximizes the probability of being stable for B as well. Via new structural properties of the type described in the question stated above, we give a polynomial time algorithm for this problem.
Cite as

Tung Mai and Vijay V. Vazirani. Finding Stable Matchings That Are Robust to Errors in the Input. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 60:1-60:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{mai_et_al:LIPIcs.ESA.2018.60,
  author =	{Mai, Tung and Vazirani, Vijay V.},
  title =	{{Finding Stable Matchings That Are Robust to Errors in the Input}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{60:1--60:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.60},
  URN =		{urn:nbn:de:0030-drops-95238},
  doi =		{10.4230/LIPIcs.ESA.2018.60},
  annote =	{Keywords: Stable Matching, Robust}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.140
Opinion Dynamics in Networks: Convergence, Stability and Lack of Explosion

Authors: Tung Mai, Ioannis Panageas, and Vijay V. Vazirani

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
Inspired by the work of Kempe et al. [Kempe, Kleinberg, Oren, Slivkins, EC 2013], we introduce and analyze a model on opinion formation; the update rule of our dynamics is a simplified version of that of [Kempe, Kleinberg, Oren, Slivkins, EC 2013]. We assume that the population is partitioned into types whose interaction pattern is specified by a graph. Interaction leads to population mass moving from types of smaller mass to those of bigger mass. We show that starting uniformly at random over all population vectors on the simplex, our dynamics converges point-wise with probability one to an independent set. This settles an open problem of [Kempe, Kleinberg, Oren, Slivkins, EC 2013], as applicable to our dynamics. We believe that our techniques can be used to settle the open problem for the Kempe et al. dynamics as well. Next, we extend the model of Kempe et al. by introducing the notion of birth and death of types, with the interaction graph evolving appropriately. Birth of types is determined by a Bernoulli process and types die when their population mass is less than epsilon (a parameter). We show that if the births are infrequent, then there are long periods of "stability" in which there is no population mass that moves. Finally we show that even if births are frequent and "stability" is not attained, the total number of types does not explode: it remains logarithmic in 1/epsilon.
Cite as

Tung Mai, Ioannis Panageas, and Vijay V. Vazirani. Opinion Dynamics in Networks: Convergence, Stability and Lack of Explosion. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 140:1-140:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{mai_et_al:LIPIcs.ICALP.2017.140,
  author =	{Mai, Tung and Panageas, Ioannis and Vazirani, Vijay V.},
  title =	{{Opinion Dynamics in Networks: Convergence, Stability and Lack of Explosion}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{140:1--140:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.140},
  URN =		{urn:nbn:de:0030-drops-74440},
  doi =		{10.4230/LIPIcs.ICALP.2017.140},
  annote =	{Keywords: Opinion Dynamics, Convergence, Jacobian, Center-stable Manifold}
}
  • Refine by Author
  • 5 Vazirani, Vijay V.
  • 4 Mai, Tung
  • 1 Feng, Yuda
  • 1 Gajulapalli, Karthik
  • 1 Gangam, Rohith Reddy
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Algorithmic game theory
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Probability and statistics
  • Show More...

  • Refine by Keyword
  • 2 mechanism design
  • 2 stable matching
  • 1 Approximation Algorithms
  • 1 Birkhoff’s Representation Theorem
  • 1 Center-stable Manifold
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 3 2024
  • 1 2017
  • 1 2018
  • 1 2020
  • 1 2021
  • Show More...

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact