Search Results

Documents authored by Borodin, Allan

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}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.5
Greedy Bipartite Matching in Random Type Poisson Arrival Model

Authors: Allan Borodin, Christodoulos Karavasilis, and Denis Pankratov

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

Abstract
We introduce a new random input model for bipartite matching which we call the Random Type Poisson Arrival Model. Just like in the known i.i.d. model (introduced by Feldman et al. [Feldman et al., 2009]), online nodes have types in our model. In contrast to the adversarial types studied in the known i.i.d. model, following the random graphs studied in Mastin and Jaillet [A. Mastin, 2013], in our model each type graph is generated randomly by including each offline node in the neighborhood of an online node with probability c/n independently. In our model, nodes of the same type appear consecutively in the input and the number of times each type node appears is distributed according to the Poisson distribution with parameter 1. We analyze the performance of the simple greedy algorithm under this input model. The performance is controlled by the parameter c and we are able to exactly characterize the competitive ratio for the regimes c = o(1) and c = omega(1). We also provide a precise bound on the expected size of the matching in the remaining regime of constant c. We compare our results to the previous work of Mastin and Jaillet who analyzed the simple greedy algorithm in the G_{n,n,p} model where each online node type occurs exactly once. We essentially show that the approach of Mastin and Jaillet can be extended to work for the Random Type Poisson Arrival Model, although several nontrivial technical challenges need to be overcome. Intuitively, one can view the Random Type Poisson Arrival Model as the G_{n,n,p} model with less randomness; that is, instead of each online node having a new type, each online node has a chance of repeating the previous type.
Cite as

Allan Borodin, Christodoulos Karavasilis, and Denis Pankratov. Greedy Bipartite Matching in Random Type Poisson Arrival Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{borodin_et_al:LIPIcs.APPROX-RANDOM.2018.5,
  author =	{Borodin, Allan and Karavasilis, Christodoulos and Pankratov, Denis},
  title =	{{Greedy Bipartite Matching in Random Type Poisson Arrival Model}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{5:1--5:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.5},
  URN =		{urn:nbn:de:0030-drops-94098},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.5},
  annote =	{Keywords: bipartite matching, stochastic input models, online algorithms, greedy algorithms}
}
Document
DOI: 10.4230/OASIcs.SOSA.2018.8
A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version

Authors: Allan Borodin, Denis Pankratov, and Amirali Salehi-Abari

Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)

Abstract
Recently, Renault (2016) studied the dual bin packing problem in the per-request advice model of online algorithms. He showed that given O(1/eps) advice bits for each input item allows approximating the dual bin packing problem online to within a factor of 1+\eps. Renault asked about the advice complexity of dual bin packing in the tape-advice model of online algorithms. We make progress on this question. Let s be the maximum bit size of an input item weight. We present a conceptually simple online algorithm that with total advice O((s + log n)/eps^2) approximates the dual bin packing to within a 1+eps factor. To this end, we describe and analyze a simple offline PTAS for the dual bin packing problem. Although a PTAS for a more general problem was known prior to our work (Kellerer 1999, Chekuri and Khanna 2006), our PTAS is arguably simpler to state and analyze. As a result, we could easily adapt our PTAS to obtain the advice-complexity result. We also consider whether the dependence on s is necessary in our algorithm. We show that if s is unrestricted then for small enough eps > 0 obtaining a 1+eps approximation to the dual bin packing requires Omega_eps(n) bits of advice. To establish this lower bound we analyze an online reduction that preserves the advice complexity and approximation ratio from the binary separation problem due to Boyar et al. (2016). We define two natural advice complexity classes that capture the distinction similar to the Turing machine world distinction between pseudo polynomial time algorithms and polynomial time algorithms. Our results on the dual bin packing problem imply the separation of the two classes in the advice complexity world.
Cite as

Allan Borodin, Denis Pankratov, and Amirali Salehi-Abari. A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 8:1-8:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{borodin_et_al:OASIcs.SOSA.2018.8,
  author =	{Borodin, Allan and Pankratov, Denis and Salehi-Abari, Amirali},
  title =	{{A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  pages =	{8:1--8:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Seidel, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.8},
  URN =		{urn:nbn:de:0030-drops-83033},
  doi =		{10.4230/OASIcs.SOSA.2018.8},
  annote =	{Keywords: dual bin packing, PTAS, tape-advice complexity}
}
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 About DROPS Imprint Privacy Contact