default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDAllan Borodin
Person information
- affiliation: University of Toronto, Canada
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[j64]Allan Borodin, Omer Lev
, Nisarg Shah, Tyrone Strangway:
Primarily about primaries. Artif. Intell. 329: 104095 (2024)- [i23]Allan Borodin, Christodoulos Karavasilis:
Random-Order Interval Selection. CoRR abs/2407.20941 (2024) - 2023
- [c70]Allan Borodin, Christodoulos Karavasilis:
Any-Order Online Interval Selection. WAOA 2023: 175-189 - [p1]Allan Borodin, Stephen A. Cook:
A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation. Logic, Automata, and Computational Complexity 2023: 245-260 - [i22]Allan Borodin, Christodoulos Karavasilis:
Any-Order Online Interval Selection. CoRR abs/2303.06127 (2023) - [i21]Allan Borodin, Calum MacRury:
Online Bipartite Matching in the Probe-Commit Model. CoRR abs/2303.08908 (2023) - 2022
- [c69]Allan Borodin, Calum MacRury, Akash Rakheja:
Prophet Matching in the Probe-Commit Model. APPROX/RANDOM 2022: 46:1-46:24 - [c68]Allan Borodin, Omer Lev, Nisarg Shah, Tyrone Strangway:
Little House (Seat) on the Prairie: Compactness, Gerrymandering, and Population Distribution. AAMAS 2022: 154-162 - [c67]Allan Borodin, Daniel Halpern, Mohamad Latifian, Nisarg Shah:
Distortion in Voting with Top-t Preferences. IJCAI 2022: 116-122 - 2021
- [c66]Allan Borodin, Calum MacRury, Akash Rakheja:
Secretary Matching Meets Probing with Commitment. APPROX-RANDOM 2021: 13:1-13:23 - [i20]Allan Borodin, Calum MacRury, Akash Rakheja:
Prophet Inequality Matching Meets Probing with Commitment. CoRR abs/2102.04325 (2021) - 2020
- [j63]Allan Borodin, Christodoulos Karavasilis, Denis Pankratov:
An Experimental Study of Algorithms for Online Bipartite Matching. ACM J. Exp. Algorithmics 25: 1-37 (2020) - [j62]Allan Borodin, Joan Boyar, Kim S. Larsen, Denis Pankratov:
Advice Complexity of Priority Algorithms. Theory Comput. Syst. 64(4): 593-625 (2020) - [i19]Allan Borodin, Calum MacRury, Akash Rakheja:
Bipartite Stochastic Matching: Online, Random Order, and I.I.D. Models. CoRR abs/2004.14304 (2020) - [i18]Allan Borodin, Calum MacRury, Akash Rakheja:
Greedy Approaches to Online Stochastic Matching. CoRR abs/2008.09260 (2020)
2010 – 2019
- 2019
- [j61]Allan Borodin, Denis Pankratov, Amirali Salehi-Abari:
On Conceptually Simple Algorithms for Variants of Online Bipartite Matching. Theory Comput. Syst. 63(8): 1781-1818 (2019) - [j60]Nicolas Pena, Allan Borodin:
On extensions of the deterministic online model for bipartite matching and max-sat. Theor. Comput. Sci. 770: 1-24 (2019) - [c65]Allan Borodin, Omer Lev, Nisarg Shah, Tyrone Strangway:
Primarily about Primaries. AAAI 2019: 1804-1811 - [c64]Yossi Azar, Allan Borodin, Michal Feldman, Amos Fiat, Kineret Segal:
Efficient Allocation of Free Stuff. AAMAS 2019: 918-925 - [i17]Allan Borodin, Akash Rakheja:
Electronic markets with multiple submodular buyers. CoRR abs/1907.11915 (2019) - 2018
- [c63]Allan Borodin, Christodoulos Karavasilis, Denis Pankratov:
Greedy Bipartite Matching in Random Type Poisson Arrival Model. APPROX-RANDOM 2018: 5:1-5:15 - [c62]Atiyeh Ashari Ghomi, Allan Borodin, Omer Lev:
Seasonal Goods and Spoiled Milk: Pricing for a Limited Shelf-Life. AAMAS 2018: 901-909 - [c61]Allan Borodin, Omer Lev, Nisarg Shah, Tyrone Strangway:
Big City vs. the Great Outdoors: Voter Distribution and How It Affects Gerrymandering. IJCAI 2018: 98-104 - [c60]Allan Borodin, Denis Pankratov, Amirali Salehi-Abari:
A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version. SOSA 2018: 8:1-8:12 - [c59]Allan Borodin, Joan Boyar, Kim S. Larsen, Denis Pankratov:
Advice Complexity of Priority Algorithms. WAOA 2018: 69-86 - [i16]Atiyeh Ashari Ghomi, Allan Borodin, Omer Lev:
Seasonal Goods and Spoiled Milk: Pricing for a Limited Shelf-Life. CoRR abs/1801.02263 (2018) - [i15]Allan Borodin, Christodoulos Karavasilis, Denis Pankratov:
Greedy Bipartite Matching in Random Type Poisson Arrival Model. CoRR abs/1805.00578 (2018) - [i14]Allan Borodin, Joan Boyar, Kim S. Larsen, Denis Pankratov:
Advice Complexity of Priority Algorithms. CoRR abs/1806.06223 (2018) - [i13]Allan Borodin, Christodoulos Karavasilis, Denis Pankratov:
An Experimental Study of Algorithms for Online Bipartite Matching. CoRR abs/1808.04863 (2018) - 2017
- [j59]Allan Borodin, Mark Braverman, Brendan Lucier, Joel Oren:
Strategyproof Mechanisms for Competitive Influence in Networks. Algorithmica 78(2): 425-452 (2017) - [j58]Brendan Lucier, Allan Borodin:
Equilibria of Greedy Combinatorial Auctions. SIAM J. Comput. 46(2): 620-660 (2017) - [j57]Allan Borodin, Aadhar Jain, Hyun Chul Lee, Yuli Ye:
Max-Sum Diversification, Monotone Submodular Functions, and Dynamic Updates. ACM Trans. Algorithms 13(3): 41:1-41:25 (2017) - [j56]Marek Adamczyk, Allan Borodin, Diodato Ferraioli, Bart de Keijzer, Stefano Leonardi:
Sequential Posted-Price Mechanisms with Correlated Valuations. ACM Trans. Economics and Comput. 5(4): 22:1-22:39 (2017) - [c58]Allan Borodin, Denis Pankratov, Amirali Salehi-Abari:
On Conceptually Simple Algorithms for Variants of Online Bipartite Matching. WAOA 2017: 253-268 - [i12]Allan Borodin, Denis Pankratov, Amirali Salehi-Abari:
On Conceptually Simple Algorithms for Variants of Online Bipartite Matching. CoRR abs/1706.09966 (2017) - [i11]Allan Borodin, Denis Pankratov, Amirali Salehi-Abari:
A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version. CoRR abs/1708.01657 (2017) - 2016
- [j55]Allan Borodin, Brendan Lucier:
On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions. ACM Trans. Economics and Comput. 5(1): 2:1-2:23 (2016) - [c57]Allan Borodin, Omer Lev, Tyrone Strangway:
Budgetary Effects on Pricing Equilibrium in Online Markets. AAMAS 2016: 95-103 - [i10]Nicolas Pena, Allan Borodin:
On the limitations of deterministic de-randomizations for online bipartite matching and max-sat. CoRR abs/1608.03182 (2016) - 2015
- [c56]Marek Adamczyk, Allan Borodin, Diodato Ferraioli, Bart de Keijzer, Stefano Leonardi:
Sequential Posted Price Mechanisms with Correlated Valuations. WINE 2015: 1-15 - [i9]Marek Adamczyk, Allan Borodin, Diodato Ferraioli, Bart de Keijzer, Stefano Leonardi:
Sequential Posted Price Mechanisms with Correlated Valuations. CoRR abs/1503.02200 (2015) - [i8]Allan Borodin, Omer Lev, Tyrone Strangway:
Budgetary Effects on Pricing Equilibrium in Online Markets. CoRR abs/1511.06954 (2015) - 2014
- [c55]Norman Huang, Allan Borodin:
Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization. ISAAC 2014: 528-539 - [i7]Allan Borodin, Dai Le, Yuli Ye:
Weakly Submodular Functions. CoRR abs/1401.6697 (2014) - 2013
- [c54]Allan Borodin:
Computing (and Life) Is All about Tradeoffs - A Small Sample of Some Computational Tradeoffs. Space-Efficient Data Structures, Streams, and Algorithms 2013: 112-132 - [c53]Allan Borodin, Mark Braverman, Brendan Lucier, Joel Oren:
Strategyproof mechanisms for competitive influence in networks. WWW 2013: 141-150 - [i6]Norman Huang, Allan Borodin:
Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotone Submodular Maximization. CoRR abs/1312.2173 (2013) - 2012
- [j54]Yuli Ye, Allan Borodin:
Elimination graphs. ACM Trans. Algorithms 8(2): 14:1-14:23 (2012) - [j53]Allan Borodin, Ioana Ivan, Yuli Ye, Bryce Zimny:
On sum coloring and sum multi-coloring for restricted families of graphs. Theor. Comput. Sci. 418: 1-13 (2012) - [c52]Allan Borodin, Hyun Chul Lee, Yuli Ye:
Max-Sum diversification, monotone submodular functions and dynamic updates. PODS 2012: 155-166 - [i5]Allan Borodin, Mark Braverman, Brendan Lucier, Joel Oren:
Truthful Mechanisms for Competing Submodular Processes. CoRR abs/1202.2097 (2012) - [i4]Allan Borodin, Hyun Chul Lee, Yuli Ye:
Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates. CoRR abs/1203.6397 (2012) - 2011
- [j52]Allan Borodin, Toniann Pitassi, Alexander A. Razborov:
Special Issue In Memory of Misha Alekhnovich. Foreword. Comput. Complex. 20(4): 579-590 (2011) - [j51]Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi:
Toward a Model for Backtracking and Dynamic Programming. Comput. Complex. 20(4): 679-740 (2011) - [j50]Allan Borodin, David Cashman, Avner Magen:
How well can primal-dual and local-ratio algorithms perform? ACM Trans. Algorithms 7(3): 29:1-29:26 (2011) - [i3]Allan Borodin, Ran El-Yaniv, Vincent Gogan:
Can We Learn to Beat the Best Stock. CoRR abs/1107.0036 (2011) - 2010
- [j49]Allan Borodin, Joan Boyar, Kim S. Larsen, Nazanin Mirmohammadi:
Priority algorithms for graph optimization problems. Theor. Comput. Sci. 411(1): 239-258 (2010) - [j48]Spyros Angelopoulos, Allan Borodin:
Randomized priority algorithms. Theor. Comput. Sci. 411(26-28): 2542-2558 (2010) - [c51]Allan Borodin, Brendan Lucier:
On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions. ICALP (1) 2010: 90-101 - [c50]Denis Pankratov, Allan Borodin:
On the Relative Merits of Simple Local Search Methods for the MAX-SAT Problem. SAT 2010: 223-236 - [c49]Brendan Lucier, Allan Borodin:
Price of Anarchy for Greedy Auctions. SODA 2010: 537-553 - [c48]Allan Borodin, Yuval Filmus, Joel Oren:
Threshold Models for Competitive Influence in Social Networks. WINE 2010: 539-550
2000 – 2009
- 2009
- [j47]Hyun Chul Lee, Allan Borodin:
Criteria for Cluster-Based Personalized Search. Internet Math. 6(3): 399-435 (2009) - [c47]Allan Borodin:
Invited Talk II The Power and Limitations of Simple Algorithms: A Partial Case Study of Greedy Mechanisim Design for Combinatorial Actions. ALGOSENSORS 2009: 2 - [c46]Yuli Ye, Allan Borodin:
Elimination Graphs. ICALP (1) 2009: 774-785 - [c45]Hyun Chul Lee, Allan Borodin:
Cluster Based Personalized Search. WAW 2009: 167-183 - [i2]Brendan Lucier, Allan Borodin:
Price of Anarchy for Greedy Auctions. CoRR abs/0909.0892 (2009) - [i1]Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen:
Toward a Model for Backtracking and Dynamic Programming. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [j46]Yuli Ye, Allan Borodin:
Priority algorithms for the subset-sum problem. J. Comb. Optim. 16(3): 198-228 (2008) - [c44]Hyun Chul Lee, Allan Borodin, Leslie Goldsmith:
Extracting and ranking viral communities using seeds and content similarity. Hypertext 2008: 139-148 - 2007
- [c43]Yuli Ye, Allan Borodin:
Priority Algorithms for the Subset-Sum Problem. COCOON 2007: 504-514 - 2006
- [c42]Allan Borodin:
Further Reflections on a Theory for Basic Algorithms. AAIM 2006: 1-9 - 2005
- [j45]Allan Borodin, Gareth O. Roberts, Jeffrey S. Rosenthal, Panayiotis Tsaparas:
Link analysis ranking: algorithms, theory, and experiments. ACM Trans. Internet Techn. 5(1): 231-297 (2005) - [c41]Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi:
Toward a Model for Backtracking and Dynamic Programming. CCC 2005: 308-322 - [c40]Allan Borodin, David Cashman, Avner Magen:
How Well Can Primal-Dual and Local-Ratio Algorithms Perform?. ICALP 2005: 943-955 - [c39]Allan Borodin:
Towards a Theory of Algorithms. WADS 2005: 1 - 2004
- [j44]Spyros Angelopoulos, Allan Borodin:
The Power of Priority Algorithms for Facility Location and Set Cover. Algorithmica 40(4): 271-291 (2004) - [j43]Allan Borodin, Ran El-Yaniv, Vincent Gogan:
Can We Learn to Beat the Best Stock. J. Artif. Intell. Res. 21: 579-594 (2004) - [j42]Allan Borodin, Rafail Ostrovsky, Yuval Rabani:
Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds. J. Interconnect. Networks 5(1): 1-12 (2004) - [j41]Allan Borodin, Rafail Ostrovsky, Yuval Rabani:
Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces. Mach. Learn. 56(1-3): 153-167 (2004) - [c38]Allan Borodin, Joan Boyar, Kim S. Larsen:
Priority Algorithms for Graph Optimization Problems. WAOA 2004: 126-139 - 2003
- [j40]Allan Borodin, Morten N. Nielsen, Charles Rackoff:
(Incremental) Priority Algorithms. Algorithmica 37(4): 295-326 (2003) - [c37]Hyun Chul Lee, Allan Borodin:
Perturbation of the Hyper-Linked Environment. COCOON 2003: 272-283 - [c36]Allan Borodin, Ran El-Yaniv, Vincent Gogan:
Can We Learn to Beat the Best Stock. NIPS 2003: 345-352 - 2002
- [c35]Spyros Angelopoulos, Allan Borodin:
On the Power of Priority Algorithms for Facility Location and Set Cover. APPROX 2002: 26-39 - [c34]Allan Borodin, Morten N. Nielsen, Charles Rackoff:
(Incremental) priority algorithms. SODA 2002: 752-761 - 2001
- [j39]Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson:
Adversarial queuing theory. J. ACM 48(1): 13-38 (2001) - [c33]Allan Borodin, Rafail Ostrovsky, Yuval Rabani:
Stability preserving transformations: packet routing networks with edge capacities and speeds. SODA 2001: 601-610 - [c32]Allan Borodin, Gareth O. Roberts, Jeffrey S. Rosenthal, Panayiotis Tsaparas:
Finding authorities and hubs from link structures on the World Wide Web. WWW 2001: 415-429 - 2000
- [c31]Allan Borodin, Ran El-Yaniv, Vincent Gogan:
On the Competitive Theory and Practice of Portfolio Selection (Extended Abstract). LATIN 2000: 173-196
1990 – 1999
- 1999
- [j38]Allan Borodin, Ran El-Yaniv:
On Randomization in On-Line Computation. Inf. Comput. 150(2): 244-267 (1999) - [j37]Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa:
A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata. SIAM J. Comput. 28(3): 1051-1072 (1999) - [c30]Allan Borodin, Rafail Ostrovsky, Yuval Rabani:
Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems. STOC 1999: 312-321 - [c29]Allan Borodin, Rafail Ostrovsky, Yuval Rabani:
Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces. STOC 1999: 435-444 - 1998
- [b3]Allan Borodin, Ran El-Yaniv:
Online computation and competitive analysis. Cambridge University Press 1998, ISBN 978-0-521-56392-5, pp. I-XVIII, 1-414 - 1997
- [j36]Allan Borodin:
Tribute to Roman Smolensky. Comput. Complex. 6(3): 195-198 (1997) - [j35]Allan Borodin, Prabhakar Raghavan, Baruch Schieber, Eli Upfal:
How much can hardware help routing? J. ACM 44(5): 726-741 (1997) - [j34]Allan Borodin, Yuval Rabani, Baruch Schieber:
Deterministic Many-to-Many Hot Potato Routing. IEEE Trans. Parallel Distributed Syst. 8(6): 587-596 (1997) - [c28]Allan Borodin, Ran El-Yaniv:
On Ranomization in Online Computation. CCC 1997: 226-238 - 1996
- [j33]Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa:
Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata. Inf. Comput. 130(2): 101-129 (1996) - [c27]Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson:
Adversarial Queueing Theory. STOC 1996: 376-385 - 1995
- [j32]Allan Borodin, Sandy Irani, Prabhakar Raghavan, Baruch Schieber:
Competitive Paging with Locality of Reference. J. Comput. Syst. Sci. 50(2): 244-258 (1995) - [e2]Frank Thomson Leighton, Allan Borodin:
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA. ACM 1995, ISBN 0-89791-718-9 [contents] - 1994
- [j31]Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, Avi Wigderson:
On the Power of Randomization in On-Line Algorithms. Algorithmica 11(1): 2-14 (1994) - [j30]Shai Ben-David, Allan Borodin:
A New Measure for the Study of On-Line Algorithms. Algorithmica 11(1): 73-91 (1994) - 1993
- [j29]Allan Borodin, Alexander A. Razborov, Roman Smolensky:
On Lower Bounds for Read-K-Times Branching Programs. Comput. Complex. 3: 1-18 (1993) - [c26]Allan Borodin:
Time Space Tradeoffs (Getting Closer to the Barrier?). ISAAC 1993: 209-220 - [c25]Allan Borodin, Prabhakar Raghavan, Baruch Schieber, Eli Upfal:
How much can hardware help routing? STOC 1993: 573-582 - [c24]Allan Borodin:
Towards a Better Understanding of the Pure Packet Routing. WADS 1993: 14-25 - 1992
- [j28]Allan Borodin, Nathan Linial, Michael E. Saks:
An Optimal On-Line Algorithm for Metrical Task System. J. ACM 39(4): 745-763 (1992) - [j27]Allan Borodin, Walter L. Ruzzo, Martin Tompa:
Lower Bounds on the Length of Universal Traversal Sequences. J. Comput. Syst. Sci. 45(2): 180-203 (1992) - [c23]Allan Borodin:
Can competitive analysis be made competitive? CASCON 1992: 359-367 - 1991
- [j26]Allan Borodin, Prasoon Tiwari:
On the Decidability of Sparse Univariate Polynomial Interpolation. Comput. Complex. 1: 67-90 (1991) - [c22]Allan Borodin, Sandy Irani, Prabhakar Raghavan, Baruch Schieber:
Competitive Paging with Locality of Reference (Brief Summary). On-Line Algorithms 1991: 167-168 - [c21]Allan Borodin, Sandy Irani, Prabhakar Raghavan, Baruch Schieber:
Competitive Paging with Locality of Reference (Preliminary Version). STOC 1991: 249-259 - 1990
- [c20]Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa:
Time-Space Tradeoffs for Undirected Graph Traversal. FOCS 1990: 429-438 - [c19]Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, Avi Wigderson:
On the Power of Randomization in Online Algorithms (Extended Abstract). STOC 1990: 379-386 - [c18]Allan Borodin, Prasoon Tiwari:
On the Decidability of Sparse Univariate Polynomial Interpolation (Preliminary Version). STOC 1990: 535-545
1980 – 1989
- 1989
- [j25]Amotz Bar-Noy, Allan Borodin, Mauricio Karchmer, Nathan Linial, Michael Werman:
Bounds on Universal Sequences. SIAM J. Comput. 18(2): 268-277 (1989) - [j24]Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, Martin Tompa:
Two Applications of Inductive Counting for Complementation Problems. SIAM J. Comput. 18(3): 559-578 (1989) - [j23]Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, Martin Tompa:
Erratum: Two Applications of Inductive Counting for Complementation Problems. SIAM J. Comput. 18(6): 1283 (1989) - [j22]