- Award ID(s):
- 1714818
- NSF-PAR ID:
- 10310212
- Date Published:
- Journal Name:
- Mathematical Programming
- Volume:
- 183
- Issue:
- 1-2
- ISSN:
- 0025-5610
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
Interval scheduling is a basic problem in the theory of algorithms and a classical task in combinatorial optimization. We develop a set of techniques for partitioning and grouping jobs based on their starting and ending times, that enable us to view an instance of interval scheduling on many jobs as a union of multiple interval scheduling instances, each containing only a few jobs. Instantiating these techniques in dynamic and local settings of computation leads to several new results. For (1+ε)-approximation of job scheduling of n jobs on a single machine, we develop a fully dynamic algorithm with O((log n)/ε) update and O(log n) query worst-case time. Further, we design a local computation algorithm that uses only O((log N)/ε) queries when all jobs are length at least 1 and have starting/ending times within [0,N]. Our techniques are also applicable in a setting where jobs have rewards/weights. For this case we design a fully dynamic deterministic algorithm whose worst-case update and query time are poly(log n,1/ε). Equivalently, this is the first algorithm that maintains a (1+ε)-approximation of the maximum independent set of a collection of weighted intervals in poly(log n,1/ε) time updates/queries. This is an exponential improvement in 1/ε over the running time of a randomized algorithm of Henzinger, Neumann, and Wiese [SoCG, 2020], while also removing all dependence on the values of the jobs' starting/ending times and rewards, as well as removing the need for any randomness. We also extend our approaches for interval scheduling on a single machine to examine the setting with M machines.more » « less
-
Interval scheduling is a basic problem in the theory of algorithms and a classical task in combinatorial optimization. We develop a set of techniques for partitioning and grouping jobs based on their starting and ending times, that enable us to view an instance of interval scheduling on many jobs as a union of multiple interval scheduling instances, each containing only a few jobs. Instantiating these techniques in dynamic and local settings of computation leads to several new results. For (1+ε)-approximation of job scheduling of n jobs on a single machine, we develop a fully dynamic algorithm with O((log n)/ε) update and O(log n) query worst-case time. Further, we design a local computation algorithm that uses only O((log N)/ε) queries when all jobs are length at least 1 and have starting/ending times within [0,N]. Our techniques are also applicable in a setting where jobs have rewards/weights. For this case we design a fully dynamic deterministic algorithm whose worst-case update and query time are poly(log n,1/ε). Equivalently, this is the first algorithm that maintains a (1+ε)-approximation of the maximum independent set of a collection of weighted intervals in poly(log n,1/ε) time updates/queries. This is an exponential improvement in 1/ε over the running time of a randomized algorithm of Henzinger, Neumann, and Wiese [SoCG, 2020], while also removing all dependence on the values of the jobs' starting/ending times and rewards, as well as removing the need for any randomness. We also extend our approaches for interval scheduling on a single machine to examine the setting with M machines.more » « less
-
Abstract In this paper, we study multistage stochastic mixed-integer nonlinear programs (MS-MINLP). This general class of problems encompasses, as important special cases, multistage stochastic convex optimization with
non-Lipschitzian value functions and multistage stochastic mixed-integer linear optimization. We develop stochastic dual dynamic programming (SDDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. The key ingredient is a new type of cuts based on generalized conjugacy. Several interesting classes of MS-MINLP are identified, where the new algorithms are guaranteed to obtain the global optimum without the assumption of complete recourse. This significantly generalizes the classic SDDP algorithms. We also characterize the iteration complexity of the proposed algorithms. In particular, for a -stage stochastic MINLP satisfying$$(T+1)$$ L -exact Lipschitz regularization withd -dimensional state spaces, to obtain an -optimal root node solution, we prove that the number of iterations of the proposed deterministic sampling algorithm is upper bounded by$$\varepsilon $$ , and is lower bounded by$${\mathcal {O}}((\frac{2LT}{\varepsilon })^d)$$ for the general case or by$${\mathcal {O}}((\frac{LT}{4\varepsilon })^d)$$ for the convex case. This shows that the obtained complexity bounds are rather sharp. It also reveals that the iteration complexity depends$${\mathcal {O}}((\frac{LT}{8\varepsilon })^{d/2-1})$$ polynomially on the number of stages. We further show that the iteration complexity dependslinearly onT , if all the state spaces are finite sets, or if we seek a -optimal solution when the state spaces are infinite sets, i.e. allowing the optimality gap to scale with$$(T\varepsilon )$$ T . To the best of our knowledge, this is the first work that reports global optimization algorithms as well as iteration complexity results for solving such a large class of multistage stochastic programs. The iteration complexity study resolves a conjecture by the late Prof. Shabbir Ahmed in the general setting of multistage stochastic mixed-integer optimization. -
In this paper, we study the online multidimensional knapsack problem (called OMdKP) in which there is a knapsack whose capacity is represented in m dimensions, each dimension could have a different capacity. Then, n items with different scalar profit values and m-dimensional weights arrive in an online manner and the goal is to admit or decline items upon their arrival such that the total profit obtained by admitted items is maximized and the capacity of knapsack across all dimensions is respected. This is a natural generalization of the classic single-dimension knapsack problem and finds several relevant applications such as in virtual machine allocation, job scheduling, and all-or-nothing flow maximization over a graph. We develop two algorithms for OMdKP that use linear and exponential reservation functions to make online admission decisions. Our competitive analysis shows that the linear and exponential algorithms achieve the competitive ratios of O(θα ) and O(łogł(θα)), respectively, where α is the ratio between the aggregate knapsack capacity and the minimum capacity over a single dimension and θ is the ratio between the maximum and minimum item unit values. We also characterize a lower bound for the competitive ratio of any online algorithm solving OMdKP and show that the competitive ratio of our algorithm with exponential reservation function matches the lower bound up to a constant factor.more » « less
-
Abstract We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in
and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes$\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$ , by showing that$\mathcal { C}$ admits non-trivial satisfiability and/or$\mathcal { C}$ # SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial# SAT algorithm for a circuit class . Say that a symmetric Boolean function${\mathcal C}$ f (x 1,…,x n ) issparse if it outputs 1 onO (1) values of . We show that for every sparse${\sum }_{i} x_{i}$ f , and for all “typical” , faster$\mathcal { C}$ # SAT algorithms for circuits imply lower bounds against the circuit class$\mathcal { C}$ , which may be$f \circ \mathcal { C}$ stronger than itself. In particular:$\mathcal { C}$ # SAT algorithms forn k -size -circuits running in 2$\mathcal { C}$ n /n k time (for allk ) implyN E X P does not have -circuits of polynomial size.$(f \circ \mathcal { C})$ # SAT algorithms for -size$2^{n^{{\varepsilon }}}$ -circuits running in$\mathcal { C}$ time (for some$2^{n-n^{{\varepsilon }}}$ ε > 0) implyQ u a s i -N P does not have -circuits of polynomial size.$(f \circ \mathcal { C})$ Applying
# SAT algorithms from the literature, one immediate corollary of our results is thatQ u a s i -N P does not haveE M A J ∘A C C 0∘T H R circuits of polynomial size, whereE M A J is the “exact majority” function, improving previous lower bounds againstA C C 0[Williams JACM’14] andA C C 0∘T H R [Williams STOC’14], [Murray-Williams STOC’18]. This is the first nontrivial lower bound against such a circuit class.