Search

Given a system (V,T,f,k), whereVis a finite set,is a submodular function andk=2 is an integer, the generalmultiway partition problem(MPP) asks to find ak-partition={V1,V2,...,V k} ofVthat satisfiesfor alliand minimizesf(V1)+f(V2)+···+f(V k), whereis ak-partition ofhold. MPP formulation captures a generalization in submodular systems of many NP-hard problems such ask-way cut,multiterminal cut,target splitand their generalizations in hypergraphs. This paper presents a simple and unified framework for developing and analyzing approximation algorithms for various MPPs. [ABSTRACT FROM AUTHOR]

Abstract. For an edge-weighted graph G with n vertices and m edges, we present a new deterministic algorithm for computing a minimum k-way cut for k = 3, 4. The algorithm runs in O(n[sup k-1]F(n, m)) = O(mn[sup k] log(n[sup 2]/m)) time and O(n[sup 2]) space for k = 3, 4, where F(n, m) denotes the time bound required to solve the maximum flow problem in G. The bound for k = 3 matches the current best deterministic bound O(mn[sup 3]) for weighted graphs, but improves the bound O(mn[sup 3]) to O(n[sup 2] F(n, m)) = O(min(mn[sup 8/3], m[sup 3/2]n[sup 2])) for unweighted graphs. The bound O(mn[sup 4]) for k = 4 improves the previous best randomized bound O(n[sup 6]) (for m = o(n[sup 2])). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system. [ABSTRACT FROM AUTHOR]

Abstract. Combinatorial optimization games deal with cooperative games for which the value of every subset of players is obtained by solving a combinatorial optimization problem on the resources collectively owned by this subset. A solution of the game is in the core if no subset of players is able m gain advantage by breaking away from this collective decision of all players. The game is totally balanced if and only if the core is non-empty for every induced subgame of it. We study the total balancedness of several combinatorial optimization games in this paper. For a class of the partition game [5], we have a complete characterization for the total balancedness. For the packing and covering games [3], we completely clarify the relationship between the related primal/dual linear programs for the corresponding games to be totally balanced. Our work opens up the question of fully characterizing the combinatorial structures of totally balanced packing and covering games, for which we present some interesting examples: the totally balanced matching, vertex cover, and minimum coloring games. [ABSTRACT FROM AUTHOR]

MAX-2-SAT is one of the representative combinatorial problems and is known to be NP-hard. Given a set of m clauses on n propositional variables, where each clause contains at most two literals and is weighted by a positive real, MAX-2-SAT asks to find a truth assignment that maximizes the total weight of satisfied clauses. In this paper, we propose branch-and-bound exact algorithms for MAX-2-SAT utilizing three kinds of lower bounds. All lower bounds are based on a directed graph that represents conflicts among clauses, and two of them use a set covering representation of MAX-2-SAT. Computational comparisons on benchmark instances disclose that these algorithms are highly effective in reducing the number of search tree nodes as well as the computation time. [ABSTRACT FROM AUTHOR]