Search

In this paper, we study the minimum k-partition problem of submodular functions, i.e., given a finite set V and a submodular function f : 2 V → R , computing a k-partition { V 1 , ... , V k } of V with minimum ∑ i = 1 k f (V i) . The problem is a natural generalization of the minimum k-cut problem in graphs and hypergraphs. It is known that the problem is NP-hard for general k, and solvable in polynomial time for fixed k ≤ 3 . In this paper, we construct the first polynomial-time algorithm for the minimum 4-partition problem. [ABSTRACT FROM AUTHOR]

We consider distributed approval voting schemes. Each voter i ∈ I has α i cards that (s)he distributes among the candidates a ∈ A as a measure of approval. One (or several) candidate(s) who received the maximum number of cards is (are) elected. We provide polynomial algorithms to recognize voting forms and voting correspondences generated by such voting schemes in cases when either the number of candidates or the number of voters is equal to 2. We prove that for two voters, if α 2 ≥ α 1 - 2 ≥ 0 then the unique voting correspondence has distinct rows. We also characterize voting forms with distinct rows. [ABSTRACT FROM AUTHOR]

A function f : 2 V → R on a finite set V is posimodular if f (X) + f (Y) ≥ f (X \ Y) + f (Y \ X) , for all X , Y ⊆ V . Posimodular functions often arise in combinatorial optimization such as undirected cut functions. We consider the problem of finding a nonempty subset X minimizing f(X), when the posimodular function f is given by oracle access. We show that posimodular function minimization requires exponential time, contrasting with the polynomial solvability of submodular function minimization that forms another generalization of cut functions. On the other hand, the problem is fixed-parameter tractable in terms of the size D of the image (or range) of f. In more detail, we show that Ω (2 0.32 n T f) time is necessary and O (2 0.92 n T f) sufficient, where T f denotes the time for one function evaluation and n = | V | . When the image of f is D = { 0 , 1 , ... , d } for integer d, O (2 1.218 d n T f) time is sufficient. We can also generate all sets minimizing f in time 2 O (d) n 2 T f . Finally, we also consider the problem of maximizing a given posimodular function, showing that it requires at least 2 n - 1 T f time in general, while it has time complexity Θ (n d - 1 T f) when D = { 0 , 1 , ... , d } is the image of f, for integer d = O (n 1 / 4) . [ABSTRACT FROM AUTHOR]

We consider the game of proper Nim, in which two players alternately move by taking stones from n piles. In one move a player chooses a proper subset (at least one and at most n - 1 ) of the piles and takes some positive number of stones from each pile of the subset. The player who cannot move is the loser. Jenkyns and Mayberry (Int J Game Theory 9(1):51–63, 1980) described the Sprague–Grundy function of these games. In this paper we consider the so-called selective compound of proper Nim games with certain other games, and obtain a closed formula for the Sprague–Grundy functions of the compound games, when n ≥ 3 . Surprisingly, the case of n = 2 is much more complicated. For this case we obtain several partial results and propose some conjectures. [ABSTRACT FROM AUTHOR]

This paper studies optimal matroid partitioning problems for various objective functions. In the problem, we are given k weighted-matroids on the same ground set. Our goal is to find a feasible partition that minimizes (maximizes) the value of an objective function. A typical objective is the maximum over all subsets of the total weights of the elements in a subset, which is extensively studied in the scheduling literature. Likewise, as an objective function, we handle the maximum/minimum/sum over all subsets of the maximum/minimum/total weight(s) of the elements in a subset. In this paper, we determine the computational complexity of the optimal partitioning problem with the above-described objective functions. Namely, for each objective function, we either provide a polynomial time algorithm or prove NP-hardness. We also discuss the approximability for the NP-hard cases. [ABSTRACT FROM AUTHOR]

In this paper, we study the unit cost buyback problem, i.e., the buyback problem with a fixed cancellation cost for each canceled element. The input of the problem is a sequence of elements e1, e2,... , en where each element ei has a weight w(ei). We assume that the weights are in a known range [l, u], i.e., l ≤ w(ei) ≤ u for any i. Given the i th element ei, we either accept ei or reject it with no cost, where we can keep a set of elements that satisfies a certain constraint. In order to accept a new element ei, we can cancel some previously selected elements at a cost which is proportional to the number of elements canceled. Our goal is to maximize the profit, i.e., the total weights of elements accepted (and not canceled) minus the total cancellation cost occurred. We construct optimal online algorithms and prove that they are the best possible when the constraint is a matroid constraint or the unweighted knapsack constraint. [ABSTRACT FROM AUTHOR]

We consider the following semi-infinite linear programming problems: max (resp., min ) c T x s.t. y T A i x + (d i) T x ≤ b i (resp., y T A i x + (d i) T x ≥ b i) , for all y ∈ Y i , for i = 1 , ... , N , where Y i ⊆ R + m are given compact convex sets and A i ∈ R + m i × n , b = (b 1 , ... b N) ∈ R + N , d i ∈ R + n , and c ∈ R + n are given non-negative matrices and vectors. This general framework is useful in modeling many interesting problems. For example, it can be used to represent a sub-class of robust optimization in which the coefficients of the constraints are drawn from convex uncertainty sets Y i , and the goal is to optimize the objective function for the worst case choice in each Y i . When the uncertainty sets Y i are ellipsoids, we obtain a sub-class of second-order cone programming. We show how to extend the multiplicative weights update method to derive approximation schemes for the above packing and covering problems. When the sets Y i are simple, such as ellipsoids or boxes, this yields substantial improvements in running time over general convex programming solvers. We also consider the mixed packing/covering problem, in which both packing and covering constraints are given, and the objective is to find an approximately feasible solution. [ABSTRACT FROM AUTHOR]

In this paper, we introduce total dual integrality of the linear complementarity problem (LCP) by analogy with the linear programming problem. The main idea of defining the notion is to propose the LCP with orientation, a variant of the LCP whose feasible complementary cones are specified by an additional input vector. Then we naturally define the dual problem of the LCP with orientation and total dual integrality of the LCP. We show that if the LCP is totally dual integral, then all basic solutions are integral. If the input matrix is sufficient or rank-symmetric, and the LCP is totally dual integral, then our result implies that the LCP always has an integral solution whenever it has a solution. We also introduce a class of matrices such that any LCP instance having the matrix as a coefficient matrix is totally dual integral. We investigate relationships between matrix classes in the LCP literature such as principally unimodular matrices. Principally unimodular matrices are known that all basic solutions to the LCP are integral for any integral input vector. In addition, we show that it is coNP-hard to decide whether a given LCP instance is totally dual integral. [ABSTRACT FROM AUTHOR]

We consider two-player zero-sum stochastic mean payoff games with perfect information. We show that any such game, with a constant number of random positions and polynomially bounded positive transition probabilities, admits a polynomial time approximation scheme, both in the relative and absolute sense. [ABSTRACT FROM AUTHOR]

In this paper, we introduce maximum composition ordering problems. The input is n real functions f1,⋯,fn:R→R and a constant c∈R. We consider two settings: total and partial compositions. The maximum total composition ordering problem is to compute a permutation σ:[n]→[n] which maximizes fσ(n)∘fσ(n-1)∘⋯∘fσ(1)(c), where [n]={1,⋯,n}. The maximum partial composition ordering problem is to compute a permutation σ:[n]→[n] and a nonnegative integer k(0≤k≤n) which maximize fσ(k)∘fσ(k-1)∘⋯∘fσ(1)(c). We propose O(nlogn) time algorithms for the maximum total and partial composition ordering problems for monotone linear functions fi, which generalize linear deterioration and shortening models for the time-dependent scheduling problem. We also show that the maximum total composition ordering problem can be solved in polynomial time if fi is of the form max{aix+bi,di,x} for some constants ai(≥0), bi and di. As a corollary, we show that the two-valued free-order secretary problem can be solved in polynomial time. We finally prove that there exists no constant-factor approximation algorithm for the problems, even if fi’s are monotone, piecewise linear functions with at most two pieces, unless P = NP. [ABSTRACT FROM AUTHOR]

We suggest a new algorithm for two-person zero-sum undiscounted stochastic games focusing on stationary strategies. Given a positive real ε, let us call a stochastic game ε-ergodic, if its values from any two initial positions differ by at most ε. The proposed new algorithm outputs for every ε>0 in finite time either a pair of stationary strategies for the two players guaranteeing that the values from any initial positions are within an ε-range, or identifies two initial positions u and v and corresponding stationary strategies for the players proving that the game values starting from u and v are at least ε/24 apart. In particular, the above result shows that if a stochastic game is ε-ergodic, then there are stationary strategies for the players proving 24ε-ergodicity. This result strengthens and provides a constructive version of an existential result by Vrieze (Stochastic games with finite state and action spaces. PhD thesis, Centrum voor Wiskunde en Informatica, Amsterdam, 1980) claiming that if a stochastic game is 0-ergodic, then there are ε-optimal stationary strategies for every ε>0. The suggested algorithm is based on a potential transformation technique that changes the range of local values at all positions without changing the normal form of the game. [ABSTRACT FROM AUTHOR]

In this paper, we consider autark and linear autark assignments of Horn CNFs. We first study maximal autark assignments of Horn CNFs and devise a linear time algorithm of computing these assignments. This complements the previous work by Marek which reveals the properties of minimal autark assignments of Horn CNFs. We then consider linear autark assignments of Horn CNFs and give a combinatorial characterization of the existence of such an assignment. By making use of this characterization, we devise a linear time algorithm of finding linear autark assignments of Horn CNFs. [ABSTRACT FROM AUTHOR]

We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph $$G = (V, E)$$ , with local rewards $$r{:}\,E \rightarrow \mathbb {Z}$$ , and three types of positions: black $$V_B$$ , white $$V_W$$ , and random $$V_R$$ forming a partition of V. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, even when $$|V_R|=0$$ . In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this short note, we show that BWR-games can be solved via convex programming in pseudo-polynomial time if the number of random positions is a constant. [ABSTRACT FROM AUTHOR]

In this paper, we study the parameterized complexity of the linear complementarity problem (LCP), which is one of the most fundamental mathematical optimization problems. The parameters we focus on are the sparsities of the input and the output of the LCP: the maximum numbers of nonzero entries per row/column in the coefficient matrix and the number of nonzero entries in a solution. Our main result is to present a fixed-parameter algorithm for the LCP with the combined parameter. We also show that if we drop any of the three parameters, then the LCP is NP-hard or W[1]-hard. In addition, we show the nonexistence of a polynomial kernel for the LCP unless coNP $$\subseteq $$ NP/poly. [ABSTRACT FROM AUTHOR]

We consider Gillette's two-person zero-sum stochastic games with perfect information. For each $$k \in \mathbb {N}=\{0,1,\ldots \}$$ we introduce an effective reward function, called k-total. For $$k = 0$$ and 1 this function is known as mean payoff and total reward, respectively. We restrict our attention to the deterministic case. For all k, we prove the existence of a saddle point which can be realized by uniformly optimal pure stationary strategies. We also demonstrate that k-total reward games can be embedded into $$(k+1)$$ -total reward games. [ABSTRACT FROM AUTHOR]

In 1964 Shapley observed that a matrix has a saddle point in pure strategies whenever every its $$2 \times 2$$ submatrix has one. In contrast, a bimatrix game may have no pure strategy Nash equilibrium (NE) even when every $$2 \times 2$$ subgame has one. Nevertheless, Shapley's claim can be extended to bimatrix games as follows. We partition all $$2 \times 2$$ bimatrix games into fifteen classes $$C = \{c_1, \ldots , c_{15}\}$$ depending only on the preferences of two players. A subset $$t \subseteq C$$ is called a NE-theorem if a bimatrix game has a NE whenever it contains no subgame from t. We suggest a method to construct all minimal (that is, strongest) NE-theorems based on the procedure of joint generation of transversal hypergraphs given by a special oracle. By this method we obtain all (six) strongest NE-theorems. Let us remark that the suggested approach, which may be called 'math-pattern recognition', is very general: it allows to characterize completely an arbitrary 'target' in terms of arbitrary 'attributes'. [ABSTRACT FROM AUTHOR]

Given two bounded convex sets $$X\subseteq \mathbb R^m$$ and $$Y\subseteq \mathbb R^n,$$ specified by membership oracles, and a continuous convex-concave function $$F:X\times Y\rightarrow \mathbb R$$ , we consider the problem of computing an $$\varepsilon $$ -approximate saddle point, that is, a pair $$(x^*,y^*)\in X\times Y$$ such that $$\sup _{y\in Y} F(x^*,y)\le \inf _{x\in X}F(x,y^*)+\varepsilon .$$ Grigoriadis and Khachiyan (Oper Res Lett 18(2):53-58, ) gave a simple randomized variant of fictitious play for computing an $$\varepsilon $$ -approximate saddle point for matrix games, that is, when $$F$$ is bilinear and the sets $$X$$ and $$Y$$ are simplices. In this paper, we extend their method to the general case. In particular, we show that, for functions of constant 'width', an $$\varepsilon $$ -approximate saddle point can be computed using $$O^* \big (\frac{(n+m)}{\varepsilon ^2}\ln R \big )$$ random samples from log-concave distributions over the convex sets $$X$$ and $$Y$$ . It is assumed that $$X$$ and $$Y$$ have inscribed balls of radius $$1/R$$ and circumscribing balls of radius $$R$$ . As a consequence, we obtain a simple randomized polynomial-time algorithm that computes such an approximation faster than known methods for problems with bounded width and when $$\varepsilon \in (0,1)$$ is a fixed, but arbitrarily small constant. Our main tool for achieving this result is the combination of the randomized fictitious play with the recently developed results on sampling from convex sets. [ABSTRACT FROM AUTHOR]

In this paper, we study the online unweighted knapsack problem with removal cost. The input is a sequence of items u, u,..., u, each of which has a size and a value, where the value of each item is assumed to be equal to the size. Given the ith item u, we either put u into the knapsack or reject it with no cost. When u is put into the knapsack, some items in the knapsack are removed with removal cost if the sum of the size of u and the total size in the current knapsack exceeds the capacity of the knapsack. Here the removal cost means a cancellation charge or disposal fee. Our goal is to maximize the profit, i.e., the sum of the values of items in the last knapsack minus the total removal cost occurred. In this paper, we consider two kinds of removal cost: unit and proportional cost. For both models, we provide their competitive ratios. Namely, we construct optimal online algorithms and prove that they are best possible. [ABSTRACT FROM AUTHOR]

Given a directed or undirected graph G=( V, E), a collection ${\mathcal{R}}=\{(S_{i},T_{i}) \mid i=1,2,\ldots,|{\mathcal{R}}|, S_{i},T_{i} \subseteq V, S_{i} \cap T_{i} =\emptyset\}$ of two disjoint subsets of V, and a requirement function $r: {\mathcal{R}} \to\mathbb{R}_{+}$, we consider the problem (called area-to-area edge-connectivity augmentation problem) of augmenting G by a smallest number of new edges so that the resulting graph $\hat{G}$ satisfies $d_{\hat{G}}(X)\geq r(S,T)$ for all X⊆ V, $(S,T) \in{\mathcal{R}}$ with S⊆ X⊆ V− T, where d( X) denotes the degree of a vertex set X in G. This problem can be regarded as a natural generalization of the global, local, and node-to-area edge-connectivity augmentation problems. In this paper, we show that there exists a constant c such that the problem is inapproximable within a ratio of $c\log{|{\mathcal{R}}|}$, unless P=NP, even restricted to the directed global node-to-area edge-connectivity augmentation or undirected local node-to-area edge-connectivity augmentation. We also provide an ${\mathrm{O}}(\log{|{\mathcal{R}}|})$-approximation algorithm for the area-to-area edge-connectivity augmentation problem, which is a natural extension of Kortsarz and Nutov's algorithm (Kortsarz and Nutov, J. Comput. Syst. Sci., 74:662-670, ). This together with the negative result implies that the problem is ${\varTheta}(\log{|{\mathcal{R}}|})$-approximable, unless P=NP, which solves open problems for node-to-area edge-connectivity augmentation in Ishii et al. (Algorithmica, 56:413-436, ), Ishii and Hagiwara (Discrete Appl. Math., 154:2307-2329, ), Miwa and Ito (J. Oper. Res. Soc. Jpn., 47:224-243, ). Furthermore, we characterize the node-to-area and area-to-area edge-connectivity augmentation problems as the augmentation problems with modulotone and k-modulotone functions. [ABSTRACT FROM AUTHOR]

We present a (full) derandomization of HSSW algorithm for 3-SAT, proposed by Hofmeister, Schöning, Schuler, and Watanabe (in STACS 2002, pp. 192-202, ). Thereby, we obtain an O(1.3303)-time deterministic algorithm for 3-SAT, which is currently fastest. [ABSTRACT FROM AUTHOR]