Search Results

Documents authored by MacRury, Calum

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.29
A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process

Authors: Pu Gao, Calum MacRury, and Paweł Prałat

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
The semi-random graph process is a single player game in which the player is initially presented an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v, and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a Hamiltonian cycle in as few rounds as possible. In particular, we present an adaptive strategy for the player which achieves it in α n rounds, where α < 2.01678 is derived from the solution to some system of differential equations. We also show that the player cannot achieve the desired property in less than β n rounds, where β > 1.26575. These results improve the previously best known bounds and, as a result, the gap between the upper and lower bounds is decreased from 1.39162 to 0.75102.
Cite as

Pu Gao, Calum MacRury, and Paweł Prałat. A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 29:1-29:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.APPROX/RANDOM.2022.29,
  author =	{Gao, Pu and MacRury, Calum and Pra{\l}at, Pawe{\l}},
  title =	{{A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{29:1--29:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.29},
  URN =		{urn:nbn:de:0030-drops-171517},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.29},
  annote =	{Keywords: Random graphs and processes, Online adaptive algorithms, Hamiltonian cycles, Differential equation method}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.46
Prophet Matching in the Probe-Commit Model

Authors: Allan Borodin, Calum MacRury, and Akash Rakheja

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
We consider the online bipartite stochastic matching problem with known i.d. (independently distributed) online vertex arrivals. In this problem, when an online vertex arrives, its weighted edges must be probed (queried) to determine if they exist, based on known edge probabilities. Our algorithms operate in the probe-commit model, in that if a probed edge exists, it must be used in the matching. Additionally, each online node has a downward-closed probing constraint on its adjacent edges which indicates which sequences of edge probes are allowable. Our setting generalizes the commonly studied patience (or time-out) constraint which limits the number of probes that can be made to an online node’s adjacent edges. Most notably, this includes non-uniform edge probing costs (specified by knapsack/budget constraint). We extend a recently introduced configuration LP to the known i.d. setting, and also provide the first proof that it is a relaxation of an optimal offline probing algorithm (the offline adaptive benchmark). Using this LP, we establish the following competitive ratio results against the offline adaptive benchmark: 1) A tight 1/2 ratio when the arrival ordering π is chosen adversarially. 2) A 1-1/e ratio when the arrival ordering π is chosen u.a.r. (uniformly at random). If π is generated adversarially, we generalize the prophet inequality matching problem. If π is u.a.r., we generalize the prophet secretary matching problem. Both results improve upon the previous best competitive ratio of 0.46 in the more restricted known i.i.d. (independent and identically distributed) arrival model against the standard offline adaptive benchmark due to Brubach et al. We are the first to study the prophet secretary matching problem in the context of probing, and our 1-1/e ratio matches the best known result without probing due to Ehsani et al. This result also applies to the unconstrained bipartite matching probe-commit problem, where we match the best known result due to Gamlath et al.
Cite as

Allan Borodin, Calum MacRury, and Akash Rakheja. Prophet Matching in the Probe-Commit Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 46:1-46:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{borodin_et_al:LIPIcs.APPROX/RANDOM.2022.46,
  author =	{Borodin, Allan and MacRury, Calum and Rakheja, Akash},
  title =	{{Prophet Matching in the Probe-Commit Model}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{46:1--46:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.46},
  URN =		{urn:nbn:de:0030-drops-171686},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.46},
  annote =	{Keywords: Stochastic probing, Online algorithms, Bipartite matching, Optimization under uncertainty}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.13
Secretary Matching Meets Probing with Commitment

Authors: Allan Borodin, Calum MacRury, and Akash Rakheja

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
We consider the online bipartite matching problem within the context of stochastic probing with commitment. This is the one-sided online bipartite matching problem where edges adjacent to an online node must be probed to determine if they exist based on edge probabilities that become known when an online vertex arrives. If a probed edge exists, it must be used in the matching. We consider the competitiveness of online algorithms in the adversarial order model (AOM) and the secretary/random order model (ROM). More specifically, we consider an unknown bipartite stochastic graph G = (U,V,E) where U is the known set of offline vertices, V is the set of online vertices, G has edge probabilities (p_{e})_{e ∈ E}, and G has edge weights (w_{e})_{e ∈ E} or vertex weights (w_u)_{u ∈ U}. Additionally, G has a downward-closed set of probing constraints (𝒞_{v})_{v ∈ V}, where 𝒞_v indicates which sequences of edges adjacent to an online vertex v can be probed. This model generalizes the various settings of the classical bipartite matching problem (i.e. with and without probing). Our contributions include the introduction and analysis of probing within the random order model, and our generalization of probing constraints which includes budget (i.e. knapsack) constraints. Our algorithms run in polynomial time assuming access to a membership oracle for each 𝒞_v. In the vertex weighted setting, for adversarial order arrivals, we generalize the known 1/2 competitive ratio to our setting of 𝒞_v constraints. For random order arrivals, we show that the same algorithm attains an asymptotic competitive ratio of 1-1/e, provided the edge probabilities vanish to 0 sufficiently fast. We also obtain a strict competitive ratio for non-vanishing edge probabilities when the probing constraints are sufficiently simple. For example, if each 𝒞_v corresponds to a patience constraint 𝓁_v (i.e., 𝓁_v is the maximum number of probes of edges adjacent to v), and any one of following three conditions is satisfied (each studied in previous papers), then there is a conceptually simple greedy algorithm whose competitive ratio is 1-1/e. - When the offline vertices are unweighted. - When the online vertex probabilities are "vertex uniform"; i.e., p_{u,v} = p_v for all (u,v) ∈ E. - When the patience constraint 𝓁_v satisfies 𝓁_v ∈ {[1,|U|} for every online vertex; i.e., every online vertex either has unit or full patience. Finally, in the edge weighted case, we match the known optimal 1/e asymptotic competitive ratio for the classic (i.e. without probing) secretary matching problem.
Cite as

Allan Borodin, Calum MacRury, and Akash Rakheja. Secretary Matching Meets Probing with Commitment. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 13:1-13:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{borodin_et_al:LIPIcs.APPROX/RANDOM.2021.13,
  author =	{Borodin, Allan and MacRury, Calum and Rakheja, Akash},
  title =	{{Secretary Matching Meets Probing with Commitment}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{13:1--13:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.13},
  URN =		{urn:nbn:de:0030-drops-147067},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.13},
  annote =	{Keywords: Stochastic probing, Online algorithms, Bipartite matching, Optimization under uncertainty}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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