We design a framework to obtain Fully Polynomial Time Approximation Schemes (FPTASes) for adjustable robust multistage decision making under the budgeted uncertainty sets introduced by Bertsimas and Sim. We apply this framework to the robust counterpart of three problems coming from operations research: (i) ordered knapsack, (ii) single-item inventory control, and (iii) single-item batch dispatch. Our work gives the first FPTAS for these problems, and for adjustable robust multistage decision making in general. The proposed approximation schemes are constructed with the technique of K-approximation sets and functions, relying on careful robust dynamic programming formulations for a master problem (corresponding to the decision maker) and for an adversary problem (corresponding to nature, which chooses bad realizations of uncertainty for the decision maker). The resulting algorithms are short and simple, requiring just a few concise subroutines. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This research was supported in part by the United States-Israel Binational Science foundation [Grant 2018095). N. Halman was also supported in part by the Israel Science Foundation [Grants 399/17 and 1074/21].

We describe algorithms to obtain an approximate classical description of a d-dimensional quantum state when given access to a unitary (and its inverse) that prepares it. For pure states we characterize the query complexity for ℓq-norm error up to logarithmic factors. As a special case, we show that it takes applications of the unitaries to obtain an ε-ℓ2-approximation of the state. For mixed states we consider a similar model, where the unitary prepares a purification of the state. We characterize the query complexity for obtaining Schatten q-norm estimates of a rank-r mixed state, up to polylogarithmic factors. In particular, we show that a trace-norm (q = 1) estimate can be obtained with queries. This improves (assuming our stronger input model) the ε-dependence over the works of O'Donnell and Wright (STOC 2016) and Haah et al. (IEEE Trans. Inf. Theory, 63.9, 2017), that use a joint measurement on copies of the state. To our knowledge, the most sample-efficient results for pure-state tomography come from setting the rank to 1 in generic mixed-state tomography algorithms, which can require a large amount of computing resources. We describe sample-optimal algorithms for pure states that are simple and fast to implement. Along the way we show that an ℓ∞-norm estimate of a normalized vector induces a (slightly worse) ℓq-norm estimate for that vector, without losing a dimension-dependent factor in the precision. We also develop an unbiased and symmetric version of phase estimation, where the probability distribution of the estimate is centered around the true value. Finally, we give an efficient method for estimating multiple expectation values, improving over the recent result by Huggins et al. (arXiv:2111.09283) when the measurement operators do not fully overlap. More specifically, we show that for E1,…, Em normalized measurement operators, all expectation values Tr(Ejρ) can be efficiently learned up to error ε with applications of a state-preparation unitary for a purification of ρ. * The full version of the paper can be accessed at https://arxiv.org/abs/2207.08800

We consider the problem of mapping a logical quantum circuit onto a given hardware with limited 2-qubit connectivity. We model this problem as an integer linear program, using a network flow formulation with binary variables that includes the initial allocation of qubits and their routing. We consider several cost functions: an approximation of the fidelity of the circuit, its total depth, and a measure of cross-talk, all of which can be incorporated in the model. Numerical experiments on synthetic data and different hardware topologies indicate that the error rate and depth can be optimized simultaneously without significant loss. We test our algorithm on a large number of quantum volume circuits, optimizing for error rate and depth; our algorithm significantly reduces the number of CNOTs compared to Qiskit’s default transpiler SABRE [ 19 ] and produces circuits that, when executed on hardware, exhibit higher fidelity.

Information Retrieval (IR) is the complex of activities that represent information as data and rank the data representing information relevant to the user's information needs by a retrieval function. Such a function involves parameters. They can in principle be set irrespective of the specific set of documents and queries, but can in practice maximize retrieval effectiveness. However, algorithms to select retrieval function parameters must be efficient due to the large search space. We can remark that: (i) all the tested methods are similarly effective, but the plots of the maximum value of NDCG@20 at a given evaluation show that our algorithm is more efficient; (ii) performance metrics and datasets studied in this paper seem to yield objective functions with few, if any, local optima with large basin of attraction; (iii) our algorithm is considerably more efficient, quickly finding parameterizations of the retrieval function yielding high performance - much faster than line search.

The retrieval function is one of the most important components of an Information Retrieval (IR) system, because it determines to what extent some information is relevant to a user query. Most retrieval functions have “free parameters” whose value must be set before retrieval, significantly affecting the effectiveness of an IR system. Choosing the optimum values for such parameters is therefore of paramount importance. However, the optimum can only be found after a computationally expensive process, especially when the generalization error is estimated via cross-validation. In this paper, we propose to determine free parameter values by solving an optimization problem aimed at maximizing a measure of retrieval effectiveness. We employ the black-box optimization paradigm, since the analytical expression of the measure of effectiveness with respect to the free parameters is unknown. We consider different methods for solving the black-box optimization problem: a simple grid-search over the whole domain, and more sophisticated techniques such as line search and surrogate model based algorithms. Experimental results on several test collections not only provide useful insight about effectiveness, but also about efficiency: they indicate that with appropriate optimization techniques, the computational cost of parameter optimization can be greatly reduced without compromising retrieval effectiveness, even when taking generalization into account.

Split cuts constitute a class of cutting planes that has been successfully employed by the majority of branch-and-cut solvers for mixed-integer linear programs. Given a basis of the linear programming (LP) relaxation and a split disjunction, the corresponding split cut can be computed with a closed-form expression. In this paper, we use the lift-and-project framework introduced by Balas and Perregaard to provide the basis, and the reduce-and-split algorithm as described by Cornuéjols and Nannicini to compute the split disjunction. We propose a cut generation algorithm that starts from a Gomory mixed-integer cut and alternates between lift-and-project and reduce-and-split in order to strengthen it. This paper has two main contributions. First, we extend the Balas and Perregaard procedure for strengthening cuts arising from split disjunctions involving one variable to split disjunctions on multiple variables. Second, we apply the reduce-and-split algorithm to nonoptimal bases of the LP relaxation. We provide detailed computational testing of the proposed methods.

Route planning in large-scale time-dependent road networks is an important practical application of the shortest-path problem that greatly benefits from speedup techniques. In this paper, we extend a two-level hierarchical approach for point-to-point shortest-path computations to the time-dependent case. This method, also known as core routing in the literature for static graphs, consists of the selection of a small subnetwork where most of the computations can be carried out, thus reducing the search space. We combine this approach with bidirectional goal-directed search to obtain an algorithm capable of finding shortest paths in a matter of milliseconds on continental-sized networks. Moreover, we tackle the dynamic scenario where the piecewise linear functions that we use to model time-dependent arc costs are not fixed but can have their coefficients updated requiring only a small computational effort.

Abstract The computation of point‐to‐point shortest paths on time‐dependent road networks has a large practical interest, but very few works propose efficient algorithms for this problem. We propose a novel approach, which tackles one of the main complications of route planning in time‐dependent graphs, which is the difficulty of using bidirectional search: because the exact arrival time at the destination is unknown, we start a backward search from the destination node using lower bounds on arc costs to restrict the set of nodes that have to be explored by the forward search. Our algorithm is based onA* with landmarks (ALT); extensive computational results show that it is very effective in practice if we are willing to accept a small approximation factor, resulting in a speed‐up of more than one order of magnitude with respect to Dijkstra's algorithm while finding only slightly suboptimal solutions. The main idea presented here can also be generalized to other types of search algorithms. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012