68 citations · 135 across the 16 of their papers we have counts for
18 papers
Primal-Dual Neural Algorithmic Reasoning
Yu He, Ellen Vitercik
Neural Algorithmic Reasoning (NAR) trains neural networks to simulate classical algorithms, enabling structured and interpretable reasoning over complex data. While prior research…
Can LLMs Reason Structurally? Benchmarking via the Lens of Data Structures
Yu He, Yingxi Li, Colin White +1
Large language models (LLMs) are deployed on increasingly complex tasks that require multi-step decision-making. Understanding their algorithmic reasoning abilities is therefore cr…
Bandit Profit-maximization for Targeted Marketing
Joon Suk Huh, Ellen Vitercik, Kirthevasan Kandasamy
We study a sequential profit-maximization problem, optimizing for both price and ancillary variables like marketing expenditures. Specifically, we aim to maximize profit over an ar…
New Sequence-Independent Lifting Techniques for Cutting Planes and When They Induce Facets
Siddharth Prasad, Ellen Vitercik, Maria-Florina Balcan +1
Sequence-independent lifting is a procedure for strengthening valid inequalities of an integer program. We generalize the sequence-independent lifting method of Gu, Nemhauser, and…
Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts
Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm +1
The incorporation of cutting planes within the branch-and-bound algorithm, known as branch-and-cut, forms the backbone of modern integer programming solvers. These solvers are the…
Improved Sample Complexity Bounds for Branch-and-Cut
Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm +1
Branch-and-cut is the most widely used algorithm for solving integer programs, employed by commercial solvers like CPLEX and Gurobi. Branch-and-cut has a wide variety of tunable pa…
Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond
Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm +1
Cutting-plane methods have enabled remarkable successes in integer programming over the last few decades. State-of-the-art solvers integrate a myriad of cutting-plane techniques to…
Generalization in portfolio-based algorithm selection
Maria-Florina Balcan, Tuomas Sandholm, Ellen Vitercik
Portfolio-based algorithm selection has seen tremendous practical success over the past two decades. This algorithm configuration procedure works by first selecting a portfolio of…
Refined bounds for algorithm configuration: The knife-edge of dual class approximability
Maria-Florina Balcan, Tuomas Sandholm, Ellen Vitercik
Automating algorithm configuration is growing increasingly necessary as algorithms come with more and more tunable parameters. It is common to tune parameters using machine learnin…
How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design
Maria-Florina Balcan, Dan DeBlasio, Travis Dick +3
Algorithms often have tunable parameters that impact performance metrics such as runtime and solution quality. For many algorithms used in practice, no parameter settings admit mea…
Learning to Optimize Computational Resources: Frugal Training with Generalization Guarantees
Maria-Florina Balcan, Tuomas Sandholm, Ellen Vitercik
Algorithms typically come with tunable parameters that have a considerable impact on the computational resources they consume. Too often, practitioners must hand-tune the parameter…
Estimating Approximate Incentive Compatibility
Maria-Florina Balcan, Tuomas Sandholm, Ellen Vitercik
In practice, most mechanisms for selling, buying, matching, voting, and so on are not incentive compatible. We present techniques for estimating how far a mechanism is from incenti…
Learning to Branch
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm +1
Tree search algorithms, such as branch-and-bound, are the most widely used tools for solving combinatorial and nonconvex problems. For example, they are the foremost method for sol…
Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization
Maria-Florina Balcan, Travis Dick, Ellen Vitercik
Data-driven algorithm design, that is, choosing the best algorithm for a specific application, is a crucial problem in modern data science. Practitioners often optimize over a para…
Generalization Guarantees for Multi-item Profit Maximization: Pricing, Auctions, and Randomized Mechanisms
Maria-Florina Balcan, Tuomas Sandholm, Ellen Vitercik
We study multi-item profit maximization when there is an underlying distribution over buyers' values. In practice, a full description of the distribution is typically unavailable,…
Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems
Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik +1
Max-cut, clustering, and many other partitioning problems that are of significant importance to machine learning and other scientific fields are NP-hard, a reality that has motivat…
Sample Complexity of Automated Mechanism Design
Maria-Florina Balcan, Tuomas Sandholm, Ellen Vitercik
The design of revenue-maximizing combinatorial auctions, i.e. multi-item auctions over bundles of goods, is one of the most fundamental problems in computational economics, unsolve…
Learning Combinatorial Functions from Pairwise Comparisons
Maria-Florina Balcan, Ellen Vitercik, Colin White
A large body of work in machine learning has focused on the problem of learning a close approximation to an underlying combinatorial function, given a small set of labeled examples…