17 Search Results for "Dughmi, Shaddin"

Document
DOI: 10.4230/LIPIcs.STACS.2026.27
The Communication Complexity of Combinatorial Auctions in Graphs

Authors: George Christodoulou, Elias Koutsoupias, Annamária Kovács, and Ioannis Vlachos

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We study truthful and non-truthful protocols for combinatorial auctions in which every item can be allocated to one of two agents (multigraphs), or more generally to a fixed number of agents (hypergraphs). We show some tight - both positive and impossibility - results for the communication complexity of approximating the optimal social welfare for general monotone, subadditive, or XOS valuations.
Cite as

George Christodoulou, Elias Koutsoupias, Annamária Kovács, and Ioannis Vlachos. The Communication Complexity of Combinatorial Auctions in Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{christodoulou_et_al:LIPIcs.STACS.2026.27,
  author =	{Christodoulou, George and Koutsoupias, Elias and Kov\'{a}cs, Annam\'{a}ria and Vlachos, Ioannis},
  title =	{{The Communication Complexity of Combinatorial Auctions in Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{27:1--27:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.27},
  URN =		{urn:nbn:de:0030-drops-255163},
  doi =		{10.4230/LIPIcs.STACS.2026.27},
  annote =	{Keywords: Auctions, Communication Complexity, Mechanism Design, Graphs}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.51
Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems

Authors: Shaddin Dughmi, Yusuf Hakan Kalayci, and Xinyu Liu

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
When uncertainty meets costly information gathering, a fundamental question emerges: which data points should we probe to unlock near-optimal solutions? Sparsification of stochastic packing problems addresses this trade-off. The existing notions of sparsification measure the level of sparsity, called degree, as the ratio of queried items to the optimal solution size. While effective for matching and matroid-type problems with uniform structures, this cardinality-based approach fails for knapsack-type constraints where feasible sets exhibit dramatic structural variation. We introduce a polyhedral sparsification framework that measures the degree as the smallest scalar needed to embed the query set within a scaled feasibility polytope, naturally capturing redundancy without relying on cardinality. Our main contribution establishes that knapsack, multiple knapsack, and generalized assignment problems admit (1-ε)-approximate sparsifiers with degree polynomial in 1/p and 1/ε - where p denotes the independent activation probability of each element - remarkably independent of problem dimensions. The key insight involves grouping items with similar weights and deploying a charging argument: when our query set misses an optimal item, we either substitute it directly with a queried item from the same group or leverage that group’s excess contribution to compensate for the loss. This reveals an intriguing complexity-theoretic separation - while the multiple knapsack problem lacks an FPTAS and generalized assignment is APX-hard, their sparsification counterparts admit efficient (1-ε)-approximation algorithms that identify polynomial degree query sets. Finally, we raise an open question: can such sparsification extend to general integer linear programs with degree independent of problem dimensions?
Cite as

Shaddin Dughmi, Yusuf Hakan Kalayci, and Xinyu Liu. Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 51:1-51:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dughmi_et_al:LIPIcs.ITCS.2026.51,
  author =	{Dughmi, Shaddin and Kalayci, Yusuf Hakan and Liu, Xinyu},
  title =	{{Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{51:1--51:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.51},
  URN =		{urn:nbn:de:0030-drops-253386},
  doi =		{10.4230/LIPIcs.ITCS.2026.51},
  annote =	{Keywords: Packing Problems, Assignment Problems, Stochastic Selection, Sparsification}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.75
Prior-Independent and Subgame Optimal Online Algorithms

Authors: Jason Hartline, Aleck Johnsen, and Anant Shah

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
This paper develops two game-theoretic notions of beyond worst-case analysis that give better than worst-case guarantees on natural inputs. We illustrate them through the finite-horizon ski-rental problem. First, we consider prior-independent design and analysis of online algorithms where, rather than choosing a worst-case input, the adversary chooses a worst-case independent and identical distribution over inputs. Prior-independent online algorithms are generally analytically intractable; instead we give a fully polynomial-time approximation scheme to compute them. Second, we consider the worst-case design of algorithms. We define "subgame optimality" which is stronger than worst-case optimality in that it requires the algorithm to take advantage of an adversary not playing a worst-case input. Algorithms that focus only on the worst case can be far from subgame optimal. Highlighting the potential improvement from these paradigms for the finite-horizon ski-rental problem, we empirically compare worst-case, subgame optimal, and prior-independent algorithms in the prior-independent framework. Finally, we analyze the structure of their decisions across input sequences: the prior-independent algorithm exhibits more extreme adaptations to observed data, in contrast with the more conservative behavior of worst-case and subgame optimal algorithms.
Cite as

Jason Hartline, Aleck Johnsen, and Anant Shah. Prior-Independent and Subgame Optimal Online Algorithms. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 75:1-75:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hartline_et_al:LIPIcs.ITCS.2026.75,
  author =	{Hartline, Jason and Johnsen, Aleck and Shah, Anant},
  title =	{{Prior-Independent and Subgame Optimal Online Algorithms}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{75:1--75:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.75},
  URN =		{urn:nbn:de:0030-drops-253622},
  doi =		{10.4230/LIPIcs.ITCS.2026.75},
  annote =	{Keywords: online algorithms, prior-independent algorithm design, zero-sum games}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.58
One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts

Authors: Michal Feldman, Yoav Gal-Tzur, Tomasz Ponitka, and Maya Schlesinger

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We study multi-agent contract design with combinatorial actions, under budget constraints, and for a broad class of objective functions, including profit (principal’s utility), reward, and welfare. Our first result is a strong impossibility: For submodular reward functions, no randomized poly-time algorithm can approximate the optimal budget-feasible value within any finite factor, even with demand-oracle access. This result rules out extending known constant-factor guarantees from either (i) unbudgeted settings with combinatorial actions or (ii) budgeted settings with binary actions, to their combination. The hardness is tight: It holds even when all but one agent have binary actions and the remaining agent has just one additional action. On the positive side, we show that gross substitutes rewards (a well-studied strict subclass of submodular functions) admit a deterministic poly-time O(1)-approximation, using only value queries. Our results thus draw the first sharp separation between budgeted and unbudgeted settings in combinatorial contracts, and identifies gross substitutes as a tractable frontier for budgeted combinatorial contracts. Finally, we present an FPTAS for additive rewards, demonstrating that arbitrary approximation is tractable under any budget. This constitutes the first FPTAS for the multi-agent combinatorial-actions setting, even in the absence of budget constraints.
Cite as

Michal Feldman, Yoav Gal-Tzur, Tomasz Ponitka, and Maya Schlesinger. One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 58:1-58:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{feldman_et_al:LIPIcs.ITCS.2026.58,
  author =	{Feldman, Michal and Gal-Tzur, Yoav and Ponitka, Tomasz and Schlesinger, Maya},
  title =	{{One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{58:1--58:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.58},
  URN =		{urn:nbn:de:0030-drops-253459},
  doi =		{10.4230/LIPIcs.ITCS.2026.58},
  annote =	{Keywords: Combinatorial Contracts, Algorithmic Contract Design, Budget-Feasible Contracts}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.6
On the Complexity of Knapsack Under Explorable Uncertainty: Hardness and Algorithms

Authors: Jens Schlöter

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
In the knapsack problem under explorable uncertainty, we are given a knapsack instance with uncertain item profits. Instead of having access to the precise profits, we are only given uncertainty intervals that are guaranteed to contain the corresponding profits. The actual item profit can be obtained via a query. The goal of the problem is to adaptively query item profits until the revealed information suffices to compute an optimal (or approximate) solution to the underlying knapsack instance. Since queries are costly, the objective is to minimize the number of queries. In the offline variant of this problem, we assume knowledge of the precise profits and the task is to compute a query set of minimum cardinality that a third party without access to the profits could use to identify an optimal (or approximate) knapsack solution. We show that this offline variant is complete for the second-level of the polynomial hierarchy, i.e., Σ₂^p-complete, and cannot be approximated within a non-trivial factor unless Σ₂^p = Δ₂^p. Motivated by these strong hardness results, we consider a "resource-augmented" variant of the problem where the requirements on the query set computed by an algorithm are less strict than the requirements on the optimal solution we compare against. More precisely, a query set computed by the algorithm must reveal sufficient information to identify an approximate knapsack solution, while the optimal query set we compare against has to reveal sufficient information to identify an optimal solution. We show that this resource-augmented setting allows interesting non-trivial algorithmic results.
Cite as

Jens Schlöter. On the Complexity of Knapsack Under Explorable Uncertainty: Hardness and Algorithms. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schloter:LIPIcs.ESA.2025.6,
  author =	{Schl\"{o}ter, Jens},
  title =	{{On the Complexity of Knapsack Under Explorable Uncertainty: Hardness and Algorithms}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{6:1--6:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.6},
  URN =		{urn:nbn:de:0030-drops-244740},
  doi =		{10.4230/LIPIcs.ESA.2025.6},
  annote =	{Keywords: Explorable uncertainty, knapsack, queries, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.103
On the Satisfiability of Random 3-SAT Formulas with k-Wise Independent Clauses

Authors: Ioannis Caragiannis, Nick Gravin, and Zhile Jiang

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
The problem of identifying the satisfiability threshold of random 3-SAT formulas has received a lot of attention during the last decades and has inspired the study of other threshold phenomena in random combinatorial structures. The classical assumption in this line of research is that, for a given set of n Boolean variables, each clause is drawn uniformly at random among all sets of three literals from these variables, independently from other clauses. Here, we keep the uniform distribution of each clause, but deviate significantly from the independence assumption and consider richer families of probability distributions. For integer parameters n, m, and k, we denote by ℱ_k(n,m) the family of probability distributions that produce formulas with m clauses, each selected uniformly at random from all sets of three literals from the n variables, so that the clauses are k-wise independent. Our aim is to make general statements about the satisfiability or unsatisfiability of formulas produced by distributions in ℱ_k(n,m) for different values of the parameters n, m, and k. Our technical results are as follows: First, all probability distributions in ℱ₂(n,m) with m ∈ Ω(n³) return unsatisfiable formulas with high probability. This result is tight. We show that there exists a probability distribution 𝒟 ∈ ℱ₃(n,m) with m ∈ O(n³) so that a random formula drawn from 𝒟 is almost always satisfiable. In contrast, for m ∈ Ω(n²), any probability distribution 𝒟 ∈ ℱ₄(n,m) returns an unsatisfiable formula with high probability. This is our most surprising and technically involved result. Finally, for any integer k ≥ 2, any probability distribution 𝒟 ∈ ℱ_k(n,m) with m ∈ O(n^{1-1/k}) returns a satisfiable formula with high probability.
Cite as

Ioannis Caragiannis, Nick Gravin, and Zhile Jiang. On the Satisfiability of Random 3-SAT Formulas with k-Wise Independent Clauses. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 103:1-103:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{caragiannis_et_al:LIPIcs.ESA.2025.103,
  author =	{Caragiannis, Ioannis and Gravin, Nick and Jiang, Zhile},
  title =	{{On the Satisfiability of Random 3-SAT Formulas with k-Wise Independent Clauses}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{103:1--103:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.103},
  URN =		{urn:nbn:de:0030-drops-245721},
  doi =		{10.4230/LIPIcs.ESA.2025.103},
  annote =	{Keywords: Random 3-SAT, k-wise independence, Random bipartite graph}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.18
q-Partitioning Valuations: Exploring the Space Between Subadditive and Fractionally Subadditive Valuations

Authors: Kiril Bangachev and S. Matthew Weinberg

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
For a set M of m elements, we define a decreasing chain of classes of normalized monotone-increasing valuation functions from 2^M to ℝ_{≥ 0}, parameterized by an integer q ∈ [2,m]. For a given q, we refer to the class as q-partitioning. A valuation function is subadditive if and only if it is 2-partitioning, and fractionally subadditive if and only if it is m-partitioning. Thus, our chain establishes an interpolation between subadditive and fractionally subadditive valuations. We show that this interpolation is smooth (q-partitioning valuations are "nearly" (q-1)-partitioning in a precise sense, Theorem 6), interpretable (the definition arises by analyzing the core of a cost-sharing game, à la the Bondareva-Shapley Theorem for fractionally subadditive valuations, Section 3.1), and non-trivial (the class of q-partitioning valuations is distinct for all q, Proposition 3). For domains where provable separations exist between subadditive and fractionally subadditive, we interpolate the stronger guarantees achievable for fractionally subadditive valuations to all q ∈ {2,…, m}. Two highlights are the following: 1) An Ω ((log log q)/(log log m))-competitive posted price mechanism for q-partitioning valuations. Note that this matches asymptotically the state-of-the-art for both subadditive (q = 2) [Paul Dütting et al., 2020], and fractionally subadditive (q = m) [Feldman et al., 2015]. 2) Two upper-tail concentration inequalities on 1-Lipschitz, q-partitioning valuations over independent items. One extends the state-of-the-art for q = m to q < m, the other improves the state-of-the-art for q = 2 for q > 2. Our concentration inequalities imply several corollaries that interpolate between subadditive and fractionally subadditive, for example: 𝔼[v(S)] ≤ (1 + 1/log q)Median[v(S)] + O(log q). To prove this, we develop a new isoperimetric inequality using Talagrand’s method of control by q points, which may be of independent interest. We also discuss other probabilistic inequalities and game-theoretic applications of q-partitioning valuations, and connections to subadditive MPH-k valuations [Tomer Ezra et al., 2019].
Cite as

Kiril Bangachev and S. Matthew Weinberg. q-Partitioning Valuations: Exploring the Space Between Subadditive and Fractionally Subadditive Valuations. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bangachev_et_al:LIPIcs.ICALP.2025.18,
  author =	{Bangachev, Kiril and Weinberg, S. Matthew},
  title =	{{q-Partitioning Valuations: Exploring the Space Between Subadditive and Fractionally Subadditive Valuations}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{18:1--18:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.18},
  URN =		{urn:nbn:de:0030-drops-233956},
  doi =		{10.4230/LIPIcs.ICALP.2025.18},
  annote =	{Keywords: Subadditive Functions, Fractionally Subadditive Functions, Posted Price Mechanisms, Concentration Inequalities}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.137
Universal Online Contention Resolution with Preselected Order

Authors: Junyao Zhao

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Online contention resolution scheme (OCRS) is a powerful technique for online decision making, which - in the case of matroids - given a matroid and a prior distribution of active elements, selects a subset of active elements that satisfies the matroid constraint in an online fashion. OCRS has been studied mostly for product distributions in the literature. Recently, universal OCRS, that works even for correlated distributions, has gained interest, because it naturally generalizes the classic notion, and its existence in the random-order arrival model turns out to be equivalent to the matroid secretary conjecture. However, currently very little is known about how to design universal OCRSs for any arrival model. In this work, we consider a natural and relatively flexible arrival model, where the OCRS is allowed to preselect (i.e., non-adaptively select) the arrival order of the elements, and within this model, we design simple and optimal universal OCRSs that are computationally efficient. In the course of deriving our OCRSs, we also discover an efficient reduction from universal online contention resolution to the matroid secretary problem for any arrival model, answering a question posed in [Dughmi, 2020].
Cite as

Junyao Zhao. Universal Online Contention Resolution with Preselected Order. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 137:1-137:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{zhao:LIPIcs.ICALP.2025.137,
  author =	{Zhao, Junyao},
  title =	{{Universal Online Contention Resolution with Preselected Order}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{137:1--137:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.137},
  URN =		{urn:nbn:de:0030-drops-235147},
  doi =		{10.4230/LIPIcs.ICALP.2025.137},
  annote =	{Keywords: Matroids, online contention resolution schemes, secretary problems}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.67
Query Efficient Weighted Stochastic Matching

Authors: Mahsa Derakhshan and Mohammad Saneian

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In this paper, we study the weighted stochastic matching problem. Let G = (V, E) be a given edge-weighted graph, and let its realization 𝒢 be a random subgraph of G that includes each edge e ∈ E independently with a known probability p_e. The goal in this problem is to pick a sparse subgraph Q of G without prior knowledge of 𝒢, such that the maximum weight matching among the realized edges of Q (i.e., the subgraph Q ∩ 𝒢) in expectation approximates the maximum weight matching of the entire realization 𝒢. It is established by previous work that attaining any constant approximation ratio for this problem requires selecting a subgraph of max-degree Ω(1/p), where p = min_{e ∈ E} p_e. On the positive side, there exists a (1-ε)-approximation algorithm by Behnezhad and Derakhshan [FOCS'20], albeit at the cost of a max-degree having exponential dependence on 1/p. Within the O(1/p) query regime, however, the best-known algorithm achieves a 0.536 approximation ratio due to Dughmi, Kalayci, and Patel [ICALP'23], improving over the 0.501 approximation algorithm by Behnezhad, Farhadi, Hajiaghayi, and Reyhani [SODA'19]. In this work, we present a 0.68-approximation algorithm with the asymptotically optimal O(1/p) queries per vertex. Our result not only substantially improves the approximation ratio for weighted graphs, but also breaks the well-known 2/3 barrier with the optimal number of queries - even for unweighted graphs. Our analysis involves reducing the problem to designing a randomized matching algorithm on a given stochastic graph with some variance-bounding properties. To achieve these properties, we leverage a randomized algorithm by MacRury and Ma [STOC'24] for a variant of online stochastic matching.
Cite as

Mahsa Derakhshan and Mohammad Saneian. Query Efficient Weighted Stochastic Matching. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 67:1-67:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{derakhshan_et_al:LIPIcs.ICALP.2025.67,
  author =	{Derakhshan, Mahsa and Saneian, Mohammad},
  title =	{{Query Efficient Weighted Stochastic Matching}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{67:1--67:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.67},
  URN =		{urn:nbn:de:0030-drops-234445},
  doi =		{10.4230/LIPIcs.ICALP.2025.67},
  annote =	{Keywords: Sublinear algorithms, Stochastic, Matching}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.50
Designing Exploration Contracts

Authors: Martin Hoefer, Conrad Schecker, and Kevin Schewior

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We study a natural application of contract design in the context of sequential exploration problems. In our principal-agent setting, a search task is delegated to an agent. The agent performs a sequential exploration of n boxes, suffers the exploration cost for each inspected box, and selects the content (called the prize) of one inspected box as outcome. Agent and principal obtain an individual value based on the selected prize. To influence the search, the principal a-priori designs a contract with a non-negative payment to the agent for each potential prize. The goal of the principal is to maximize her expected reward, i.e., value minus payment. Interestingly, this natural contract scenario shares close relations with the Pandora’s Box problem. We show how to compute optimal contracts for the principal in several scenarios. A popular and important subclass is that of linear contracts, and we show how to compute optimal linear contracts in polynomial time. For general contracts, we obtain optimal contracts under the standard assumption that the agent suffers cost but obtains value only from the transfers by the principal. More generally, for general contracts with non-zero agent values for outcomes we show how to compute an optimal contract in two cases: (1) when each box has only one prize with non-zero value for principal and agent, (2) for i.i.d. boxes with a single prize with positive value for the principal.
Cite as

Martin Hoefer, Conrad Schecker, and Kevin Schewior. Designing Exploration Contracts. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 50:1-50:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hoefer_et_al:LIPIcs.STACS.2025.50,
  author =	{Hoefer, Martin and Schecker, Conrad and Schewior, Kevin},
  title =	{{Designing Exploration Contracts}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{50:1--50:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.50},
  URN =		{urn:nbn:de:0030-drops-228755},
  doi =		{10.4230/LIPIcs.STACS.2025.50},
  annote =	{Keywords: Exploration, Contract Design, Pandora’s Box Problem}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.41
Query Complexity of Stochastic Minimum Vertex Cover

Authors: Mahsa Derakhshan, Mohammad Saneian, and Zhiyang Xun

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We study the stochastic minimum vertex cover problem for general graphs. In this problem, we are given a graph G = (V, E) and an existence probability p_e for each edge e ∈ E. Edges of G are realized (or exist) independently with these probabilities, forming the realized subgraph 𝒢. The existence of an edge in 𝒢 can only be verified using edge queries. The goal of this problem is to find a near-optimal vertex cover of 𝒢 using a small number of queries. Previous work by Derakhshan, Durvasula, and Haghtalab [STOC 2023] established the existence of 1.5 + ε approximation algorithms for this problem with O(n/ε) queries. They also show that, under mild correlation among edge realizations, beating this approximation ratio requires querying a subgraph of size Ω(n ⋅ RS(n)). Here, RS(n) refers to Ruzsa-Szemerédi Graphs and represents the largest number of induced edge-disjoint matchings of size Θ(n) in an n-vertex graph. In this work, we design a simple algorithm for finding a (1 + ε) approximate vertex cover by querying a subgraph of size O(n ⋅ RS(n)) for any absolute constant ε > 0. Our algorithm can tolerate up to O(n ⋅ RS(n)) correlated edges, hence effectively completing our understanding of the problem under mild correlation.
Cite as

Mahsa Derakhshan, Mohammad Saneian, and Zhiyang Xun. Query Complexity of Stochastic Minimum Vertex Cover. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 41:1-41:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{derakhshan_et_al:LIPIcs.ITCS.2025.41,
  author =	{Derakhshan, Mahsa and Saneian, Mohammad and Xun, Zhiyang},
  title =	{{Query Complexity of Stochastic Minimum Vertex Cover}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{41:1--41:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.41},
  URN =		{urn:nbn:de:0030-drops-226691},
  doi =		{10.4230/LIPIcs.ITCS.2025.41},
  annote =	{Keywords: Sublinear algorithms, Vertex cover, Query complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.51
On Sparsification of Stochastic Packing Problems

Authors: Shaddin Dughmi, Yusuf Hakan Kalayci, and Neel Patel

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
Motivated by recent progress on stochastic matching with few queries, we embark on a systematic study of the sparsification of stochastic packing problems more generally. Specifically, we consider packing problems where elements are independently active with a given probability p, and ask whether one can (non-adaptively) compute a "sparse" set of elements guaranteed to contain an approximately optimal solution to the realized (active) subproblem. We seek structural and algorithmic results of broad applicability to such problems. Our focus is on computing sparse sets containing on the order of d feasible solutions to the packing problem, where d is linear or at most polynomial in 1/p. Crucially, we require d to be independent of the number of elements, or any parameter related to the "size" of the packing problem. We refer to d as the "degree" of the sparsifier, as is consistent with graph theoretic degree in the special case of matching. First, we exhibit a generic sparsifier of degree 1/p based on contention resolution. This sparsifier’s approximation ratio matches the best contention resolution scheme (CRS) for any packing problem for additive objectives, and approximately matches the best monotone CRS for submodular objectives. Second, we embark on outperforming this generic sparsifier for additive optimization over matroids and their intersections, as well as weighted matching. These improved sparsifiers feature different algorithmic and analytic approaches, and have degree linear in 1/p. In the case of a single matroid, our sparsifier tends to the optimal solution. In the case of weighted matching, we combine our contention-resolution-based sparsifier with technical approaches of prior work to improve the state of the art ratio from 0.501 to 0.536. Third, we examine packing problems with submodular objectives. We show that even the simplest such problems do not admit sparsifiers approaching optimality. We then outperform our generic sparsifier for some special cases with submodular objectives.
Cite as

Shaddin Dughmi, Yusuf Hakan Kalayci, and Neel Patel. On Sparsification of Stochastic Packing Problems. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 51:1-51:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dughmi_et_al:LIPIcs.ICALP.2023.51,
  author =	{Dughmi, Shaddin and Kalayci, Yusuf Hakan and Patel, Neel},
  title =	{{On Sparsification of Stochastic Packing Problems}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{51:1--51:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.51},
  URN =		{urn:nbn:de:0030-drops-181036},
  doi =		{10.4230/LIPIcs.ICALP.2023.51},
  annote =	{Keywords: Stochastic packing, sparsification, matroid}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.11
Multi-Channel Bayesian Persuasion

Authors: Yakov Babichenko, Inbal Talgam-Cohen, Haifeng Xu, and Konstantin Zabarnyi

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
The celebrated Bayesian persuasion model considers strategic communication between an informed agent (the sender) and uninformed decision makers (the receivers). The current rapidly-growing literature assumes a dichotomy: either the sender is powerful enough to communicate separately with each receiver (a.k.a. private persuasion), or she cannot communicate separately at all (a.k.a. public persuasion). We propose a model that smoothly interpolates between the two, by introducing a natural multi-channel communication structure in which each receiver observes a subset of the sender’s communication channels. This captures, e.g., receivers on a network, where information spillover is almost inevitable. Our main result is a complete characterization specifying when one communication structure is better for the sender than another, in the sense of yielding higher optimal expected utility universally over all prior distributions and utility functions. The characterization is based on a simple pairwise relation among receivers - one receiver information-dominates another if he observes at least the same channels. We prove that a communication structure M₁ is (weakly) better than M₂ if and only if every information-dominating pair of receivers in M₁ is also such in M₂. This result holds in the most general model of Bayesian persuasion in which receivers may have externalities - that is, the receivers' actions affect each other. The proof is cryptographic-inspired and it has a close conceptual connection to secret sharing protocols. As a surprising consequence of the main result, the sender can implement private Bayesian persuasion (which is the best communication structure for the sender) for k receivers using only O(log k) communication channels, rather than k channels in the naive implementation. We provide an implementation that matches the information-theoretical lower bound on the number of channels - not only asymptotically, but exactly. Moreover, the main result immediately implies some results of [Kerman and Tenev, 2021] on persuading receivers arranged in a network such that each receiver observes both the signals sent to him and to his neighbours in the network. We further provide an additive FPTAS for an optimal sender’s signaling scheme when the number of states of nature is constant, the sender has an additive utility function and the graph of the information-dominating pairs of receivers is a directed forest. We focus on a constant number of states, as even for the special case of public persuasion and additive sender’s utility, it was shown by [Shaddin Dughmi and Haifeng Xu, 2017] that one can achieve neither an additive PTAS nor a polynomial-time constant-factor optimal sender’s utility approximation (unless P=NP). We leave for future research studying exact tractability of forest communication structures, as well as generalizing our result to more families of sender’s utility functions and communication structures. Finally, we prove that finding an optimal signaling scheme under multi-channel persuasion is computationally hard for a general family of sender’s utility functions - separable supermajority functions, which are specified by choosing a partition of the set of receivers and summing supermajority functions corresponding to different elements of the partition, multiplied by some non-negative constants. Note that one can easily deduce from [Emir Kamenica and Matthew Gentzkow, 2011] and [Itai Arieli and Yakov Babichenko, 2019] that finding an optimal signaling scheme for such utility functions is computationally tractable for both public and private persuasion. This difference illustrates both the conceptual and the computational hardness of general multi-channel persuasion.
Cite as

Yakov Babichenko, Inbal Talgam-Cohen, Haifeng Xu, and Konstantin Zabarnyi. Multi-Channel Bayesian Persuasion. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 11:1-11:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{babichenko_et_al:LIPIcs.ITCS.2022.11,
  author =	{Babichenko, Yakov and Talgam-Cohen, Inbal and Xu, Haifeng and Zabarnyi, Konstantin},
  title =	{{Multi-Channel Bayesian Persuasion}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{11:1--11:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.11},
  URN =		{urn:nbn:de:0030-drops-156072},
  doi =		{10.4230/LIPIcs.ITCS.2022.11},
  annote =	{Keywords: Algorithmic game theory, Bayesian persuasion, Private Bayesian persuasion, Public Bayesian persuasion, Secret sharing, Networks}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.58
Matroid Secretary Is Equivalent to Contention Resolution

Authors: Shaddin Dughmi

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We show that the matroid secretary problem is equivalent to correlated contention resolution in the online random-order model. Specifically, the matroid secretary conjecture is true if and only if every matroid admits an online random-order contention resolution scheme which, given an arbitrary (possibly correlated) prior distribution over subsets of the ground set, matches the balance ratio of the best offline scheme for that distribution up to a constant. We refer to such a scheme as universal. Our result indicates that the core challenge of the matroid secretary problem lies in resolving contention for positively correlated inputs, in particular when the positive correlation is benign in as much as offline contention resolution is concerned. Our result builds on our previous work which establishes one direction of this equivalence, namely that the secretary conjecture implies universal random-order contention resolution, as well as a weak converse, which derives a matroid secretary algorithm from a random-order contention resolution scheme with only partial knowledge of the distribution. It is this weak converse that we strengthen in this paper: We show that universal random-order contention resolution for matroids, in the usual setting of a fully known prior distribution, suffices to resolve the matroid secretary conjecture in the affirmative.
Cite as

Shaddin Dughmi. Matroid Secretary Is Equivalent to Contention Resolution. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 58:1-58:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dughmi:LIPIcs.ITCS.2022.58,
  author =	{Dughmi, Shaddin},
  title =	{{Matroid Secretary Is Equivalent to Contention Resolution}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{58:1--58:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.58},
  URN =		{urn:nbn:de:0030-drops-156540},
  doi =		{10.4230/LIPIcs.ITCS.2022.58},
  annote =	{Keywords: Contention Resolution, Secretary Problems, Matroids}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.37
Delegated Stochastic Probing

Authors: Curtis Bechtel and Shaddin Dughmi

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

Abstract
Delegation covers a broad class of problems in which a principal doesn't have the resources or expertise necessary to complete a task by themselves, so they delegate the task to an agent whose interests may not be aligned with their own. Stochastic probing describes problems in which we are tasked with maximizing expected utility by "probing" known distributions for acceptable solutions subject to certain constraints. In this work, we combine the concepts of delegation and stochastic probing into a single mechanism design framework which we term delegated stochastic probing. We study how much a principal loses by delegating a stochastic probing problem, compared to their utility in the non-delegated solution. Our model and results are heavily inspired by the work of Kleinberg and Kleinberg in "Delegated Search Approximates Efficient Search." Building on their work, we show that there exists a connection between delegated stochastic probing and generalized prophet inequalities, which provides us with constant-factor deterministic mechanisms for a large class of delegated stochastic probing problems. We also explore randomized mechanisms in a simple delegated probing setting, and show that they outperform deterministic mechanisms in some instances but not in the worst case.
Cite as

Curtis Bechtel and Shaddin Dughmi. Delegated Stochastic Probing. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 37:1-37:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bechtel_et_al:LIPIcs.ITCS.2021.37,
  author =	{Bechtel, Curtis and Dughmi, Shaddin},
  title =	{{Delegated Stochastic Probing}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{37:1--37: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.37},
  URN =		{urn:nbn:de:0030-drops-135763},
  doi =		{10.4230/LIPIcs.ITCS.2021.37},
  annote =	{Keywords: Delegation, Mechanism Design, Algorithmic Game Theory}
}
  • Refine by Type
  • 17 Document/PDF
  • 11 Document/HTML

  • Refine by Publication Year
  • 4 2026
  • 7 2025
  • 1 2023
  • 2 2022
  • 1 2021
  • Show More...

  • Refine by Author
  • 6 Dughmi, Shaddin
  • 2 Derakhshan, Mahsa
  • 2 Kalayci, Yusuf Hakan
  • 2 Saneian, Mohammad
  • 1 Babichenko, Yakov
  • Show More...

  • Refine by Series/Journal
  • 17 LIPIcs

  • Refine by Classification
  • 4 Theory of computation → Design and analysis of algorithms
  • 3 Theory of computation → Algorithmic game theory
  • 3 Theory of computation → Algorithmic mechanism design
  • 2 Mathematics of computing → Probability and statistics
  • 2 Theory of computation → Computational pricing and auctions
  • Show More...

  • Refine by Keyword
  • 3 Matroids
  • 2 Contention Resolution
  • 2 Mechanism Design
  • 2 Secretary Problems
  • 2 Sublinear algorithms
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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