Search

We study a generalized binary search problem on the line and general trees. On the line (e.g., a sorted array), binary search finds a target node in $O(\log n)$ queries in the worst case, where $n$ is the number of nodes. In situations with limited budget or time, we might only be able to perform a few queries, possibly sub-logarithmic many. In this case, it is impossible to guarantee that the target will be found regardless of its position. Our main result is the construction of a randomized strategy that maximizes the minimum (over the target position) probability of finding the target. Such a strategy provides a natural solution where there is no apriori (stochastic) information of the target's position. As with regular binary search, we can find and run the strategy in $O(\log n)$ time (and using only $O(\log n)$ random bits). Our construction is obtained by reinterpreting the problem as a two-player (\textit{seeker} and \textit{hider}) zero-sum game and exploiting an underlying number theoretical structure. Furthermore, we generalize the setting to study a search game on trees. In this case, a query returns the edge's endpoint closest to the target. Again, when the number of queries is bounded by some given $k$, we quantify a \emph{the-less-queries-the-better} approach by defining a seeker's profit $p$ depending on the number of queries needed to locate the hider. For the linear programming formulation of the corresponding zero-sum game, we show that computing the best response for the hider (i.e., the separation problem of the underlying dual LP) can be done in time $O(n^2 2^{2k})$, where $n$ is the size of the tree. This result allows to compute a Nash equilibrium in polynomial time whenever $k=O(\log n)$. In contrast, computing the best response for the hider is NP-hard.

We study set selection problems where the weights are uncertain. Instead of its exact weight, only an uncertainty interval containing its true weight is available for each element. In some cases, some solutions are universally optimal; i.e., they are optimal for every weight that lies within the uncertainty intervals. However, it may be that no universal optimal solution exists, unless we are revealed additional information on the precise values of some elements. In the minimum cost admissible query problem, we are tasked to (non-adaptively) find a minimum-cost subset of elements that, no matter how they are revealed, guarantee the existence of a universally optimal solution. We introduce thresholds under uncertainty to analyze problems of minimum cost admissible queries. Roughly speaking, for every element e, there is a threshold for its weight, below which e is included in all optimal solutions and a second threshold above which e is excluded from all optimal solutions. We show that computing thresholds and finding minimum cost admissible queries are essentially equivalent problems. Thus, the analysis of the minimum admissible query problem reduces to the problem of computing thresholds. We provide efficient algorithms for computing thresholds in the settings of minimum spanning trees, matroids, and matchings in trees; and NP-hardness results in the settings of s-t shortest paths and bipartite matching. By making use of the equivalence between the two problems these results translate into efficient algorithms for minimum cost admissible queries in the settings of minimum spanning trees, matroids, and matchings in trees; and NP-hardness results in the settings of s-t shortest paths and bipartite matching.

Symmetry handling inequalities (SHIs) are an appealing and popular tool for handling symmetries in integer programming. Despite their practical application, little is known about their interaction with optimization problems. This article focuses on Schreier-Sims (SST) cuts, a recently introduced family of SHIs, and investigate their impact on the computational and polyhedral complexity of optimization problems. Given that SST cuts are not unique, a crucial question is to understand how different constructions of SST cuts influence the solving process. First, we observe that SST cuts do not increase the computational complexity of solving a linear optimization problem over any polytope $P$. However, separating the integer hull of $P$ enriched by SST cuts can be NP-hard, even if $P$ is integral and has a compact formulation. We study this phenomenon more in-depth for the stable set problem, particularly for subclasses of perfect graphs. For bipartite graphs, we give a complete characterization of the integer hull after adding SST cuts based on odd-cycle inequalities. For trivially perfect graphs, we observe that the separation problem is still NP-hard after adding a generic set of SST cuts. Our main contribution is to identify a specific class of SST cuts, called stringent SST cuts, that keeps the separation problem polynomial and a complete set of inequalities, namely SST clique cuts, that yield a complete linear description. We complement these results by giving SST cuts based presolving techniques and provide a computational study to compare the different approaches. In particular, our newly identified stringent SST cuts dominate other approaches.

We consider box-constrained integer programs with objective $g(Wx) + c^T x$, where $g$ is a "complicated" function with an $m$ dimensional domain. Here we assume we have $n \gg m$ variables and that $W \in \mathbb Z^{m \times n}$ is an integer matrix with coefficients of absolute value at most $\Delta$. We design an algorithm for this problem using only the mild assumption that the objective can be optimized efficiently when all but $m$ variables are fixed, yielding a running time of $n^m(m \Delta)^{O(m^2)}$. Moreover, we can avoid the term $n^m$ in several special cases, in particular when $c = 0$. Our approach can be applied in a variety of settings, generalizing several recent results. An important application are convex objectives of low domain dimension, where we imply a recent result by Hunkenschr\"oder et al. [SIOPT'22] for the 0-1-hypercube and sharp or separable convex $g$, assuming $W$ is given explicitly. By avoiding the direct use of proximity results, which only holds when $g$ is separable or sharp, we match their running time and generalize it for arbitrary convex functions. In the case where the objective is only accessible by an oracle and $W$ is unknown, we further show that their proximity framework can be implemented in $n (m \Delta)^{O(m^2)}$-time instead of $n (m \Delta)^{O(m^3)}$. Lastly, we extend the result by Eisenbrand and Weismantel [SODA'17, TALG'20] for integer programs with few constraints to a mixed-integer linear program setting where integer variables appear in only a small number of different constraints., Comment: To appear at IPCO 2023

Symmetry handling inequalities (SHIs) are a popular tool to handle symmetries in integer programming. Despite their successful application in practice, only little is known about the interaction of SHIs with optimization problems. In this article, we focus on SST cuts, an attractive class of SHIs, and investigate their computational and polyhedral consequences for optimization problems. After showing that they do not increase the computational complexity of solving optimization problems, we focus on the stable set problem for which we derive presolving techniques based on SST cuts. Moreover, we derive strengthened versions of SST cuts and identify cases in which adding these inequalities to the stable set polytope maintains integrality. Preliminary computational experiments show that our techniques have a high potential to reduce both the size of stable set problems and the time to solve them.

Understanding the strategic behavior of miners in a blockchain is of great importance for its proper operation. A common model for mining games considers an infinite time horizon, with players optimizing asymptotic average objectives. Implicitly, this assumes that the asymptotic behaviors are realized at human-scale times, otherwise invalidating current models. We study the mining game utilizing Markov Decision Processes. Our approach allows us to describe the asymptotic behavior of the game in terms of the stationary distribution of the induced Markov chain. We focus on a model with two players under immediate release, assuming two different objectives: the (asymptotic) average reward per turn and the (asymptotic) percentage of obtained blocks. Using tools from Markov chain analysis, we show the existence of a strategy achieving slow mixing times, exponential in the policy parameters. This result emphasizes the imperative need to understand convergence rates in mining games, validating the standard models. Towards this end, we provide upper bounds for the mixing time of certain meaningful classes of strategies. This result yields criteria for establishing that long-term averaged functions are coherent as payoff functions. Moreover, by studying hitting times, we provide a criterion to validate the common simplification of considering finite states models. For both considered objectives functions, we provide explicit formulae depending on the stationary distribution of the underlying Markov chain. In particular, this shows that both mentioned objectives are not equivalent. Finally, we perform a market share case study in a particular regime of the game. More precisely, we show that an strategic player with a sufficiently large processing power can impose negative revenue on honest players.

We consider a classical scheduling problem on $m$ identical machines. For an arbitrary constant $q>1$, the aim is to assign jobs to machines such that $\sum_{i=1}^m C_i^q$ is minimized, where $C_i$ is the total processing time of jobs assigned to machine $i$. It is well known that this problem is strongly NP-hard. Under mild assumptions, the running time of an $(1+\epsilon)$-approximation algorithm for a strongly NP-hard problem cannot be polynomial on $1/\epsilon$, unless $\text{P}=\text{NP}$. For most problems in the literature, this translates into algorithms with running time at least as large as $2^{\Omega(1/\varepsilon)}+n^{O(1)}$. For the natural scheduling problem above, we establish the existence of an algorithm which violates this threshold. More precisely, we design a PTAS that runs in $2^{\tilde{O}(\sqrt{1/\epsilon})}+n^{O(1)}$ time. This result is in sharp contrast to the closely related minimum makespan variant, where an exponential lower bound is known under the exponential time hypothesis (ETH). We complement our result with an essentially matching lower bound on the running time, showing that our algorithm is best-possible under ETH. The lower bound proof exploits new number-theoretical constructions for variants of progression-free sets, which might be of independent interest. Furthermore, we provide a fine-grained characterization on the running time of a PTAS for this problem depending on the relation between $\epsilon$ and the number of machines $m$. More precisely, our lower bound only holds when $m=\Theta(\sqrt{1/\epsilon})$. Better algorithms, that go beyond the lower bound, exist for other values of $m$. In particular, there even exists an algorithm with running time polynomial in $1/\epsilon$ if we restrict ourselves to instances with $m=\Omega(1/\epsilon\log^21/\epsilon)$.

Breaking symmetries is a popular way of speeding up the branch-and-bound method for symmetric integer programs. We study fundamental domains, which are minimal and closed symmetry breaking polyhedra. Our long-term goal is to understand the relationship between the complexity of such polyhedra and their symmetry breaking capability. Borrowing ideas from geometric group theory, we provide structural properties that relate the action of the group with the geometry of the facets of fundamental domains. Inspired by these insights, we provide a new generalized construction for fundamental domains, which we call generalized Dirichlet domain (GDD). Our construction is recursive and exploits the coset decomposition of the subgroups that fix given vectors in $\mathbb{R}^n$. We use this construction to analyze a recently introduced set of symmetry breaking inequalities by Salvagnin (2018) and Liberti and Ostrowski (2014), called Schreier-Sims inequalities. In particular, this shows that every permutation group admits a fundamental domain with less than $n$ facets. We also show that this bound is tight. Finally, we prove that the Schreier-Sims inequalities can contain an exponential number of isomorphic binary vectors for a given permutation group $G$, which provides evidence of the lack of symmetry breaking effectiveness of this fundamental domain. Conversely, a suitably constructed GDD for this $G$ has linearly many inequalities and contains unique representatives for isomorphic binary vectors.

Obtaining strong linear relaxations of capacitated covering problems constitute a major technical challenge even for simple settings. For one of the most basic cases, the Knapsack-Cover (Min-Knapsack) problem, the relaxation based on knapsack-cover inequalities achieves an integrality gap of 2. These inequalities have been exploited in more general environments, many of which admit primal-dual approximation algorithms. Inspired by problems from power and transport systems, we introduce a new general setting in which items can be taken fractionally to cover a given demand. The cost incurred by an item is given by an arbitrary non-decreasing function of the chosen fraction. We generalize the knapsack-cover inequalities to this setting an use them to obtain a $(2+\varepsilon)$-approximate primal-dual algorithm. Our procedure has a natural interpretation as a bucket-filling algorithm, which effectively balances the difficulties given by having different slopes in the cost functions: when some superior portion of an item presents a low slope, it helps to increase the priority with which the inferior portions may be taken. We also present a rounding algorithm with an approximation guarantee of 2. We generalize our algorithm to the Unsplittable Flow-Cover problem on a line, also for the setting where items can be taken fractionally. For this problem we obtain a $(4+\varepsilon)$-approximation algorithm in polynomial time, almost matching the $4$-approximation known for the classical setting.

We consider a natural generalization of classical scheduling problems in which using a time unit for processing a job causes some time-dependent cost which must be paid in addition to the standard scheduling cost. We study the scheduling objectives of minimizing the makespan and the sum of (weighted) completion times. It is not difficult to derive a polynomial-time algorithm for preemptive scheduling to minimize the makespan on unrelated machines. The problem of minimizing the total (weighted) completion time is considerably harder, even on a single machine. We present a polynomial-time algorithm that computes for any given sequence of jobs an optimal schedule, i.e., the optimal set of time-slots to be used for scheduling jobs according to the given sequence. This result is based on dynamic programming using a subtle analysis of the structure of optimal solutions and a potential function argument. With this algorithm, we solve the unweighted problem optimally in polynomial time. For the more general problem, in which jobs may have individual weights, we develop a polynomial-time approximation scheme (PTAS) based on a dual scheduling approach introduced for scheduling on a machine of varying speed. As the weighted problem is strongly NP-hard, our PTAS is the best possible approximation we can hope for., Comment: 17 pages; A preliminary version of this paper with a subset of results appeared in the Proceedings of MFCS 2015

The min-cost matching problem suffers from being very sensitive to small changes of the input. Even in a simple setting, e.g., when the costs come from the metric on the line, adding two nodes to the input might change the optimal solution completely. On the other hand, one expects that small changes in the input should incur only small changes on the constructed solutions, measured as the number of modified edges. We introduce a two-stage model where we study the trade-off between quality and robustness of solutions. In the first stage we are given a set of nodes in a metric space and we must compute a perfect matching. In the second stage $2k$ new nodes appear and we must adapt the solution to a perfect matching for the new instance. We say that an algorithm is $(\alpha,\beta)$-robust if the solutions constructed in both stages are $\alpha$-approximate with respect to min-cost perfect matchings, and if the number of edges deleted from the first stage matching is at most $\beta k$. Hence, $\alpha$ measures the quality of the algorithm and $\beta$ its robustness. In this setting we aim to balance both measures by deriving algorithms for constant $\alpha$ and $\beta$. We show that there exists an algorithm that is $(3,1)$-robust for any metric if one knows the number $2k$ of arriving nodes in advance. For the case that $k$ is unknown the situation is significantly more involved. We study this setting under the metric on the line and devise a $(10,2)$-robust algorithm that constructs a solution with a recursive structure that carefully balances cost and redundancy.

The Sum of Squares (\sos{}) hierarchy gives an automatized technique to create a family of increasingly tight convex relaxations for binary programs. There are several problems for which a constant number of rounds of this hierarchy give integrality gaps matching the best known approximation algorithms. For many other problems, however, ad-hoc techniques give better approximation ratios than \sos{} in the worst case, as shown by corresponding lower bound instances. Notably, in many cases these instances are invariant under the action of a large permutation group. This yields the question how symmetries in a formulation degrade the performance of the relaxation obtained by the \sos{} hierarchy. In this paper, we study this for the case of the minimum makespan problem on identical machines. Our first result is to show that $\Omega(n)$ rounds of \sos{} applied over the \emph{configuration linear program} yields an integrality gap of at least $1.0009$, where $n$ is the number of jobs. Our result is based on tools from representation theory of symmetric groups. Then, we consider the weaker \emph{assignment linear program} and add a well chosen set of symmetry breaking inequalities that removes a subset of the machine permutation symmetries. We show that applying $2^{\tilde{O}(1/\varepsilon^2)}$ rounds of the SA hierarchy to this stronger linear program reduces the integrality gap to $1+\varepsilon$, which yields a linear programming based polynomial time approximation scheme. Our results suggest that for this classical problem, symmetries were the main barrier preventing the \sos{}/ SA hierarchies to give relaxations of polynomial complexity with an integrality gap of~$1+\varepsilon$. We leave as an open question whether this phenomenon occurs for other symmetric problems.

In the Steiner Forest problem, we are given a graph and a collection of source-sink pairs, and the goal is to find a subgraph of minimum total length such that all pairs are connected. The problem is APX-Hard and can be 2-approximated by, e.g., the elegant primal-dual algorithm of Agrawal, Klein, and Ravi from 1995. We give a local-search-based constant-factor approximation for the problem. Local search brings in new techniques to an area that has for long not seen any improvements and might be a step towards a combinatorial algorithm for the more general survivable network design problem. Moreover, local search was an essential tool to tackle the dynamic MST/Steiner Tree problem, whereas dynamic Steiner Forest is still wide open. It is easy to see that any constant factor local search algorithm requires steps that add/drop many edges together. We propose natural local moves which, at each step, either (a) add a shortest path in the current graph and then drop a bunch of inessential edges, or (b) add a set of edges to the current solution. This second type of moves is motivated by the potential function we use to measure progress, combining the cost of the solution with a penalty for each connected component. Our carefully-chosen local moves and potential function work in tandem to eliminate bad local minima that arise when using more traditional local moves., Comment: 46 pages, 22 figures

We present a general approximation framework for weighted integer covering problems. In a weighted integer covering problem, the goal is to determine a non-negative integer solution $x$ to system $\{ Ax \geq r \}$ minimizing a non-negative cost function $c^T x$ (of appropriate dimensions). All coefficients in matrix $A$ are assumed to be non-negative. We analyze the performance of a very simple primal-dual greedy algorithm and discuss conditions of system $(A,r)$ that guarantee feasibility of the constructed solutions, and a bounded approximation factor. We call system $(A,r)$ a \emph{greedy system} if it satisfies certain properties introduced in this work. These properties highly rely on monotonicity and supermodularity conditions on $A$ and $r$, and can thus be seen as a far reaching generalization of contra-polymatroids. Given a greedy system $(A,r)$, we carefully construct a truncated system $(A',r)$ containing the same integer feasible points. We show that our primal-dual greedy algorithm when applied to the truncated system $(A',r)$ obtains a feasible solution to $(A,r)$ with approximation factor at most $2\delta + 1$, or $2\delta$ if $r$ is non-negative. Here, $\delta$ is some characteristic of the truncated matrix $A'$ which is small in many applications. The analysis is shown to be tight up to constant factors. We also provide an approximation factor of $k (\delta + 1)$ if the greedy algorithm is applied to the intersection of multiple greedy systems. The parameter $k$ is always bounded by the number of greedy systems but may be much smaller. Again, we show that the dependency on $k$ is tight. We conclude this paper with an exposition of classical approximation results based on primal-dual algorithms that are covered by our framework. We match all of the known results. Additionally, we provide some new insight in a generalization of the flow cover on a line problem.

We consider the following single-machine scheduling problem, which is often denoted $1||\sum f_{j}$: we are given $n$ jobs to be scheduled on a single machine, where each job $j$ has an integral processing time $p_j$, and there is a nondecreasing, nonnegative cost function $f_j(C_{j})$ that specifies the cost of finishing $j$ at time $C_{j}$; the objective is to minimize $\sum_{j=1}^n f_j(C_j)$. Bansal \& Pruhs recently gave the first constant approximation algorithm with a performance guarantee of 16. We improve on this result by giving a primal-dual pseudo-polynomial-time algorithm based on the recently introduced knapsack-cover inequalities. The algorithm finds a schedule of cost at most four times the constructed dual solution. Although we show that this bound is tight for our algorithm, we leave open the question of whether the integrality gap of the LP is less than 4. Finally, we show how the technique can be adapted to yield, for any $\epsilon >0$, a $(4+\epsilon )$-approximation algorithm for this problem., Comment: 26 pages. A preliminary version appeared in APPROX 2011. arXiv admin note: text overlap with arXiv:1403.0298

Online models that allow recourse are highly effective in situations where classical models are too pessimistic. One such problem is the online machine covering problem on identical machines. In this setting, jobs arrive one by one and must be assigned to machines with the objective of maximizing the minimum machine load. When a job arrives, we are allowed to reassign some jobs as long as their total size is (at most) proportional to the processing time of the arriving job. The proportionality constant is called the migration factor of the algorithm. Using a rounding procedure with useful structural properties for online packing and covering problems, we design first a simple $(1.7 + \varepsilon)$-competitive algorithm using a migration factor of $O(1/\varepsilon)$ which maintains at every arrival a locally optimal solution with respect to the Jump neighborhood. After that, we present as our main contribution a more involved $(4/3+\varepsilon)$-competitive algorithm using a migration factor of $\tilde{O}(1/\varepsilon^3)$. At every arrival, we run an adaptation of the Largest Processing Time first (LPT) algorithm. Since the new job can cause a complete change of the assignment of smaller jobs in both cases, a low migration factor is achieved by carefully exploiting the highly symmetric structure obtained by the rounding procedure., Comment: 26 pages, 3 figures; full version of ESA 2018 paper

Makespan scheduling on identical machines is one of the most basic and fundamental packing problems studied in the discrete optimization literature. It asks for an assignment of $n$ jobs to a set of $m$ identical machines that minimizes the makespan. The problem is strongly NP-hard, and thus we do not expect a $(1+\epsilon)$-approximation algorithm with a running time that depends polynomially on $1/\epsilon$. Furthermore, Chen et al. [3] recently showed that a running time of $2^{(1/\epsilon)^{1-\delta}}+\text{poly}(n)$ for any $\delta>0$ would imply that the Exponential Time Hypothesis (ETH) fails. A long sequence of algorithms have been developed that try to obtain low dependencies on $1/\epsilon$, the better of which achieves a running time of $2^{\tilde{O}(1/\epsilon^2)}+O(n\log n)$ [11]. In this paper we obtain an algorithm with a running time of $2^{\tilde{O}(1/\epsilon)}+O(n\log n)$, which is tight under ETH up to logarithmic factors on the exponent. Our main technical contribution is a new structural result on the configuration-IP. More precisely, we show the existence of a highly symmetric and sparse optimal solution, in which all but a constant number of machines are assigned a configuration with small support. This structure can then be exploited by integer programming techniques and enumeration. We believe that our structural result is of independent interest and should find applications to other settings. In particular, we show how the structure can be applied to the minimum makespan problem on related machines and to a larger class of objective functions on parallel machines. For all these cases we obtain an efficient PTAS with running time $2^{\tilde{O}(1/\epsilon)} + \text{poly}(n)$., Comment: 20 pages, ICALP 2016

We consider a single machine scheduling problem that seeks to minimize a generalized cost function: given a subset of jobs we must order them so as to minimize $\sum f_j(C_j)$, where $C_j$ is the completion time of job $j$ and $f_j$ is a job-dependent cost function. This problem has received a considerably amount of attention lately, partly because it generalizes a large number of sequencing problems while still allowing constant approximation guarantees. In a recent paper, Cheung and Shmoys provided a primal-dual algorithm for the problem and claimed that is a 2-approximation. In this paper we show that their analysis cannot yield an approximation guarantee better than $4$. We then cast their algorithm as a local ratio algorithm and show that in fact it has an approximation ratio of $4$. Additionally, we consider a more general problem where jobs has release dates and can be preempted. For this version we give a $4\kappa$-approximation algorithm where $\kappa$ is the number of distinct release dates., Comment: This paper has been withdrawn due to new merged paper arXiv:1612.03339

We study scheduling problems on a machine with varying speed. Assuming a known speed function we ask for a cost-efficient scheduling solution. Our main result is a PTAS for minimizing the total weighted completion time in this setting. This also implies a PTAS for the closely related problem of scheduling to minimize generalized global cost functions. The key to our results is a re-interpretation of the problem within the well-known two-dimensional Gantt chart: instead of the standard approach of scheduling in the {\em time-dimension}, we construct scheduling solutions in the weight-dimension. We also consider a dynamic problem variant in which deciding upon the speed is part of the scheduling problem and we are interested in the tradeoff between scheduling cost and speed-scaling cost, which is typically the energy consumption. We observe that the optimal order is independent of the energy consumption and that the problem can be reduced to the setting where the speed of the machine is fixed, and thus admits a PTAS. Furthermore, we provide an FPTAS for the NP-hard problem variant in which the machine can run only on a fixed number of discrete speeds. Finally, we show how our results can be used to obtain a~$(2+\eps)$-approximation for scheduling preemptive jobs with release dates on multiple identical parallel machines.

One of the most important open problems in machine scheduling is the problem of scheduling a set of jobs on unrelated machines to minimize the makespan. The best known approximation algorithm for this problem guarantees an approximation factor of 2. It is known to be NP-hard to approximate with a better ratio than 3/2. Closing this gap has been open for over 20 years. The best known approximation factors are achieved by LP-based algorithms. The strongest known linear program formulation for the problem is the configuration-LP. We show that the configuration-LP has an integrality gap of 2 even for the special case of unrelated graph balancing, where each job can be assigned to at most two machines. In particular, our result implies that a large family of cuts does not help to diminish the integrality gap of the canonical assignment-LP. Also, we present cases of the problem which can be approximated with a better factor than 2. They constitute valuable insights for constructing an NP-hardness reduction which improves the known lower bound. Very recently Svensson studied the restricted assignment case, where each job can only be assigned to a given set of machines on which it has the same processing time. He shows that in this setting the configuration-LP has an integrality gap of 33/17<2. Hence, our result imply that the unrelated graph balancing case is significantly more complex than the restricted assignment case. Then we turn to another objective function: maximizing the minimum machine load. For the case that every job can be assigned to at most two machines we give a purely combinatorial 2-approximation algorithm which is best possible, unless P=NP. This improves on the computationally costly LP-based (2+eps)-approximation algorithm by Chakrabarty et al., Comment: 12 pages, 1 figure