Home

Gregory Gutin

  1. On the Parameterized Complexity of the Workflow Satisfiability Problem.

    Mon, 05/07/2012 - 15:01 — SomNambul
    Authors: Gregory Gutin, Anders Yeo, Jason Crampton
    Subjects: Cryptography and Security
    Abstract

    A workflow specification defines a set of steps and the order in which those
    steps must be executed. Security requirements may impose constraints on which
    groups of users are permitted to perform subsets of those steps. A workflow
    specification is said to be satisfiable if there exists an assignment of users
    to workflow steps that satisfies all the constraints. An algorithm for
    determining whether such an assignment exists is important, both as a static
    analysis tool for workflow specifications, and for the construction of run-time
    reference monitors for workflow management systems.

  2. Local Search Algorithms for the Generalized Traveling Salesman Problem.

    Tue, 06/01/2010 - 15:01 — SomNambul
    Authors: Gregory Gutin, Daniel Karapetyan
    Subjects: Data Structures and Algorithms
    Abstract

    The Generalized Traveling Salesman Problem (GTSP) is a well-known
    combinatorial optimization problem with a host of applications. It is an
    extension of the Traveling Salesman Problem (TSP) where the set of cities is
    divided into so-called clusters, and the salesman have to visit each cluster
    exactly once.

  3. All Ternary Permutation Constraint Satisfaction Problems Parameterized Above Average Have Polynomial Kernels.

    Tue, 04/13/2010 - 15:02 — SomNambul
    Authors: Gregory Gutin, Leo van Iersel, Matthias Mnich, Anders Yeo
    Subjects: Data Structures and Algorithms
    Abstract

    A ternary Permutation-CSP is specified by a subset $\Pi$ of the symmetric
    group $\mathcal S_3$. An instance of such a problem consists of a set of
    variables $V$ and a multiset of constraints, which are ordered triples of
    distinct variables of $V.$ The objective is to find a linear ordering $\alpha$
    of $V$ that maximizes the number of triples whose ordering (under $\alpha$)
    follows a permutation in $\Pi$. We prove that all ternary Permutation-CSPs
    parameterized above average have polynomial-size kernels.

  4. Lin-Kernighan Heuristic Adaptation for the Generalized Traveling Salesman Problem.

    Tue, 03/30/2010 - 15:02 — SomNambul
    Authors: Gregory Gutin, Daniel Karapetyan
    Subjects: Data Structures and Algorithms
    Abstract

    Lin-Kernighan heuristic is known to be one of the most successful heuristics
    for the Traveling Salesman Problem (TSP). It has also proven its efficiency in
    application to some other problems. However, it was never applied to the the
    Generalized Traveling Salesman Problem (GTSP) though it has the same nature as
    TSP. In this paper we discuss possible adaptations of TSP heuristics for GTSP
    and focus on the case of Lin-Kernighan algorithm. At first, we provide an
    easy-to-understand description of the original Lin-Kernighan heuristic.

  5. A New Approach to Population Sizing for Memetic Algorithms: A Case Study for the Multidimensional Assignment Problem.

    Wed, 03/24/2010 - 16:01 — SomNambul
    Authors: Gregory Gutin, Daniel Karapetyan
    Subjects: Data Structures and Algorithms
    Abstract

    Memetic Algorithms are known to be a powerful technique in solving hard
    optimization problems. To design a memetic algorithm one needs to make a host
    of decisions; selecting a population size is one of the most important among
    them. Most algorithms in the literature fix the population size to a certain
    constant value. This reduces the algorithm's quality since the optimal
    population size varies for different instances, local search procedures and
    running times. In this paper we propose an adjustable population size.

  6. Note on Max Lin-2 above Average.

    Tue, 12/01/2009 - 16:02 — SomNambul
    Authors: Gregory Gutin, Robert Crowston, Mark Jones
    Subjects: Data Structures and Algorithms
    Abstract

    In the Max Lin-2 problem we are given a system $S$ of $m$ linear equations in
    $n$ variables over $\mathbb{F}_2$ in which Equation $j$ is assigned a positive
    integral weight $w_j$ for each $j$. We wish to find an assignment of values to
    the variables which maximizes the total weight of satisfied equations. This
    problem generalizes Max Cut. The expected weight of satisfied equations is
    $W/2$, where $W=w_1+... +w_m$; $W/2$ is a tight lower bound on the optimal
    solution of Max Lin-2.

  7. Vertex Cover Problem Parameterized Above and Below Tight Bounds.

    Mon, 08/31/2009 - 17:16 — SomNambul
    Authors: Gregory Gutin, Eun Jung Kim, Michael Lampis, Valia Mitsou
    Subjects: Computational Complexity
    Abstract

    We study the well-known Vertex Cover problem parameterized above and below
    tight bounds. We show that two of the parameterizations (both were suggested by
    Mahajan, Raman and Sikdar, J. Computer and System Sciences, 75(2):137--153,
    2009) are fixed-parameter tractable and two other parameterizations are
    W[1]-hard (one of them is, in fact, W[2]-hard).

Math-arch

Syndicate content