Allan Borodin

Publication Activity (10 Years)

Years Active: 1969-2024
Publications (10 Years): 38

Top Venues

CoRR

AAMAS

WAOA

APPROX-RANDOM

Publications

Allan Borodin, Omer Lev, Nisarg Shah, Tyrone Strangway
Primarily about primaries. Artif. Intell. 329 (2024)
Allan Borodin, Christodoulos Karavasilis
Random-Order Interval Selection. CoRR (2024)
Allan Borodin, Calum MacRury
Online Bipartite Matching in the Probe-Commit Model. CoRR (2023)
Allan Borodin, Christodoulos Karavasilis
Any-Order Online Interval Selection. CoRR (2023)
Allan Borodin, Christodoulos Karavasilis
Any-Order Online Interval Selection. WAOA (2023)
Allan Borodin, Omer Lev, Nisarg Shah, Tyrone Strangway
Little House (Seat) on the Prairie: Compactness, Gerrymandering, and Population Distribution. AAMAS (2022)
Allan Borodin, Calum MacRury, Akash Rakheja
Prophet Matching in the Probe-Commit Model. APPROX/RANDOM (2022)
Allan Borodin, Daniel Halpern, Mohamad Latifian, Nisarg Shah
Distortion in Voting with Top-t Preferences. IJCAI (2022)
Allan Borodin, Calum MacRury, Akash Rakheja
Secretary Matching Meets Probing with Commitment. APPROX-RANDOM (2021)
Allan Borodin, Calum MacRury, Akash Rakheja
Prophet Inequality Matching Meets Probing with Commitment. CoRR (2021)
Allan Borodin, Calum MacRury, Akash Rakheja
Bipartite Stochastic Matching: Online, Random Order, and I.I.D. Models. CoRR (2020)
Allan Borodin, Calum MacRury, Akash Rakheja
Greedy Approaches to Online Stochastic Matching. CoRR (2020)
Allan Borodin, Christodoulos Karavasilis, Denis Pankratov
An Experimental Study of Algorithms for Online Bipartite Matching. ACM J. Exp. Algorithmics 25 (2020)
Allan Borodin, Joan Boyar, Kim S. Larsen, Denis Pankratov
Advice Complexity of Priority Algorithms. Theory Comput. Syst. 64 (4) (2020)
Yossi Azar, Allan Borodin, Michal Feldman, Amos Fiat, Kineret Segal
Efficient Allocation of Free Stuff. AAMAS (2019)
Nicolas Pena, Allan Borodin
On extensions of the deterministic online model for bipartite matching and max-sat. Theor. Comput. Sci. 770 (2019)
Allan Borodin, Omer Lev, Nisarg Shah, Tyrone Strangway
Primarily about Primaries. AAAI (2019)
Allan Borodin, Akash Rakheja
Electronic markets with multiple submodular buyers. CoRR (2019)
Allan Borodin, Denis Pankratov, Amirali Salehi-Abari
On Conceptually Simple Algorithms for Variants of Online Bipartite Matching. Theory Comput. Syst. 63 (8) (2019)
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)
Allan Borodin, Christodoulos Karavasilis, Denis Pankratov
Greedy Bipartite Matching in Random Type Poisson Arrival Model. CoRR (2018)
Allan Borodin, Joan Boyar, Kim S. Larsen, Denis Pankratov
Advice Complexity of Priority Algorithms. CoRR (2018)
Atiyeh Ashari Ghomi, Allan Borodin, Omer Lev
Seasonal Goods and Spoiled Milk: Pricing for a Limited Shelf-Life. AAMAS (2018)
Allan Borodin, Joan Boyar, Kim S. Larsen, Denis Pankratov
Advice Complexity of Priority Algorithms. WAOA (2018)
Allan Borodin, Omer Lev, Nisarg Shah, Tyrone Strangway
Big City vs. the Great Outdoors: Voter Distribution and How It Affects Gerrymandering. IJCAI (2018)
Allan Borodin, Christodoulos Karavasilis, Denis Pankratov
Greedy Bipartite Matching in Random Type Poisson Arrival Model. APPROX-RANDOM (2018)
Atiyeh Ashari Ghomi, Allan Borodin, Omer Lev
Seasonal Goods and Spoiled Milk: Pricing for a Limited Shelf-Life. CoRR (2018)
Allan Borodin, Christodoulos Karavasilis, Denis Pankratov
An Experimental Study of Algorithms for Online Bipartite Matching. CoRR (2018)
Allan Borodin, Aadhar Jain, Hyun Chul Lee, Yuli Ye
Max-Sum Diversification, Monotone Submodular Functions, and Dynamic Updates. ACM Trans. Algorithms 13 (3) (2017)
Allan Borodin, Denis Pankratov, Amirali Salehi-Abari
On Conceptually Simple Algorithms for Variants of Online Bipartite Matching. CoRR (2017)
Allan Borodin, Denis Pankratov, Amirali Salehi-Abari
On Conceptually Simple Algorithms for Variants of Online Bipartite Matching. WAOA (2017)
Allan Borodin, Mark Braverman, Brendan Lucier, Joel Oren
Strategyproof Mechanisms for Competitive Influence in Networks. Algorithmica 78 (2) (2017)
Allan Borodin, Denis Pankratov, Amirali Salehi-Abari
A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version. CoRR (2017)
Brendan Lucier, Allan Borodin
Equilibria of Greedy Combinatorial Auctions. SIAM J. Comput. 46 (2) (2017)
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) (2017)
Allan Borodin, Brendan Lucier
On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions. ACM Trans. Economics and Comput. 5 (1) (2016)
Nicolas Pena, Allan Borodin
On the limitations of deterministic de-randomizations for online bipartite matching and max-sat. CoRR (2016)
Allan Borodin, Omer Lev, Tyrone Strangway
Budgetary Effects on Pricing Equilibrium in Online Markets. AAMAS (2016)
Allan Borodin, Omer Lev, Tyrone Strangway
Budgetary Effects on Pricing Equilibrium in Online Markets. CoRR (2015)
Marek Adamczyk, Allan Borodin, Diodato Ferraioli, Bart de Keijzer, Stefano Leonardi
Sequential Posted Price Mechanisms with Correlated Valuations. WINE (2015)
Marek Adamczyk, Allan Borodin, Diodato Ferraioli, Bart de Keijzer, Stefano Leonardi
Sequential Posted Price Mechanisms with Correlated Valuations. CoRR (2015)
Allan Borodin, Dai Le, Yuli Ye
Weakly Submodular Functions. CoRR (2014)
Norman Huang, Allan Borodin
Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization. ISAAC (2014)
Allan Borodin, Mark Braverman, Brendan Lucier, Joel Oren
Strategyproof mechanisms for competitive influence in networks. WWW (2013)
Allan Borodin
Computing (and Life) Is All about Tradeoffs - A Small Sample of Some Computational Tradeoffs. Space-Efficient Data Structures, Streams, and Algorithms (2013)
Norman Huang, Allan Borodin
Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotone Submodular Maximization. CoRR (2013)
Allan Borodin, Hyun Chul Lee, Yuli Ye
Max-Sum diversification, monotone submodular functions and dynamic updates. PODS (2012)
Allan Borodin, Mark Braverman, Brendan Lucier, Joel Oren
Truthful Mechanisms for Competing Submodular Processes CoRR (2012)
Yuli Ye, Allan Borodin
Elimination graphs. ACM Trans. Algorithms 8 (2) (2012)
Allan Borodin, Ioana Ivan, Yuli Ye, Bryce Zimny
On sum coloring and sum multi-coloring for restricted families of graphs. Theor. Comput. Sci. 418 (2012)
Allan Borodin, Hyun Chul Lee, Yuli Ye
Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates CoRR (2012)
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) (2011)
Allan Borodin, Ran El-Yaniv, Vincent Gogan
Can We Learn to Beat the Best Stock CoRR (2011)
Allan Borodin, Toniann Pitassi, Alexander A. Razborov
Special Issue In Memory of Misha Alekhnovich. Foreword. Comput. Complex. 20 (4) (2011)
Allan Borodin, David Cashman, Avner Magen
How well can primal-dual and local-ratio algorithms perform? ACM Trans. Algorithms 7 (3) (2011)
Allan Borodin, Brendan Lucier
On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions. ICALP (1) (2010)
Allan Borodin, Yuval Filmus, Joel Oren
Threshold Models for Competitive Influence in Social Networks. WINE (2010)
Allan Borodin, Joan Boyar, Kim S. Larsen, Nazanin Mirmohammadi
Priority algorithms for graph optimization problems. Theor. Comput. Sci. 411 (1) (2010)
Brendan Lucier, Allan Borodin
Price of Anarchy for Greedy Auctions. SODA (2010)
Denis Pankratov, Allan Borodin
On the Relative Merits of Simple Local Search Methods for the MAX-SAT Problem. SAT (2010)
Spyros Angelopoulos, Allan Borodin
Randomized priority algorithms. Theor. Comput. Sci. 411 (26-28) (2010)
Brendan Lucier, Allan Borodin
Price of Anarchy for Greedy Auctions CoRR (2009)
Hyun Chul Lee, Allan Borodin
Cluster Based Personalized Search. WAW (2009)
Hyun Chul Lee, Allan Borodin
Criteria for Cluster-Based Personalized Search. Internet Math. 6 (3) (2009)
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)
Yuli Ye, Allan Borodin
Elimination Graphs. ICALP (1) (2009)
Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen
Toward a Model for Backtracking and Dynamic Programming. Electron. Colloquium Comput. Complex. 16 (2009)
Hyun Chul Lee, Allan Borodin, Leslie Goldsmith
Extracting and ranking viral communities using seeds and content similarity. Hypertext (2008)
Yuli Ye, Allan Borodin
Priority algorithms for the subset-sum problem. J. Comb. Optim. 16 (3) (2008)
Yuli Ye, Allan Borodin
Priority Algorithms for the Subset-Sum Problem. COCOON (2007)
Allan Borodin
Further Reflections on a Theory for Basic Algorithms. AAIM (2006)
Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi
Toward a Model for Backtracking and Dynamic Programming. Computational Complexity Conference (2005)
Allan Borodin, David Cashman, Avner Magen
How Well Can Primal-Dual and Local-Ratio Algorithms Perform?. ICALP (2005)
Allan Borodin, Gareth O. Roberts, Jeffrey S. Rosenthal, Panayiotis Tsaparas
Link analysis ranking: algorithms, theory, and experiments. ACM Trans. Internet Techn. 5 (1) (2005)
Allan Borodin
Towards a Theory of Algorithms. WADS (2005)
Spyros Angelopoulos, Allan Borodin
The Power of Priority Algorithms for Facility Location and Set Cover. Algorithmica 40 (4) (2004)
Allan Borodin, Joan Boyar, Kim S. Larsen
Priority Algorithms for Graph Optimization Problems. WAOA (2004)
Allan Borodin, Ran El-Yaniv, Vincent Gogan
Can We Learn to Beat the Best Stock. J. Artif. Intell. Res. 21 (2004)
Allan Borodin, Rafail Ostrovsky, Yuval Rabani
Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds. J. Interconnect. Networks 5 (1) (2004)
Allan Borodin, Rafail Ostrovsky, Yuval Rabani
Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces. Mach. Learn. 56 (1-3) (2004)
Hyun Chul Lee, Allan Borodin
Perturbation of the Hyper-Linked Environment. COCOON (2003)
Allan Borodin, Ran El-Yaniv, Vincent Gogan
Can We Learn to Beat the Best Stock. NIPS (2003)
Allan Borodin, Morten N. Nielsen, Charles Rackoff
(Incremental) Priority Algorithms. Algorithmica 37 (4) (2003)
Spyros Angelopoulos, Allan Borodin
On the Power of Priority Algorithms for Facility Location and Set Cover. APPROX (2002)
Allan Borodin, Morten N. Nielsen, Charles Rackoff
(Incremental) priority algorithms. SODA (2002)
Allan Borodin, Rafail Ostrovsky, Yuval Rabani
Stability preserving transformations: packet routing networks with edge capacities and speeds. SODA (2001)
Allan Borodin, Gareth O. Roberts, Jeffrey S. Rosenthal, Panayiotis Tsaparas
Finding authorities and hubs from link structures on the World Wide Web. WWW (2001)
Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson
Adversarial queuing theory. J. ACM 48 (1) (2001)
Allan Borodin, Ran El-Yaniv, Vincent Gogan
On the Competitive Theory and Practice of Portfolio Selection (Extended Abstract). LATIN (2000)
Allan Borodin, Rafail Ostrovsky, Yuval Rabani
Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems. STOC (1999)
Allan Borodin, Rafail Ostrovsky, Yuval Rabani
Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces. STOC (1999)
Allan Borodin, Ran El-Yaniv
On Randomization in On-Line Computation. Inf. Comput. 150 (2) (1999)
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) (1999)
Allan Borodin, Prabhakar Raghavan, Baruch Schieber, Eli Upfal
How much can hardware help routing? J. ACM 44 (5) (1997)
Allan Borodin
Tribute to Roman Smolensky. Comput. Complex. 6 (3) (1997)
Allan Borodin, Ran El-Yaniv
On Ranomization in Online Computation. Computational Complexity Conference (1997)
Allan Borodin, Yuval Rabani, Baruch Schieber
Deterministic Many-to-Many Hot Potato Routing. IEEE Trans. Parallel Distributed Syst. 8 (6) (1997)
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) (1996)
Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson
Adversarial Queueing Theory. STOC (1996)
Allan Borodin, Sandy Irani, Prabhakar Raghavan, Baruch Schieber
Competitive Paging with Locality of Reference. J. Comput. Syst. Sci. 50 (2) (1995)

Allan Borodin.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Allan Borodin