共查询到20条相似文献,搜索用时 46 毫秒
1.
2.
3.
《Journal of Computer and System Sciences》2016,82(6):1044-1063
We study the Weighted t-Uniform Sparsest Cut (Weighted t-USC) and other related problems. In an instance of the Weighted t-USC problem, a parameter t and an undirected graph with edge-weights and vertex-weights are given. The goal is to find a vertex set with while minimizing , where is the total weight of the edges with exactly one endpoint in S and . For this problem, we present a factor bicriteria approximation algorithm. Our algorithm outperforms the current best algorithm when . We also present better approximation algorithms for Weighted ρ-Unbalanced Cut and Min–Max k-Partitioning problems. 相似文献
4.
《Computers & Mathematics with Applications》2005,49(9-10):1387-1395
5.
6.
Raphael Yuster 《Information Processing Letters》2011,111(21-22):1057-1061
We present an algorithm that finds, for each vertex of an undirected graph, a shortest cycle containing it. While for directed graphs this problem reduces to the All-Pairs Shortest Paths problem, this is not known to be the case for undirected graphs.We present a truly sub-cubic randomized algorithm for the undirected case. Given an undirected graph with n vertices and integer weights in , it runs in time where is the exponent of matrix multiplication. As a by-product, our algorithm can be used to determine which vertices lie on cycles of length at most t in time. For the case of bounded real edge weights, a variant of our algorithm solves the problem up to an additive error of ? in time. 相似文献
7.
8.
In multiple-instance learning the learner receives bags, i.e., sets of instances. A bag is labeled positive if it contains a positive example of the target. An lower bound is given for the VC-dimension of bags of size r for d-dimensional halfspaces and it is shown that the same lower bound holds for halfspaces over any large point set in general position. This lower bound improves an lower bound of Sabato and Tishby, and it is sharp in order of magnitude. We also show that the hypothesis finding problem is NP-complete and formulate several open problems. 相似文献
9.
《Journal of Computer and System Sciences》2016,82(5):782-792
This paper presents improved algorithms for the round-trip single-facility location problem on a general graph, in which a set A of collection depots is given and the service distance of a customer is defined to be the distance from the server, to the customer, then to a depot, and back to the server. Each customer i is associated with a subset of depots that i can potentially select from and use. When for each customer i, the problem is unrestricted; otherwise it is restricted. For the restricted round-trip 1-center problem, we give an -time algorithm. For the restricted 1-median problem, we give an -time algorithm. For the unrestricted 1-median problem, we give an -time algorithm. 相似文献
10.
《Journal of Computer and System Sciences》2016,82(5):767-781
Let r≥ 4 be an even integer. Graph G is r-bipancyclic if it contains a cycle of every even length from r to , where is the number of vertices in G. A graph G is r-pancyclic if it contains a cycle of every length from r to , where . A graph is k-edge-fault Hamiltonian if, after deleting arbitrary k edges from the graph, the resulting graph remains Hamiltonian. The terms k-edge-fault r-bipancyclic and k-edge-fault r-pancyclic can be defined similarly. Given two graphs G and H, where , 9, let , be the minimum degrees of G and H, respectively. This study determined the edge-fault r-bipancyclic and edge-fault r-pancyclic of Cartesian product graph with some conditions. These results were then used to evaluate the edge-fault pancyclicity (bipancyclicity) of and . 相似文献
11.
Wenjie Li Zhenkun Zhang Hailing Liu Jinjiang Yuan 《Information Processing Letters》2012,112(12):503-508
This paper studies the online scheduling of equal-length jobs with incompatible families on multiple batch machines which can process the jobs from a common family in batches, where each batch has a capacity b with in the unbounded batching and in the bounded batching. Each job J has an equal-length integral processing time , an integral release time , an integral deadline and a real weight . The goal is to determine a preemptive schedule with restart which maximizes the weighted number of early jobs. When , we show that a simple greedy online algorithm has a competitive ratio 2, and establish the lower bound . This means that the greedy algorithm is of the best possible for . When p is any positive integer, we provide an online algorithm of competitive ratio for both and . This is the first online algorithm for the problem with a constant competitive ratio. 相似文献
12.
13.
Let be a connected graph on n vertices. The proximity of G is the minimum average distance from a vertex of G to all others. The eccentricity of a vertex v in G is the largest distance from v to another vertex, and the average eccentricity of the graph G is . Recently, it was conjectured by Aouchiche and Hansen (2011) [3] that for any connected graph G on vertices, , with equality if and only if . In this paper, we show that this conjecture is true. 相似文献
14.
15.
16.
Jesse Kamp Anup Rao Salil Vadhan David Zuckerman 《Journal of Computer and System Sciences》2011,77(1):191-220
We give polynomial-time, deterministic randomness extractors for sources generated in small space, where we model space s sources on as sources generated by width branching programs. Specifically, there is a constant such that for any , our algorithm extracts bits that are exponentially close to uniform (in variation distance) from space s sources with min-entropy δn, where . Previously, nothing was known for , even for space 0. Our results are obtained by a reduction to the class of total-entropy independent sources. This model generalizes both the well-studied models of independent sources and symbol-fixing sources. These sources consist of a set of r independent smaller sources over , where the total min-entropy over all the smaller sources is k. We give deterministic extractors for such sources when k is as small as , for small enough ?. 相似文献
17.
18.
19.
20.
《Journal of Computer and System Sciences》2016,82(6):1007-1019
Systems of equations of the form and are considered, in which the unknowns are sets of integers, the plus operator denotes element-wise sum of sets, and C is an ultimately periodic constant. For natural numbers, such equations are equivalent to language equations over a one-symbol alphabet using concatenation and regular constants. It is shown that such systems are computationally universal: for every recursive (r.e., co-r.e.) set there exists a system with a unique (least, greatest) solution containing a component T with . Testing solution existence for these equations is -complete, solution uniqueness is -complete, and finiteness of the set of solutions is -complete. A similar construction for integers represents any hyper-arithmetical set by a set satisfying , whereas testing solution existence is -complete. 相似文献