Combinatorics and Optimization
http://hdl.handle.net/10012/9928
Tue, 30 May 2023 10:16:12 GMT2023-05-30T10:16:12ZAlgorithmic and Linear Programming-Based Techniques for the Maximum Utility Problem
http://hdl.handle.net/10012/19481
Algorithmic and Linear Programming-Based Techniques for the Maximum Utility Problem
Lawrence, Paul
A common topic of study in the subfield of Operations Research known as Revenue Management
is finding optimal prices for a line of products given customer preferences. While there exists a
large number of ways to model optimal pricing problems, in this thesis we study a price-based
Revenue Management model known as the Maximum Utility Problem (MUP). In this model, we
are given a set of n customer segments and m products, as well as reservation prices Rij which
reflect the amount that Segment i is willing to pay for Product j. Using a number of structural and
behavioral assumptions, if we derive a vector of prices for our line of products, we can compute an
assignment of customers to products. We wish to find the set of prices that leads to the optimal
amount of revenue given our rules for assigning customers to products. Using this framework, we
can formulate a Nonlinear Mixed Integer Programming formulation that, while difficult to solve,
has a surprising amount of underlying structure. If we fix an assignment and simply ask for the
optimal set of prices such that said assignment is feasible, we obtain a new linear program, the
dual of which happens to be a set of shortest-paths problems. This fact lead to the development of
the Dobson-Kalish Algorithm, which explores a large number of assignments and quickly computes
their optimal prices.
Since the introduction of the Dobson-Kalish Algorithm, there has been a rich variety of literature
surrounding MUP and its relatives. These include the introduction of utility tolerances to increase
the robustness of the model, as well as new approximation algorithms, hardness results, and insights
into the underlying combinatorial structure of the problem. After detailing this history, this thesis
discusses a range of settings under which MUP can be solved in polynomial time. Relating it to
other equilibria and price-based optimization problems, we overview Stackelberg Network Pricing
Games as well as the general formulations of Bilevel Mixed Integer Linear Programs and Bilinear
Mixed Integer Programs, showing that our formulation of the latter is in fact a more general version
of the former. We provide some new structured instances for which we can prove additional ap-
proximation and runtime results for existing algorithms. We also contribute a generalized heuristic
algorithm and show that MUP can be solved exactly when the matrix of reservation prices is rank
1. Finally, we discuss techniques for improving the upper bound to the overall problem, analyzing
the primal and dual of the linear programming relaxation of MUP. To test the effectiveness of our
approach, we analyze numerous examples that have been solved using Gurobi and present possible
avenues for improving our ideas.
Thu, 25 May 2023 00:00:00 GMThttp://hdl.handle.net/10012/194812023-05-25T00:00:00ZLow-Rank Plus Sparse Decompositions of Large-Scale Matrices via Semidefinite Optimization
http://hdl.handle.net/10012/19463
Low-Rank Plus Sparse Decompositions of Large-Scale Matrices via Semidefinite Optimization
Gong, Rui
We study the problem of decomposing a symmetric matrix into the sum of a low-rank symmetric positive semidefinite matrix and a tridiagonal matrix, and a relaxation which looks for symmetric positive semidefinite matrices with small nuclear norms. These problems are generalizations of
the problem of decomposing a symmetric matrix into a low-rank symmetric positive semidefinite
matrix plus a diagonal matrix and one of its relaxations, the minimum trace factor analysis problem. We also show that for the relaxation of the low-rank plus tridiagonal decomposition problem
with regularizations on the tridiagonal matrix, the optimal solution is unique when the nonnegative
regularizing coefficient is not 2. Then, given such a coefficient λ ∈ R+ \ {2}, we consider three
problems. The first problem is decomposing a matrix into a low-rank symmetric positive semidefi-
nite matrix and a tridiagonal matrix. The second is to determine the facial structure of E′
n, which is
the set of correlation matrices whose absolute values of entries right below and above the diagonal
entries are upper bounded by λ/2. And the third problem is that given strictly positive integers k, n
with n > k, and points v1, . . . , vn ∈ Rk, determine if there exists a centered (degenerate) ellipsoid
passing through all these points exactly such that when the points are projected onto the unit ball
corresponding to the ellipsoid, for every i, the cosine value of the angle between the projected ith
and (i + 1)th points is upper bounded by λ/2 and lower bounded by −λ/2. We then prove that all
these three problems are equivalent and when the regularization coefficient λ goes to infinity, we
show the equivalence between them and the corresponding properties of the low-rank plus diagonal
decomposition problem.
We also provide a sufficient condition on a subspace U for us to find a nonempty face of
E′
n defined by U. By the equivalence above, this is also a sufficient condition for the other two
problems.
After that, we prove that the low-rank plus tridiagonal problem can be solved in polynomial time when the rank of the positive semidefinite matrix in the decomposition is bounded above by
an absolute constant.
In the end, we consider representing our problem as a conic programming problem and generalizing it to general sparsity patterns.
Fri, 19 May 2023 00:00:00 GMThttp://hdl.handle.net/10012/194632023-05-19T00:00:00ZGraph Coverings with Few Eigenvalues or No Short Cycles
http://hdl.handle.net/10012/19459
Graph Coverings with Few Eigenvalues or No Short Cycles
Levit, Maxwell
This thesis addresses the extent of the covering graph construction. How much must a cover X resemble the graph Y that it covers? How much can X deviate from Y? The main statistics of X and Y which we will measure are their regularity, the spectra of their adjacency matrices, and the length of their shortest cycles. These statistics are highly interdependent and the main contribution of this thesis is to advance our understanding of this interdependence. We will see theorems that characterize the regularity of certain covering graphs in terms of the number of distinct eigenvalues of their adjacency matrices. We will see old examples of covers whose lack of short cycles is equivalent to the concentration of their spectra on few points, and new examples that indicate certain limits to this equivalence in a more general setting. We will see connections to many combinatorial objects such as regular maps, symmetric and divisible designs, equiangular lines, distance-regular graphs, perfect codes, and more. Our main tools will come from algebraic graph theory and representation theory. Additional motivation will come from topological graph theory, finite geometry, and algebraic topology.
Thu, 18 May 2023 00:00:00 GMThttp://hdl.handle.net/10012/194592023-05-18T00:00:00ZNear-optimal quantum strategies for nonlocal games, approximate representations, and BCS algebras
http://hdl.handle.net/10012/19418
Near-optimal quantum strategies for nonlocal games, approximate representations, and BCS algebras
Paul-Paddock, Connor
Quantum correlations can be viewed as particular abstract states on the tensor product of
operator systems which model quantum measurement scenarios. In the paradigm of nonlocal games,
this perspective illustrates a connection between optimal strategies and certain
representations of a finitely presented $*$-algebra affiliated with the nonlocal game.
This algebraic interpretation of quantum correlations arising from nonlocal games has been
valuable in recent years. In particular, the connection between representations and
strategies has been useful for investigating and separating the various frameworks for
quantum correlation as well as in developing cryptographic primitives for untrusted
quantum devices. However to make use of this correspondence in a realistic setting one
needs mathematical guarantees that this correspondence is robust to noise.
We address this issue by considering the situation where the correlations are not ideal.
We show that near-optimal finite-dimensional quantum strategies using arbitrary quantum
states are approximate representations of the affiliated nonlocal game algebra for
synchronous, boolean constraint systems (BCS), and XOR nonlocal games. This result
robustly extends the correspondence between optimal strategies and finite-dimensional
representations of the nonlocal game algebras for these prominent classes of nonlocal
games. We also show that finite-dimensional approximate representations of these nonlocal
game algebras are close to near-optimal strategies employing a maximally entangled state.
As a corollary, we deduce that near-optimal quantum strategies are close to a near-optimal
quantum strategy using a maximally entangled state.
A boolean constraint system $B$ is $pp$-definable from another boolean constraint system
$B'$ if there is a $pp$-formula defining $B$ over $B'$. There is such a $pp$-formula if all the constraints in $B$ can be defined via conjunctions of relations in $B'$ using additional boolean variables if needed. We associate a finitely presented $*$-algebra, called a BCS algebra, to each boolean constraint system $B$. We show that $pp$-definability can be interpreted algebraically as $*$-homomorphisms between BCS algebras. This allows us to classify boolean constraint languages and separations between various generalized notions of satisfiability. These types of satisfiability
are motivated by nonlocal games and the various frameworks for quantum correlations and
state-independent contextuality. As an example, we construct a BCS that is $C^*$-satisfiable in the sense that it has a representation on a Hilbert space $H$ but has no tracial
representations, and thus no interpretation in terms of commuting operator correlations.
Thu, 04 May 2023 00:00:00 GMThttp://hdl.handle.net/10012/194182023-05-04T00:00:00Z