BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Marek Adamczyk

Marek Adamczyk appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputer Science and Game Theory

Catalog footprint

What is connected

6works
2topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

6 published item(s)

preprint2015arXiv

Improved Approximation Algorithms for Stochastic Matching

In this paper we consider the Stochastic Matching problem, which is motivated by applications in kidney exchange and online dating. We are given an undirected graph in which every edge is assigned a probability of existence and a positive profit, and each node is assigned a positive integer called timeout. We know whether an edge exists or not only after probing it. On this random graph we are executing a process, which one-by-one probes the edges and gradually constructs a matching. The process is constrained in two ways: once an edge is taken it cannot be removed from the matching, and the timeout of node $v$ upper-bounds the number of edges incident to $v$ that can be probed. The goal is to maximize the expected profit of the constructed matching. For this problem Bansal et al. (Algorithmica 2012) provided a $3$-approximation algorithm for bipartite graphs, and a $4$-approximation for general graphs. In this work we improve the approximation factors to $2.845$ and $3.709$, respectively. We also consider an online version of the bipartite case, where one side of the partition arrives node by node, and each time a node $b$ arrives we have to decide which edges incident to $b$ we want to probe, and in which order. Here we present a $4.07$-approximation, improving on the $7.92$-approximation of Bansal et al. The main technical ingredient in our result is a novel way of probing edges according to a random but non-uniform permutation. Patching this method with an algorithm that works best for large probability edges (plus some additional ideas) leads to our improved approximation factors.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Non-negative submodular stochastic probing via stochastic contention resolution schemes

The abstract model of stochastic probing was presented by Gupta and Nagarajan (IPCO'13), and provides a unified view of a number of problems. Adamczyk, Sviridenko, Ward (STACS'14) gave better approximation for matroid environments and linear objectives. At the same time this method was easily extendable to settings, where the objective function was monotone submodular. However, the case of non-negative submodular function could not be handled by previous techniques. In this paper we address this problem, and our results are twofold. First, we adapt the notion of contention resolution schemes of Chekuri, Vondrák, Zenklusen (SICOMP'14) to show that we can optimize non-negative submodular functions in this setting with a constant factor loss with respect to the deterministic setting. Second, we show a new contention resolution scheme for transversal matroids, which yields better approximations in the stochastic probing setting than the previously known tools. The rounding procedure underlying the scheme can be of independent interest --- Bansal, Gupta, Li, Mestre, Nagarajan, Rudra (Algorithmica'12) gave two seemingly different algorithms for stochastic matching and stochastic $k$-set packing problems with two different analyses, but we show that our single technique can be used to analyze both their algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Sequential Posted Price Mechanisms with Correlated Valuations

We study the revenue performance of sequential posted price mechanisms and some natural extensions, for a general setting where the valuations of the buyers are drawn from a correlated distribution. Sequential posted price mechanisms are conceptually simple mechanisms that work by proposing a take-it-or-leave-it offer to each buyer. We apply sequential posted price mechanisms to single-parameter multi-unit settings in which each buyer demands only one item and the mechanism can assign the service to at most k of the buyers. For standard sequential posted price mechanisms, we prove that with the valuation distribution having finite support, no sequential posted price mechanism can extract a constant fraction of the optimal expected revenue, even with unlimited supply. We extend this result to the the case of a continuous valuation distribution when various standard assumptions hold simultaneously. In fact, it turns out that the best fraction of the optimal revenue that is extractable by a sequential posted price mechanism is proportional to ratio of the highest and lowest possible valuation. We prove that for two simple generalizations of these mechanisms, a better revenue performance can be achieved: if the sequential posted price mechanism has for each buyer the option of either proposing an offer or asking the buyer for its valuation, then a Omega(1/max{1,d}) fraction of the optimal revenue can be extracted, where d denotes the degree of dependence of the valuations, ranging from complete independence (d=0) to arbitrary dependence (d=n-1). Moreover, when we generalize the sequential posted price mechanisms further, such that the mechanism has the ability to make a take-it-or-leave-it offer to the i-th buyer that depends on the valuations of all buyers except i's, we prove that a constant fraction (2-sqrt{e})/4~0.088 of the optimal revenue can be always be extracted.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Efficiency of Truthful and Symmetric Mechanisms in One-sided Matching

We study the efficiency (in terms of social welfare) of truthful and symmetric mechanisms in one-sided matching problems with {\em dichotomous preferences} and {\em normalized von Neumann-Morgenstern preferences}. We are particularly interested in the well-known {\em Random Serial Dictatorship} mechanism. For dichotomous preferences, we first show that truthful, symmetric and optimal mechanisms exist if intractable mechanisms are allowed. We then provide a connection to online bipartite matching. Using this connection, it is possible to design truthful, symmetric and tractable mechanisms that extract 0.69 of the maximum social welfare, which works under assumption that agents are not adversarial. Without this assumption, we show that Random Serial Dictatorship always returns an assignment in which the expected social welfare is at least a third of the maximum social welfare. For normalized von Neumann-Morgenstern preferences, we show that Random Serial Dictatorship always returns an assignment in which the expected social welfare is at least $\frac{1}{e}\frac{ν(\opt)^2}{n}$, where $ν(\opt)$ is the maximum social welfare and $n$ is the number of both agents and items. On the hardness side, we show that no truthful mechanism can achieve a social welfare better than $\frac{ν(\opt)^2}{n}$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Submodular Stochastic Probing on Matroids

In a stochastic probing problem we are given a universe $E$, where each element $e \in E$ is active independently with probability $p_e$, and only a probe of e can tell us whether it is active or not. On this universe we execute a process that one by one probes elements --- if a probed element is active, then we have to include it in the solution, which we gradually construct. Throughout the process we need to obey inner constraints on the set of elements taken into the solution, and outer constraints on the set of all probed elements. This abstract model was presented by Gupta and Nagarajan (IPCO '13), and provides a unified view of a number of problems. Thus far, all the results falling under this general framework pertain mainly to the case in which we are maximizing a linear objective function of the successfully probed elements. In this paper we generalize the stochastic probing problem by considering a monotone submodular objective function. We give a $(1 - 1/e)/(k_{in} + k_{out}+1)$-approximation algorithm for the case in which we are given $k_{in}$ matroids as inner constraints and $k_{out}$ matroids as outer constraints. Additionally, we obtain an improved $1/(k_{in} + k_{out})$-approximation algorithm for linear objective functions.

0 citations0 reviewsNo code linkedOpen access