Rounding two and three dimensional solutions of the sdp relaxation of max cut




Скачать 142.7 Kb.
НазваниеRounding two and three dimensional solutions of the sdp relaxation of max cut
страница1/5
Дата14.02.2013
Размер142.7 Kb.
ТипДокументы
  1   2   3   4   5
Kinetic and Dynamic Data Structures for Convex Hulls and Upper

Envelopes


Giora Alexandron

School of Computer Science

Tel Aviv University

gioraa@post.tau.ac.il


Haim Kaplan

School of Computer Science

Tel Aviv University

haimk@post.tau.ac.il


Micha Sharir

School of Computer Science

Tel Aviv University

and

Courant Institute of Mathematical Sciences

New York University

michas@post.tau.ac.il


Let S be a set of n moving points in the plane. We present a kinetic and dynamic (randomized) data structure for maintaining the convex hull of S. The structure uses O(n) space, and processes an expected number of O(n2s+2(n) log n) critical events, each in O(log2n) expected time, including O(n) insertions, deletions, and changes in the flight plans of the points. Here s is the maximum number of times where any specific triple of points can become collinear,

s(q) = s(q)/q, and s(q) is the maximum length of Davenport-Schinzel sequences of order s on n symbols. Compared with the previous solution of Basch et al. [?], our structure uses simpler certificates, uses roughly the same resources, and is also dynamic.

Dotted Interval Graphs


Yonathan Aumann

Bar-Ilan University

aumann@cs.biu.ac.il


We introduce a generalization of interval graphs, which we call dotted interval graphs (DIG). A dotted interval graph is an intersection graph of arithmetic progressions (= dotted intervals). Coloring of dotted intervals graphs naturally arises in the context of high throughput genotyping. We study the properties of dotted interval graphs, with a focus on coloring.

We show that any graph is a DIG, but that DIGd graphs, i.e. DIGs in which the arithmetic progressions have a jump of at most d, form a strict hierarchy. We show that coloring DIGd graphs is NP-complete even for d=2. For any fixed d, we provide a 5/6d approximation for the coloring of digD graphs.

Joint work with: Moshe Lewenstein, Oren Malamud, Ron Pinter, and Zohar Yakhini


Rounding two and three dimensional solutions of the SDP relaxation of
MAX CUT



Adi Avidor

Tel Aviv University

adi@post.tau.ac.il


Uri Zwick


Goemans and Williamson obtained an approximation algorithm for the MAX CUT problem with a performance ratio of GW 0.87856. Their algorithm starts by solving a standard SDP relaxation of MAX CUT and then rounds the optimal solution obtained using a random hyperplane. In some cases, the optimal solution of the SDP relaxation happens to lie in a low dimensional space. Can an improved performance ratio be obtained for such instances? We show that the answer is yes in dimensions two and three and conjecture that this is also the case in any higher fixed dimension. In two dimensions an optimal -approximation algorithm was already obtained by Goemans. (Note that 0.88456.) We obtain an alternative derivation of this result using Gegenbauer polynomials. Our main result is an improved rounding procedure for SDP solutions that lie in R3 with a performance ratio of about 0.8818. The rounding procedure uses an interesting yin-yan coloring of the three dimensional sphere. The improved performance ratio obtained resolves, in the negative, an open problem posed by Feige and Schechtman [STOC’01]. They asked whether there are MAX CUT instances with integrality ratios arbitrarily close to GW that have optimal embeddings, i.e., optimal solutions of their SDP relaxations, that lie in R3.


A Citation Analysis of Michael Rabin’s Work


Judit Bar-Ilan

Department of Information Science

Bar-Ilan University

and

School of Library, Archive and Information Studies

The Hebrew University of Jerusalem

judit@cc.huji.ac.il


Michael Rabin’s first publication is from 1953 in Hebrew in the Riveon LeMatematika. ISI’s Science Citation Index (“Web of Science”) indexes 32 of his publications, starting from 1958; DBLP lists 48 papers and references to 86 publications can be found in Michael Rabin’s CV.

The Science Citation Index listed 2849 citations to Michael Rabin’s work as of November, 2004. Citeseer identified 2169 citations to Michael Rabin’s work in June 2004.

Based on these information sources, we are going to characterize Michael Rabin’s collaborators, citing (i.e., whom he cites) and cited patterns (i.e. who cites him). Limitations of the different information sources will also be discussed.


Adversarial Contention Resolution for Simple Channels


Michael Bender

Department of Computer Science

SUNY Stony Brook

bender@cs.sunysb.edu


We present results analyzing the worst-case performance of randomized backoff.  Specifically, an adversary chooses the packet arrival times.  In contract, most analyses of backoff make statistical assumptions on packet arrivals.  We give a thorough analysis of a range of backoff strategies for the special case in which all the jobs arrive at the same time.  For the case of online arrivals, we assume an adversarial-queuing-theory model and prove upper and lower bounds on the average arrival rates for stability and instability of binary exponential backoff.


Joint work with: Martin Farach-Colton, Simai He, Bradley Kuszmaul, and Charles E.  Leiserson.

Prediction of Small RNA Conformational Switching Using Fine-Grain Graph

Representations and the Wiener Index


Danny Barash

University of Haifa

and

Ben-Gurion University

dbarash@research.haifa.ac.il


Assaf Avihoo


Conformational switching in the secondary structure of RNAs has been observed experimentally, and was recently shown to offer an economical procedure for regulation in bacteria by allosteric means. In order to detect RNA switches that occur in nature and also to devise novel artificial RNA switches, we use graph representations that correspond to the secondary structure of RNAs. Previously, it was shown that predicting selective mutations leading to topological transitions in the RNA secondary structure can be achieved by a coarse-grain Laplacian tree graph representation using its second eigenvalue. However, for small RNAs that are 50 nt long or less, such representations at the level of stems, bulges, and loops become ineffective. It is necessary to use fine-grain graph representation at the level of nucleotides. Each nucleotide becomes a node in the graph and its equivalent Laplacian matrix is of the size NxN for a sequence of N nucleotides. Conformational rearrangements can be studied using measures to assess the differences between Laplacian matrices of fine-grain graph representations. In fine-grain graph representations, the second eigenvalue of the Laplacian matrix does not have a clear intuitive meaning as in coarse-grain tree graphs. However, it is possible to calculate the Wiener index (Merris, Linear & Multilinear Algebra 25 (1989), 291-296) in order to assess the similarities between two RNA secondary structures. We show convincing results using the Wiener index along with some other similarity measures.

On Matroids and Non-ideal Secret Sharing


Amos Beimel

Department of Computer Science

Ben-Gurion University

beimel@cs.bgu.ac.il


Noam Livne


A secret sharing scheme involves a dealer who has a secret, a finite set of participants, and a collection A of subsets of the set of participants called the access structure.

A secret-sharing scheme for A is a method by which the dealer distributes shares to the parties such that any subset in A can reconstruct the secret from its shares, while any subset not in A cannot reveal any partial information about the secret in the information theoretic sense. Certain access structures give rise to very economical secret sharing schemes. A secret sharing scheme is called ideal if the shares are taken from the same domain as the secrets. An access structure is called ideal if there is an ideal secret sharing scheme which realizes the access structure over some finite domain of secrets. Brickell and Davenport (J. of Cryptology, 1991) have shown that ideal access structures are closely related to matroids over a set containing the participants plus the dealer. They give a necessary condition for an access structure to be ideal – the access structure must be induced by a matroid – and a somewhat stronger sufficient condition – the matroid should be representable over some finite field. Seymour (J. of Combinatorial Theory B, 1992) showed that the necessary condition is not sufficient: There exists an access structure induced by a matroid that does not have an ideal scheme.

In this work we continue the research on access structure induced by matroids. Our main result in the work is strengthening the result of Seymour. We show that in any secret sharing scheme realizing the access structure induced by the Vamos matroid with domain of the secret of size k, the size of the domain of the shares is at least

Our second result considers non-ideal secret sharing schemes realizing access structures induced by matroids. We prove that the fact that an access structures is induced by a matroid implies lower and upper bounds on the size of the domain of shares of subsets of participants even in non-ideal schemes (this generalized results of Brickell and Davenport for ideal schemes).

Fast Quantum Byzantine Agreement


Michael Ben-Or

Hebrew University

benor@cs.huji.ac.il


We present a fast quantum Byzantine Agreement protocol that can reach agreement in constant expected communication rounds against a strong full information dynamic adversary, tolerating up to the optimal t faulty players in the synchronous setting, and up to t faulty players for asynchronous systems.

This should be contrasted with the known classical synchronous lower bound of  (\sqrt{n/\log n}) and the classical asynchronous lower bound of (n/log2 n) when t=(n).


Joint work with Avinatan Hassidim.

Autonomous Ontology Extraction using Hierarchical UNSO Hypercube Graph


Yosi Ben-Asher

University of Haifa


Shlomo Berkovsky

University of Haifa

slavax@cs.haifa.ac.il


Yaniv Eytani

University of Haifa


Data Integration is a complex process focusing on matching between similar (or identical) concepts that describe data originated from heterogeneous sources. Importance of Data Integration increases with the amount of available information as different information sources describe similar (or identical) data they provide in various different ways.

In previous works we developed UNSO (UNSpecified Ontology). UNSO allows to integrate heterogeneous semantic descriptions of resources (given in form of attribute:value pairs) to a graph topology called Multi-Layered Hypercube (MLH). MLH topology can be illustrated as a hypercube where each node is recursively comprised of another hypercube. UNSO effectively creates a mapping between semantic concepts and the underlying MLH graph. Similar (or identical) are mapped to vertexes in the graph that are found in close proximity. The hypercube topology inherently facilitates distributed and completely decentralized management of the resources.

In this work we extend the topology developed in UNSO to create an adaptive autonomous hierarchical graph topology. We achieve it by dynamically changing the graph topology using the previously learned properties of the semantic descriptions' attributes. The graph topology evolves automatically by applying a predefined set of operators (such as splitting, shrinkage, and swapping of two adjacent hierarchical levels) on the MLH graph. This effectively creates a hierarchical graph topology where each hierarchical level correlates the relevant attributes with their relative importance in resources' descriptions.

Our structure leverages the process of Data Integration through providing an efficient mean for dynamic ontology extraction basing on statistical properties of the attributes in the semantic descriptions of the resources.

Connectivity and Parity


András Frank

Eötvös University

frank@cs.elte.hu


Parity (matching theory) and connectivity (network flows) are two main branches of combinatorial optimization. In this talk I try to overview the interrelation of these topics. We study problems where both parity and connectivity requirements are imposed. For example, a characterization is given for undirected graphs having a k-edgeconnected orientation for which the in-degree of every node v is congruent to q(v) (mod 2) for every ”compatible” parity prescriptions q : V {0, 1}.


Tighter Approximations on Greedy for Maximum Induced Matchings in Regular Graphs


Tzvi Gotthilf

Bar-Ilan University


and


Moshe Lewenstein

Bar-Ilan University

moshe@macs.biu.ac.il


An induced matching is a matching for which each two edges in the matching are at distance >= 2. Induced matchings are well-studied combinatorial objects and a lot of consideration has been given to finding maximum induced matchings, which is an NP-complete problem. Specifically, finding maximum induced matchings in regular graphs is well-known to be NP-complete. A couple of papers lately showed a couple of simple greedy algorithm that approximate a maximum induced matching with a factor of d-1/2 and d-1 (different papers - different factors), where d is the degree of regularity. We show a simple greedy approach that yields an 0.8d approximation factor.


Some Relationships between Probabilistic Performance Evaluation Models


Sergey Frenkel

The Institute of  Informatics Problems

Russian Academy of Sciences

slf-ipiran@mtu-net.ru


Probabilistic performance evaluation models are used to predict execution time of a program with stochastic behavior. In general, the probabilistic performance modelling of distributed and parallel CS includes both semantic and computational aspects. “Semantic” models are used for formal specification of the target CS. The “computational” ones are some mathematical models of the target system, quantifying the relationships established by the formal specifications. Schematically, all the analytical computational models can be sorted over task graphs and state transition- based ones. In task graphs modeling a program is decomposed into modules called tasks that are executed according to some precedence constraints. State Transition-based models are based formally on well-known conception of “labeled transition system”. The task graph model is very convenient tool of CS description, but, there is a difficult to compute and predict the distribution of the execution time of an application by convolving density functions of individual tasks execution times. Overall computation consumptions depend essentially on the task graph structures. In particular, sometimes we can reduce the consumptions using either way of the task graph levelizing. However, in many cases it is more reasonable (from the point of view of computational consumption) to use some state-based models, like FSM, “Stochastic automation network”(SAN), etc. This talk shows some relationships between different mathematical models of performance evaluation that allows to choose a trade-off between various mathematical design tools. In particular, it will be shown a way to map a task graph performance model to a state-based one, which deals with a semi-Markov process. This semi-Markov process may be built correctly if, besides the traditional precedence constraints, a description of the tasks relationship involves also some probabilistic characteristics of a dynamic of running and waiting of tasks in the task graph nodes.

On the Chromatic Spectrum of Decompositions of Graphs


Robert E. Jamison

Department of Mathematical Sciences

Clemson University

rejam@clemson.edu


Eric Mendelsohn

Department of Mathematics

University of Toronto

mendelso@math.utoronto.ca


The idea of a decomposition of graph occurs both in the study of intersection graphs and in combinatorial design theory. The former deals mostly with sparse graphs, the latter with complete and complete multipartite graphs. Here we will explore a theory for decompositions of general graphs which incorporates both these endeavours.

Let K be a family of graphs. A K -decomposition D of a graph H = (V,E) is a partition of the edge set E of H so that for each part P of the partition, the subgraph of H induced by P is isomorphic to a graph in K. The graph H is called the host graph for the decomposition. The subgraphs of H induced by the parts of the partition are called the blocks of the partition, and the graphs in K are called the block prototypes for the decomposition.

The intersection graph I(D) of the decomposition D has a vertex for each block of the partition and two blocks A and B are adjacent iff they share a common node. The chromatic index of a decomposition D is the chromatic number of I(D). Thus the chromatic index X’(D) of an K -decomposition D of H is the minimum number of colors required to color the subgraphs in the decomposition so that subgraphs which share a node get different colors. The K-chromatic spectrum SpecK (H) is the set of all values of X’(D) over all K decompositions D of H.

We will show that if the host graph is a tree T, then all S-decompositions of T have the same chromatic index and this can be computed in polynomial time. By contrast, for every tree S the problem of determining the chromatic index of an S-decomposition of a bipartite graph is NP-complete as is the problem of deciding if an integer is in the S-spectrum of a bipartite graph.

We will also investigate such questions as 1) Which sets of positivre integers are the spectra of graphs? and 2) How can spectra be constructed with large lacunae?

Braid group cryptanalysis


David Garber

Holon Academic Institute of Technology

garber@hait.ac.il


An important problem in combinatorial group theory is: Given a system of equations in a finitely generated group, find (in an efficient manner) a solution to this system of equations. This problem generalizes many problems of combinatorial group theory (the conjugacy problem, the membership problem, etc.).

In the last few years, several public-key cryptosystems where suggested, who rely on the difficulty of this problem in the braid group. In the talk, we will present an efficient algorithmic way for finding a small ordered list of elements in the subgroup which contains a solution to the equation with a significant probability. In many cases, the solution will be the first in this list. This approach actually shows the vulnerability of all mentioned cryptosystems.

This is a joint work with S. Kaplan, M. Teicher, B. Tsaban and U. Vishne.

  1   2   3   4   5

Похожие:

Rounding two and three dimensional solutions of the sdp relaxation of max cut icon3ds Max 2009 выходит в двух версиях. Версия 3ds Max 2009 ориентирована на разработчиков игр, а версия 3ds Max 2009 Design на тех, кто занимается архитектурной
Зато в 3ds Max 2009 Design есть система для анализа освещения в сценах Lightning Analysis, который отсутствует в 3ds Max 2009. Если...
Rounding two and three dimensional solutions of the sdp relaxation of max cut iconOnno Boxma, Department of Mathematics and Computer Science Eindhoven University of Technology, Two-dimensional workload processes and two-dimensional insurance processes II

Rounding two and three dimensional solutions of the sdp relaxation of max cut iconThe Typology of Rounding Harmony

Rounding two and three dimensional solutions of the sdp relaxation of max cut icon[Volume 99, Issues 2-3] Deformation and relaxation of Newtonian drops in planar extensional flows of a Boger fluid

Rounding two and three dimensional solutions of the sdp relaxation of max cut iconУчебный курс «Технологии программирования. Курс на базе Microsoft Solutions Framework (msf)» для подготовки по направлению «Информационные технологии»
Лекция методология Microsoft Solutions Framework. Разработка. Стабилизация. Внедрение
Rounding two and three dimensional solutions of the sdp relaxation of max cut iconУчебный курс «Технологии программирования. Курс на базе Microsoft Solutions Framework (msf)» для подготовки по направлению «Информационные технологии»
Лекция методология Microsoft Solutions Framework. Выработка концепции. Планирование
Rounding two and three dimensional solutions of the sdp relaxation of max cut iconУчебный курс «Технологии программирования. Курс на базе Microsoft Solutions Framework (msf)» для подготовки по направлению «Информационные технологии»
Лекция методология Microsoft Solutions Framework. Управление рисками. Модель процессов
Rounding two and three dimensional solutions of the sdp relaxation of max cut iconУчебный курс «Технологии программирования. Курс на базе Microsoft Solutions Framework (msf)» для подготовки по направлению «Информационные технологии»
Лекция методология Microsoft Solutions Framework. Введение. Версии. Модель проектной группы
Rounding two and three dimensional solutions of the sdp relaxation of max cut iconDonnie darko: The Director's Cut

Rounding two and three dimensional solutions of the sdp relaxation of max cut iconThree Dimensional Digitisation of Objects

Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница