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

Amin Saberi

Amin Saberi 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 Algorithmsmath.PRDiscrete MathematicsComputational ComplexityComputer Science and Game Theoryecon.THmath.COmath.OCphysics.soc-phSocial and Information Networks

Catalog footprint

What is connected

12works
10topics
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

12 published item(s)

preprint2022arXiv

Beating Greedy Matching in Sublinear Time

We study sublinear time algorithms for estimating the size of maximum matching in graphs. Our main result is a $(\frac{1}{2}+Ω(1))$-approximation algorithm which can be implemented in $O(n^{1+ε})$ time, where $n$ is the number of vertices and the constant $ε> 0$ can be made arbitrarily small. The best known lower bound for the problem is $Ω(n)$, which holds for any constant approximation. Existing algorithms either obtain the greedy bound of $\frac{1}{2}$-approximation [Behnezhad FOCS'21], or require some assumption on the maximum degree to run in $o(n^2)$-time [Yoshida, Yamamoto, and Ito STOC'09]. We improve over these by designing a less "adaptive" augmentation algorithm for maximum matching that might be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Improved Online Contention Resolution for Matchings and Applications to the Gig Economy

Motivated by applications in the gig economy, we study approximation algorithms for a \emph{sequential pricing problem}. The input is a bipartite graph $G=(I,J,E)$ between individuals $I$ and jobs $J$. The platform has a value of $v_j$ for matching job $j$ to an individual worker. In order to find a matching, the platform can consider the edges $(i j) \in E$ in any order and make a one-time take-it-or-leave-it offer of a price $π_{ij} = w$ of its choosing to $i$ for completing $j$. The worker accepts the offer with a known probability $ p_{ijw} $; in this case the job and the worker are irrevocably matched. What is the best way to make offers to maximize revenue and/or social welfare? The optimal algorithm is known to be NP-hard to compute (even if there is only a single job). With this in mind, we design efficient approximations to the optimal policy via a new Random-Order Online Contention Resolution Scheme (RO-OCRS) for matching. Our main result is a 0.456-balanced RO-OCRS in bipartite graphs and a 0.45-balanced RO-OCRS in general graphs. These algorithms improve on the recent bound of $\frac{1}{2}(1-e^{-2})\approx 0.432$ of [BGMS21], and improve on the best known lower bounds for the correlation gap of matching, despite applying to a significantly more restrictive setting. As a consequence of our OCRS results, we obtain a $0.456$-approximate algorithm for the sequential pricing problem. We further extend our results to settings where workers can only be contacted a limited number of times, and show how to achieve improved results for this problem, via improved algorithms for the well-studied stochastic probing problem.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Locality of Random Digraphs on Expanders

We study random digraphs on sequences of expanders with bounded average degree {which converge locally in probability}. We prove that the threshold for the existence of a giant strongly connected component, as well as the asymptotic fraction of nodes with giant fan-in or nodes with giant fan-out are local, in the sense that they are the same for two sequences with the same local limit. The digraph has a bow-tie structure, with all but a vanishing fraction of nodes lying either in the unique strongly connected giant and its fan-in and fan-out, or in sets with small fan-in and small fan-out. All local quantities are expressed in terms of percolation on the limiting rooted graph, without any structural assumptions on the limit, allowing, in particular, for non tree-like graphs. {In the course of establishing these results, we generalize previous results on the locality of the size of the giant to expanders of bounded average degree with possibly non-tree like limits. We also show that regardless of the local convergence of a sequence, the uniqueness of the giant and convergence of its relative size for unoriented percolation imply the bow-tie structure for directed percolation.} An application of our methods shows that the critical threshold for bond percolation and random digraphs on preferential attachment graphs is $p_c=0$, with an infinite order phase transition at $p_c$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Sequential importance sampling for estimating expectations over the space of perfect matchings

This paper makes three contributions to estimating the number of perfect matching in bipartite graphs. First, we prove that the popular sequential importance sampling algorithm works in polynomial time for dense bipartite graphs. More carefully, our algorithm gives a $(1\pmε)$-approximation for the number of perfect matchings of a $λ$-dense bipartite graph, using $O(n^{\frac{1-2λ}λε^{-2}})$ samples. With size $n$ on each side and for $\frac{1}{2}>λ>0$, a $λ$-dense bipartite graph has all degrees greater than $(λ+\frac{1}{2})n$. Second, practical applications of the algorithm require many calls to matching algorithms. A novel preprocessing step is provided which makes significant improvements. Third, three applications are provided. The first is for counting Latin squares, the second is a practical way of computing the greedy algorithm for a card-guessing game with feedback, and the third is for stochastic block models. In all three examples, sequential importance sampling allows treating practical problems of reasonably large sizes.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Tiered Random Matching Markets: Rank is Proportional to Popularity

We study the stable marriage problem in two-sided markets with randomly generated preferences. We consider agents on each side divided into a constant number of "soft tiers", which intuitively indicate the quality of the agent. Specifically, every agent within a tier has the same public score, and agents on each side have preferences independently generated proportionally to the public scores of the other side. We compute the expected average rank which agents in each tier have for their partners in the men-optimal stable matching, and prove concentration results for the average rank in asymptotically large markets. Furthermore, we show that despite having a significant effect on ranks, public scores do not strongly influence the probability of an agent matching to a given tier of the other side. This generalizes results of [Pittel 1989] which correspond to uniform preferences. The results quantitatively demonstrate the effect of competition due to the heterogeneous attractiveness of agents in the market, and we give the first explicit calculations of rank beyond uniform markets.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Nash Social Welfare, Matrix Permanent, and Stable Polynomials

We study the problem of allocating $m$ items to $n$ agents subject to maximizing the Nash social welfare (NSW) objective. We write a novel convex programming relaxation for this problem, and we show that a simple randomized rounding algorithm gives a $1/e$ approximation factor of the objective. Our main technical contribution is an extension of Gurvits's lower bound on the coefficient of the square-free monomial of a degree $m$-homogeneous stable polynomial on $m$ variables to all homogeneous polynomials. We use this extension to analyze the expected welfare of the allocation returned by our randomized rounding algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Asymptotic behavior and distributional limits of preferential attachment graphs

We give an explicit construction of the weak local limit of a class of preferential attachment graphs. This limit contains all local information and allows several computations that are otherwise hard, for example, joint degree distributions and, more generally, the limiting distribution of subgraphs in balls of any given radius $k$ around a random vertex in the preferential attachment graph. We also establish the finite-volume corrections which give the approach to the limit.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A Sequential Algorithm for Generating Random Graphs

We present a nearly-linear time algorithm for counting and randomly generating simple graphs with a given degree sequence in a certain range. For degree sequence $(d_i)_{i=1}^n$ with maximum degree $d_{\max}=O(m^{1/4-τ})$, our algorithm generates almost uniform random graphs with that degree sequence in time $O(m\,d_{\max})$ where $m=\f{1}{2}\sum_id_i$ is the number of edges in the graph and $τ$ is any positive constant. The fastest known algorithm for uniform generation of these graphs McKay Wormald (1990) has a running time of $O(m^2d_{\max}^2)$. Our method also gives an independent proof of McKay's estimate McKay (1985) for the number of such graphs. We also use sequential importance sampling to derive fully Polynomial-time Randomized Approximation Schemes (FPRAS) for counting and uniformly generating random graphs for the same range of $d_{\max}=O(m^{1/4-τ})$. Moreover, we show that for $d = O(n^{1/2-τ})$, our algorithm can generate an asymptotically uniform $d$-regular graph. Our results improve the previous bound of $d = O(n^{1/3-τ})$ due to Kim and Vu (2004) for regular graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Message Passing Algorithms for Sparse Network Alignment

Network alignment generalizes and unifies several approaches for forming a matching or alignment between the vertices of two graphs. We study a mathematical programming framework for network alignment problem and a sparse variation of it where only a small number of matches between the vertices of the two graphs are possible. We propose a new message passing algorithm that allows us to compute, very efficiently, approximate solutions to the sparse network alignment problems with graph sizes as large as hundreds of thousands of vertices. We also provide extensive simulations comparing our algorithms with two of the best solvers for network alignment problems on two synthetic matching problems, two bioinformatics problems, and three large ontology alignment problems including a multilingual problem with a known labeled alignment.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Online Stochastic Matching: Online Actions Based on Offline Statistics

We consider the online stochastic matching problem proposed by Feldman et al. [FMMM09] as a model of display ad allocation. We are given a bipartite graph; one side of the graph corresponds to a fixed set of bins and the other side represents the set of possible ball types. At each time step, a ball is sampled independently from the given distribution and it needs to be matched upon its arrival to an empty bin. The goal is to maximize the number of allocations. We present an online algorithm for this problem with a competitive ratio of 0.702. Before our result, algorithms with a competitive ratio better than $1-1/e$ were known under the assumption that the expected number of arriving balls of each type is integral. A key idea of the algorithm is to collect statistics about the decisions of the optimum offline solution using Monte Carlo sampling and use those statistics to guide the decisions of the online algorithm. We also show that our algorithm achieves a competitive ratio of 0.705 when the rates are integral. On the hardness side, we prove that no online algorithm can have a competitive ratio better than 0.823 under the known distribution model (and henceforth under the permutation model). This improves upon the 5/6 hardness result proved by Goel and Mehta \cite{GM08} for the permutation model.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Prisoner's Dilemma on Graphs with Large Girth

We study the evolution of cooperation in populations where individuals play prisoner's dilemma on a network. Every node of the network corresponds on an individual choosing whether to cooperate or defect in a repeated game. The players revise their actions by imitating those neighbors who have higher payoffs. We show that when the interactions take place on graphs with large girth, cooperation is more likely to emerge. On the flip side, in graphs with many cycles of length 3 and 4, defection spreads more rapidly. One of the key ideas of our analysis is that our dynamics can be seen as a perturbation of the voter model. We write the transition kernel of the corresponding Markov chain in terms of the pairwise correlations in the voter model. We analyze the pairwise correlation and show that in graphs with relatively large girth, cooperators cluster and help each other.

0 citations0 reviewsNo code linkedOpen access