Normal surfaces as combinatorial slicings

We investigate slicings of combinatorial manifolds as properly embedded co-dimension 1 submanifolds. Focus is given to the case of dimension 3, where slicings are (discrete) normal surfaces. For the cases of 2-neighborly 3-manifolds as well as quadrangulated slicings, lower bounds on the number of quadrilaterals of slicings depending on its genus g are presented. These are shown to be sharp for infinitely many values of g. Furthermore, we classify slicings of combinatorial 3-manifolds which are weakly neighborly polyhedral maps.     

An exact algorithm for the network pricing problem

This work focuses on an improved exact algorithm for addressing an NP-hard network pricing problem. The method involves an efficient and partial generation of candidate solutions, a recursive scheme for generating improved upper bounds, and a column generation procedure for solving the network-structured subproblems. Its efficiency is assessed against both randomly generated instances involving three distinct topologies as well as instances based on real life situations in telecommunication and freight transportation.     

GO-MOCE: Greedy Order Method of Conditional Expectations for Max Sat

In this paper we present and study a new algorithm for the Maximum Satisfiability (Max Sat) problem. The algorithm is based on the Method of Conditional Expectations (MOCE, also known as Johnson’s Algorithm) and applies a greedy variable ordering to MOCE. Thus, we name it Greedy Order MOCE (GO-MOCE). We also suggest a combination of GO-MOCE with CCLS, a state-of-the-art solver. We refer to this combined solver as GO-MOCE-CCLS.We conduct a comprehensive comparative evaluation of GO-MOCE versus MOCE on random instances and on public competition benchmark instances. We show that GO-MOCE reduces the number of unsatisfied clauses by tens of percents, while keeping the runtime almost the same. The worst case time complexity of GO-MOCE is linear. We also show that GO-MOCE-CCLS improves on CCLS consistently by up to about 80%.We study the asymptotic performance of GO-MOCE. To this end, we introduce three measures for evaluating the asymptotic performance of algorithms for Max Sat. We point out to further possible improvements of GO-MOCE, based on an empirical study of the main quantities managed by GO-MOCE during its execution.     

A two-phase algorithm for the partial accessibility constrained vehicle routing problem

In the partial accessibility constrained vehicle routing problem, a route can be covered by two types of vehicles, i.e. truck or truck + trailer. Some customers are accessible by both vehicle types, whereas others solely by trucks. After introducing an integer programming formulation for the problem, we describe a two-phase heuristic method which extends a classical vehicle routing algorithm. Since it is necessary to solve a combinatorial problem that has some similarities with the generalized assignment problem, we propose an enumerative procedure in which bounds are obtained from a Lagrangian relaxation. The routine provides very encouraging results on a set of test problems.     

Combinatorial approximation algorithms: a comparative review

This paper is a comparative review of three related books:Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, Marco Protasi, Complexity and Approximation (Combinatorial Optimization Problems and Their Approximability Properties), second printing, Springer, Berlin, 2003, ISBN 3-540-65431-3, 524 pp., €53.45 (first printing 1999).Juraj Hromkovi?, Algorithmics for Hard Problems (Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics), second edition, Springer, Berlin, 2003, ISBN 3-540-44134-4, 544 pp., €53.45 (first printing 2001).Vijay Vazirani, Approximation Algorithms, second printing, Springer, Berlin, 2002, ISBN 3-540-65367-8, 380 pp., €37.40 (first printing 2001).     

Approximation of the supply scheduling problem

The supply scheduling problem consists in finding a minimum cost delivery plan from a set of providers to a manufacturing unit, subject to given bounds on the shipment sizes and subject to the demand at the manufacturing unit. We provide a fully polynomial time approximation scheme for this problem.     

The union of minimal hitting sets: Parameterized combinatorial bounds and counting

A k-hitting set in a hypergraph is a set of at most k vertices that intersects all hyperedges. We study the union of all inclusion-minimal k-hitting sets in hypergraphs of rank r (where the rank is the maximum size of hyperedges). We show that this union is relevant for certain combinatorial inference problems and give worst-case bounds on its size, depending on r and k. For r=2 our result is tight, and for each r3 we have an asymptotically optimal bound and make progress regarding the constant factor. The exact worst-case size for r3 remains an open problem. We also propose an algorithm for counting all k-hitting sets in hypergraphs of rank r. Its asymptotic runtime matches the best one known for the much more special problem of finding one k-hitting set. The results are used for efficient counting of k-hitting sets that contain any particular vertex.     

Indecomposable permutations, hypermaps and labeled Dyck paths

Hypermaps were introduced as an algebraic tool for the representation of embeddings of graphs on an orientable surface. Recently a bijection was given between hypermaps and indecomposable permutations; this sheds new light on the subject by connecting a hypermap to a simpler object. In this paper, a bijection between indecomposable permutations and labeled Dyck paths is proposed, from which a few enumerative results concerning hypermaps and maps follow. We obtain for instance an inductive formula for the number of hypermaps with n darts, p vertices and q hyperedges; the latter is also the number of indecomposable permutations of Sn with p cycles and q left-to-right maxima. The distribution of these parameters among all permutations is also considered.