FOCS

\documentclass[conference]{IEEEtran}
\IEEEoverridecommandlockouts
\usepackage{cite}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{hyperref}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\begin{document}

\title{Tight Bounds for Online Matching\\under Stochastic Arrivals}

\author{\IEEEauthorblockN{First Last}
\IEEEauthorblockA{\textit{University of Example}\\[email protected]}
\and
\IEEEauthorblockN{Jane Doe}
\IEEEauthorblockA{\textit{Example Research Labs}\\[email protected]}}

\maketitle

\begin{abstract}
We resolve the competitive ratio for online bipartite matching under
stochastic arrivals, closing a long-standing gap between $1 - 1/e$ and
the optimal bound. Our main result is an algorithm achieving a ratio of
$0.712$, matched by a new upper bound of $0.712$ via a construction
based on random regular graphs.
\end{abstract}

\section{Introduction}
The i.i.d. model has received much recent attention, with lower bounds
converging to $\approx 0.71$ but upper bounds remaining at $0.729$.

\begin{theorem}\label{thm:algo}
There is an online algorithm achieving competitive ratio $0.712$ on
the i.i.d. stochastic arrival model.
\end{theorem}

\begin{theorem}\label{thm:lb}
No online algorithm achieves competitive ratio better than $0.712$ on
the i.i.d. stochastic arrival model.
\end{theorem}

\section{Preliminaries}
\begin{definition}
An input is a bipartite graph $G = (L \cup R, E)$ with $|L|=|R|=n$ where
$R$ arrives online with each vertex drawn i.i.d. from distribution
$\mathcal{D}$.
\end{definition}

\section{Upper Bound}
We analyze a new algorithm based on scaled primal-dual with type-level
regularization.

\begin{lemma}
The scaled primal-dual algorithm achieves competitive ratio
$1 - h(p^*)$ for a carefully chosen threshold function $h$.
\end{lemma}

\section{Lower Bound}
The lower bound uses a reduction from online matching to a structured
random graph problem.

\section{Open Problems}
Generalizing to correlated arrivals and graphs of unbounded degree.

\bibliographystyle{IEEEtran}
\bibliography{refs}
\end{document}