Journal articles: 'Max-cut problems on graphs'

1

Bibak, Ali, Charles Carlson, and Karthekeyan Chandrasekaran. "Improving the Smoothed Complexity of FLIP for Max Cut Problems." ACM Transactions on Algorithms 17, no. 3 (2021): 1–38. http://dx.doi.org/10.1145/3454125.

Full text

Abstract:

Finding locally optimal solutions for MAX-CUT and MAX- k -CUT are well-known PLS-complete problems. An instinctive approach to finding such a locally optimum solution is the FLIP method. Even though FLIP requires exponential time in worst-case instances, it tends to terminate quickly in practical instances. To explain this discrepancy, the run-time of FLIP has been studied in the smoothed complexity framework. Etscheid and Röglin (ACM Transactions on Algorithms, 2017) showed that the smoothed complexity of FLIP for max-cut in arbitrary graphs is quasi-polynomial. Angel, Bubeck, Peres, and Wei (STOC, 2017) showed that the smoothed complexity of FLIP for max-cut in complete graphs is ( O Φ 5 n 15.1 ), where Φ is an upper bound on the random edge-weight density and Φ is the number of vertices in the input graph. While Angel, Bubeck, Peres, and Wei’s result showed the first polynomial smoothed complexity, they also conjectured that their run-time bound is far from optimal. In this work, we make substantial progress toward improving the run-time bound. We prove that the smoothed complexity of FLIP for max-cut in complete graphs is O (Φ n 7.83 ). Our results are based on a carefully chosen matrix whose rank captures the run-time of the method along with improved rank bounds for this matrix and an improved union bound based on this matrix. In addition, our techniques provide a general framework for analyzing FLIP in the smoothed framework. We illustrate this general framework by showing that the smoothed complexity of FLIP for MAX-3-CUT in complete graphs is polynomial and for MAX - k - CUT in arbitrary graphs is quasi-polynomial. We believe that our techniques should also be of interest toward showing smoothed polynomial complexity of FLIP for MAX - k - CUT in complete graphs for larger constants k .

APA, Harvard, Vancouver, ISO, and other styles

2

Bondarenko, Vladimir, and Andrei Nikolaev. "On Graphs of the Cone Decompositions for the Min-Cut and Max-Cut Problems." International Journal of Mathematics and Mathematical Sciences 2016 (2016): 1–6. http://dx.doi.org/10.1155/2016/7863650.

Full text

Abstract:

We consider maximum and minimum cut problems with nonnegative weights of edges. We define the graphs of the cone decompositions and find a linear clique number for the min-cut problem and a superpolynomial clique number for the max-cut problem. These values characterize the time complexity in a broad class of algorithms based on linear comparisons.

APA, Harvard, Vancouver, ISO, and other styles

3

Rodriguez-Fernandez, Angel E., Bernardo Gonzalez-Torres, Ricardo Menchaca-Mendez, and Peter F. Stadler. "Clustering Improves the Goemans–Williamson Approximation for the Max-Cut Problem." Computation 8, no. 3 (2020): 75. http://dx.doi.org/10.3390/computation8030075.

Full text

Abstract:

MAX-CUT is one of the well-studied NP-hard combinatorial optimization problems. It can be formulated as an Integer Quadratic Programming problem and admits a simple relaxation obtained by replacing the integer “spin” variables xi by unitary vectors v→i. The Goemans–Williamson rounding algorithm assigns the solution vectors of the relaxed quadratic program to a corresponding integer spin depending on the sign of the scalar product v→i·r→ with a random vector r→. Here, we investigate whether better graph cuts can be obtained by instead using a more sophisticated clustering algorithm. We answer this question affirmatively. Different initializations of k-means and k-medoids clustering produce better cuts for the graph instances of the most well known benchmark for MAX-CUT. In particular, we found a strong correlation of cluster quality and cut weights during the evolution of the clustering algorithms. Finally, since in general the maximal cut weight of a graph is not known beforehand, we derived instance-specific lower bounds for the approximation ratio, which give information of how close a solution is to the global optima for a particular instance. For the graphs in our benchmark, the instance specific lower bounds significantly exceed the Goemans–Williamson guarantee.

APA, Harvard, Vancouver, ISO, and other styles

4

Hamerly, Ryan, Takahiro Inagaki, Peter L. McMahon, et al. "Experimental investigation of performance differences between coherent Ising machines and a quantum annealer." Science Advances 5, no. 5 (2019): eaau0823. http://dx.doi.org/10.1126/sciadv.aau0823.

Full text

Abstract:

Physical annealing systems provide heuristic approaches to solving combinatorial optimization problems. Here, we benchmark two types of annealing machines—a quantum annealer built by D-Wave Systems and measurement-feedback coherent Ising machines (CIMs) based on optical parametric oscillators—on two problem classes, the Sherrington-Kirkpatrick (SK) model and MAX-CUT. The D-Wave quantum annealer outperforms the CIMs on MAX-CUT on cubic graphs. On denser problems, however, we observe an exponential penalty for the quantum annealer [exp(–αDWN2)] relative to CIMs [exp(–αCIMN)] for fixed anneal times, both on the SK model and on 50% edge density MAX-CUT. This leads to a several orders of magnitude time-to-solution difference for instances with over 50 vertices. An optimal–annealing time analysis is also consistent with a substantial projected performance difference. The difference in performance between the sparsely connected D-Wave machine and the fully-connected CIMs provides strong experimental support for efforts to increase the connectivity of quantum annealers.

APA, Harvard, Vancouver, ISO, and other styles

5

Zivan, Roie, Omer Lev, and Rotem Galiki. "Beyond Trees: Analysis and Convergence of Belief Propagation in Graphs with Multiple Cycles." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 05 (2020): 7333–40. http://dx.doi.org/10.1609/aaai.v34i05.6227.

Full text

Abstract:

Belief propagation, an algorithm for solving problems represented by graphical models, has long been known to converge to the optimal solution when the graph is a tree. When the graph representing the problem includes a single cycle, the algorithm either converges to the optimal solution or performs periodic oscillations. While the conditions that trigger these two behaviors have been established, the question regarding the convergence and divergence of the algorithm on graphs that include more than one cycle is still open.Focusing on Max-sum, the version of belief propagation for solving distributed constraint optimization problems (DCOPs), we extend the theory on the behavior of belief propagation in general – and Max-sum specifically – when solving problems represented by graphs with multiple cycles. This includes: 1) Generalizing the results obtained for graphs with a single cycle to graphs with multiple cycles, by using backtrack cost trees (BCT). 2) Proving that when the algorithm is applied to adjacent symmetric cycles, the use of a large enough damping factor guarantees convergence to the optimal solution.

APA, Harvard, Vancouver, ISO, and other styles

6

COUDERT, D., P. DATTA, S. PERENNES, H. RIVANO, and M. E. VOGE. "SHARED RISK RESOURCE GROUP COMPLEXITY AND APPROXIMABILITY ISSUES." Parallel Processing Letters 17, no. 02 (2007): 169–84. http://dx.doi.org/10.1142/s0129626407002958.

Full text

Abstract:

This article investigates complexity and approximability properties of combinatorial optimization problems yielded by the notion of Shared Risk Resource Group (SRRG). SRRG has been introduced in order to capture network survivability issues where a failure may break a whole set of resources, and has been formalized as colored graphs, where a set of resources is represented by a set of edges with same color. We consider here the analogous of classical problems such as determining paths or cuts with the minimum numbers of colors or color disjoint paths. These optimization problems are much more difficult than their counterparts in classical graph theory. In particular standard relationship such as the Max Flow - Min Cut equality do not hold any longer. In this article we identify cases where these problems are polynomial, for example when the edges of a given color form a connected subgraph, and otherwise give hardness and non approximability results for these problems.

APA, Harvard, Vancouver, ISO, and other styles

7

Wu, Y., P. Austrin, T. Pitassi, and D. Liu. "Inapproximability of Treewidth and Related Problems." Journal of Artificial Intelligence Research 49 (April 6, 2014): 569–600. http://dx.doi.org/10.1613/jair.4030.

Full text

Abstract:

Graphical models, such as Bayesian Networks and Markov networks play an important role in artificial intelligence and machine learning. Inference is a central problem to be solved on these networks. This, and other problems on these graph models are often known to be hard to solve in general, but tractable on graphs with bounded Treewidth. Therefore, finding or approximating the Treewidth of a graph is a fundamental problem related to inference in graphical models. In this paper, we study the approximability of a number of graph problems: Treewidth and Pathwidth of graphs, Minimum Fill-In, One-Shot Black (and Black-White) pebbling costs of directed acyclic graphs, and a variety of different graph layout problems such as Minimum Cut Linear Arrangement and Interval Graph Completion. We show that, assuming the recently introduced Small Set Expansion Conjecture, all of these problems are NP-hard to approximate to within any constant factor in polynomial time.

APA, Harvard, Vancouver, ISO, and other styles

8

Koam, Ali N. A., Muhammad Akram, and Peide Liu. "Decision-Making Analysis Based on Fuzzy Graph Structures." Mathematical Problems in Engineering 2020 (August 12, 2020): 1–30. http://dx.doi.org/10.1155/2020/6846257.

Full text

Abstract:

A graph structure is a useful framework to solve the combinatorial problems in various fields of computational intelligence systems and computer science. In this research article, the concept of fuzzy sets is applied to the graph structure to define certain notions of fuzzy graph structures. Fuzzy graph structures can be very useful in the study of various structures, including fuzzy graphs, signed graphs, and the graphs having labeled or colored edges. The notions of the fuzzy graph structure, lexicographic-max product, and degree and total degree of a vertex in the lexicographic-max product are introduced. Further, the proposed concepts are explained through several numerical examples. In particular, applications of the fuzzy graph structures in decision-making process, regarding detection of marine crimes and detection of the road crimes, are presented. Finally, the general procedure of these applications is described by an algorithm.

APA, Harvard, Vancouver, ISO, and other styles

9

Drineas, Petros, Ravi Kannan, and Michael W. Mahoney. "Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms." Random Structures & Algorithms 32, no. 3 (2007): 307–33. http://dx.doi.org/10.1002/rsa.20196.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Engelberg, Roee, Jochen Könemann, Stefano Leonardi, and Joseph (Seffi) Naor. "Cut problems in graphs with a budget constraint." Journal of Discrete Algorithms 5, no. 2 (2007): 262–79. http://dx.doi.org/10.1016/j.jda.2006.05.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Khachiyan, Leonid, Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino. "Generating Cut Conjunctions in Graphs and Related Problems." Algorithmica 51, no. 3 (2007): 239–63. http://dx.doi.org/10.1007/s00453-007-9111-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Cohen-Addad, Vincent, Éric Colin De Verdière, Dániel Marx, and Arnaud De Mesmay. "Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs." Journal of the ACM 68, no. 4 (2021): 1–26. http://dx.doi.org/10.1145/3450704.

Full text

Abstract:

We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surface-embedded graphs: the Shortest Cut Graph problem and the Multiway Cut problem. A cut graph of a graph G embedded on a surface S is a subgraph of G whose removal from S leaves a disk. We consider the problem of deciding whether an unweighted graph embedded on a surface of genus G has a cut graph of length at most a given value. We prove a time lower bound for this problem of n Ω( g log g ) conditionally to the ETH. In other words, the first n O(g) -time algorithm by Erickson and Har-Peled [SoCG 2002, Discr. Comput. Geom. 2004] is essentially optimal. We also prove that the problem is W[1]-hard when parameterized by the genus, answering a 17-year-old question of these authors. A multiway cut of an undirected graph G with t distinguished vertices, called terminals , is a set of edges whose removal disconnects all pairs of terminals. We consider the problem of deciding whether an unweighted graph G has a multiway cut of weight at most a given value. We prove a time lower bound for this problem of n Ω( gt + g 2 + t log ( g + t )) , conditionally to the ETH, for any choice of the genus g ≥ 0 of the graph and the number of terminals t ≥ 4. In other words, the algorithm by the second author [Algorithmica 2017] (for the more general multicut problem) is essentially optimal; this extends the lower bound by the third author [ICALP 2012] (for the planar case). Reductions to planar problems usually involve a gridlike structure. The main novel idea for our results is to understand what structures instead of grids are needed if we want to exploit optimally a certain value G of the genus.

APA, Harvard, Vancouver, ISO, and other styles

13

Gao, Zhen-Bin, Gee-Choon Lau, and Wai-Chee Shiu. "Graphs with Minimal Strength." Symmetry 13, no. 3 (2021): 513. http://dx.doi.org/10.3390/sym13030513.

Full text

Abstract:

For any graph G of order p, a bijection f:V(G)→{1,2,…,p} is called a numbering of G. The strength strf(G) of a numbering f of G is defined by strf(G)=max{f(u)+f(v)|uv∈E(G)}, and the strength str(G) of a graph G is str(G)=min{strf(G)|f is a numbering of G}. In this paper, many open problems are solved, and the strengths of new families of graphs are determined.

APA, Harvard, Vancouver, ISO, and other styles

14

Bruglieri, Maurizio, Francesco Maffioli, and Marco Trubian. "Solving minimum K-cardinality cut problems in planar graphs." Networks 48, no. 4 (2006): 195–208. http://dx.doi.org/10.1002/net.20129.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Asahiro, Yuichi, Jesper Jansson, Eiji Miyano, Hirotaka Ono, and T. P. Sandhya. "Graph Orientation with Edge Modifications." International Journal of Foundations of Computer Science 32, no. 02 (2021): 209–33. http://dx.doi.org/10.1142/s012905412150012x.

Full text

Abstract:

The goal of an outdegree-constrained edge-modification problem is to find a spanning subgraph or supergraph [Formula: see text] of an input undirected graph [Formula: see text] such that either: (Type I) the number of edges in [Formula: see text] is minimized or maximized and [Formula: see text] can be oriented to satisfy some specified constraints on the vertices’ resulting outdegrees; or: (Type II) among all subgraphs or supergraphs of [Formula: see text] that can be constructed by deleting or inserting a fixed number of edges, [Formula: see text] admits an orientation optimizing some objective involving the vertices’ outdegrees. This paper introduces eight new outdegree-constrained edge-modification problems related to load balancing called (Type I) MIN-DEL-MAX, MIN-INS-MIN, MAX-INS-MAX, and MAX-DEL-MIN and (Type II) [Formula: see text]-DEL-MAX, [Formula: see text]-INS-MIN, [Formula: see text]-INS-MAX, and [Formula: see text]-DEL-MIN. In each of the eight problems, the input is a graph and the goal is to delete or insert edges so that the resulting graph has an orientation in which the maximum outdegree (taken over all vertices) is small or the minimum outdegree is large. We first present a framework that provides algorithms for solving all eight problems in polynomial time on unweighted graphs. Next we investigate the inapproximability of the edge-weighted versions of the problems, and design polynomial-time algorithms for six of the problems on edge-weighted trees.

APA, Harvard, Vancouver, ISO, and other styles

16

GANDHI, RAJIV, BRADFORD GREENING, SRIRAM PEMMARAJU, and RAJIV RAMAN. "SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS." Discrete Mathematics, Algorithms and Applications 02, no. 03 (2010): 331–45. http://dx.doi.org/10.1142/s1793830910000693.

Full text

Abstract:

In this paper, we study the sub-coloring and hypo-coloring problems on interval graphs. These problems have applications in job scheduling and distributed computing and can be used as "subroutines" for other combinatorial optimization problems. In the sub-coloring problem, given a graph G, we want to partition the vertices of G into minimum number of sub-color classes, where each sub-color class induces a union of disjoint cliques in G. In the hypo-coloring problem, given a graph G, and integral weights on vertices, we want to find a partition of the vertices of G into sub-color classes such that the sum of the weights of the heaviest cliques in each sub-color class is minimized. We present a "forbidden subgraph" characterization of graphs with sub-chromatic number k and use this to derive a 3-approximation algorithm for sub-coloring interval graphs. For the hypo-coloring problem on interval graphs, we first show that it is NP-complete, and then via reduction to the max-coloring problem, show how to obtain an O( log n)-approximation algorithm for it.

APA, Harvard, Vancouver, ISO, and other styles

17

Borba, Elizandro, Eliseu Fritscher, Carlos Hoppen, and Sebastian Richter. "The p-spectral radius of the Laplacian matrix." Applicable Analysis and Discrete Mathematics 12, no. 2 (2018): 455–66. http://dx.doi.org/10.2298/aadm170206012b.

Full text

Abstract:

The p-spectral radius of a graph G=(V,E) with adjacency matrix A is defined as ?(p)(G) = max||x||p=1 xT Ax. This parameter shows connections with graph invariants, and has been used to generalize some extremal problems. In this work, we define the p-spectral radius of the Laplacian matrix L as ?(p)(G) = max||x||p=1 xT Lx. We show that ?(p)(G) relates to invariants such as maximum degree and size of a maximum cut. We also show properties of ?(p)(G) as a function of p, and a upper bound on maxG: |V(G)|=n ?(p)(G) in terms of n = |V| for p > 2, which is attained if n is even.

APA, Harvard, Vancouver, ISO, and other styles

18

Manjula, V. "Graphs in Network Flows." Mapana - Journal of Sciences 11, no. 4 (2012): 99–108. http://dx.doi.org/10.12723/mjs.23.8.

Full text

Abstract:

This paper presents a collection of basics and application of Network flows in Graph theory which is an out- growth of set of lecture notes on Graph applications. It is not only a record of material from text books but also a reflection of precise graphical concept which will be useful for students where such facts are needed. There are many real life problems dealing with discrete objects and binary relations and graph is very convenient form of its representation. A network flow graph G=(V,E) is a directed graph with two special vertices: the source vertex s, and the sink vertex t. Many problems in the real world are to be solved using maximum flow. "Real" networks, like the Internet or electronic circuit boards, are good examples of flow networks. Generally graphs can be used in two situations. Firstly since graph is a very simple, convenient and natural way of representing the relationship between objects. Secondly we have graph as model solve the appropriate graph theoretic problem then interpret the solution in terms of original problem In the modern world, planning efficient routes is essential for business and industry, The flow of information or water or gas etc in a network are useful to find the max rate of flow that is possible from one station to another A Transport network represents a general model for transportation of material from origin of supply to destination through shipping routes. The objective of this paper is to discuss the concepts and terminology of Network flows with Graphical representations.

APA, Harvard, Vancouver, ISO, and other styles

19

Suhl, Uwe H., and Heinrich Hilbert. "A branch-and-cut algorithm for solving generalized multiperiod Steiner problems in graphs." Networks 31, no. 4 (1998): 273–82. http://dx.doi.org/10.1002/(sici)1097-0037(199807)31:4<273::aid-net7>3.0.co;2-a.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Fernandes, Cristina G., Tina Janne Schmidt, and Anusch Taraz. "On minimum bisection and related cut problems in trees and tree-like graphs." Journal of Graph Theory 89, no. 2 (2018): 214–45. http://dx.doi.org/10.1002/jgt.22248.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Narayanaswamy, N. S., and R. Vijayaragunathan. "Parameterized Optimization in Uncertain Graphs—A Survey and Some Results." Algorithms 13, no. 1 (2019): 3. http://dx.doi.org/10.3390/a13010003.

Full text

Abstract:

We present a detailed survey of results and two new results on graphical models of uncertainty and associated optimization problems. We focus on two well-studied models, namely, the Random Failure (RF) model and the Linear Reliability Ordering (LRO) model. We present an FPT algorithm parameterized by the product of treewidth and max-degree for maximizing expected coverage in an uncertain graph under the RF model. We then consider the problem of finding the maximal core in a graph, which is known to be polynomial time solvable. We show that the Probabilistic-Core problem is polynomial time solvable in uncertain graphs under the LRO model. On the other hand, under the RF model, we show that the Probabilistic-Core problem is W[1]-hard for the parameter d, where d is the minimum degree of the core. We then design an FPT algorithm for the parameter treewidth.

APA, Harvard, Vancouver, ISO, and other styles

22

Taşkin, Z. Caner, and J. Cole Smith. "Branch-cut-price algorithms for solving a class of search problems on general graphs." Networks 70, no. 1 (2017): 4–18. http://dx.doi.org/10.1002/net.21740.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Chekuri, Chandra, Alina Ene, and Ali Vakilian. "Node-weighted Network Design in Planar and Minor-closed Families of Graphs." ACM Transactions on Algorithms 17, no. 2 (2021): 1–25. http://dx.doi.org/10.1145/3447959.

Full text

Abstract:

We consider node-weighted survivable network design (SNDP) in planar graphs and minor-closed families of graphs. The input consists of a node-weighted undirected graph G = ( V , E ) and integer connectivity requirements r ( uv ) for each unordered pair of nodes uv . The goal is to find a minimum weighted subgraph H of G such that H contains r ( uv ) disjoint paths between u and v for each node pair uv . Three versions of the problem are edge-connectivity SNDP (EC-SNDP), element-connectivity SNDP (Elem-SNDP), and vertex-connectivity SNDP (VC-SNDP), depending on whether the paths are required to be edge, element, or vertex disjoint, respectively. Our main result is an O ( k )-approximation algorithm for EC-SNDP and Elem-SNDP when the input graph is planar or more generally if it belongs to a proper minor-closed family of graphs; here, k = max uv r ( uv ) is the maximum connectivity requirement. This improves upon the O ( k log n )-approximation known for node-weighted EC-SNDP and Elem-SNDP in general graphs [31]. We also obtain an O (1) approximation for node-weighted VC-SNDP when the connectivity requirements are in {0, 1, 2}; for higher connectivity our result for Elem-SNDP can be used in a black-box fashion to obtain a logarithmic factor improvement over currently known general graph results. Our results are inspired by, and generalize, the work of Demaine, Hajiaghayi, and Klein [13], who obtained constant factor approximations for node-weighted Steiner tree and Steiner forest problems in planar graphs and proper minor-closed families of graphs via a primal-dual algorithm.

APA, Harvard, Vancouver, ISO, and other styles

24

Jünger, Michael, Elisabeth Lobe, Petra Mutzel, et al. "Quantum Annealing versus Digital Computing." ACM Journal of Experimental Algorithmics 26 (July 8, 2021): 1–30. http://dx.doi.org/10.1145/3459606.

Full text

Abstract:

Quantum annealing is getting increasing attention in combinatorial optimization. The quantum processing unit by D-Wave is constructed to approximately solve Ising models on so-called Chimera graphs. Ising models are equivalent to quadratic unconstrained binary optimization (QUBO) problems and maximum cut problems on the associated graphs. We have tailored branch-and-cut as well as semidefinite programming algorithms for solving Ising models for Chimera graphs to provable optimality and use the strength of these approaches for comparing our solution values to those obtained on the current quantum annealing machine, D-Wave 2000Q. This allows for the assessment of the quality of solutions produced by the D-Wave hardware. In addition, we also evaluate the performance of a heuristic by Selby. It has been a matter of discussion in the literature how well the D-Wave hardware performs at its native task, and our experiments shed some more light on this issue. In particular, we examine how reliably the D-Wave computer can deliver true optimum solutions and present some surprising results.

APA, Harvard, Vancouver, ISO, and other styles

25

DÍAZ, JOSEP, MATHEW D. PENROSE, JORDI PETIT, and MARÍA SERNA. "Convergence Theorems for Some Layout Measures on Random Lattice and Random Geometric Graphs." Combinatorics, Probability and Computing 9, no. 6 (2000): 489–511. http://dx.doi.org/10.1017/s0963548300004454.

Full text

Abstract:

This work deals with convergence theorems and bounds on the cost of several layout measures for lattice graphs, random lattice graphs and sparse random geometric graphs. Specifically, we consider the following problems: Minimum Linear Arrangement, Cutwidth, Sum Cut, Vertex Separation, Edge Bisection and Vertex Bisection. For full square lattices, we give optimal layouts for the problems still open. For arbitrary lattice graphs, we present best possible bounds disregarding a constant factor. We apply percolation theory to the study of lattice graphs in a probabilistic setting. In particular, we deal with the subcritical regime that this class of graphs exhibits and characterize the behaviour of several layout measures in this space of probability. We extend the results on random lattice graphs to random geometric graphs, which are graphs whose nodes are spread at random in the unit square and whose edges connect pairs of points which are within a given distance. We also characterize the behaviour of several layout measures on random geometric graphs in their subcritical regime. Our main results are convergence theorems that can be viewed as an analogue of the Beardwood, Halton and Hammersley theorem for the Euclidean TSP on random points in the unit square.

APA, Harvard, Vancouver, ISO, and other styles

26

uit het Broek, Michiel A. J., Albert H. Schrotenboer, Bolor Jargalsaikhan, Kees Jan Roodbergen, and Leandro C. Coelho. "Asymmetric Multidepot Vehicle Routing Problems: Valid Inequalities and a Branch-and-Cut Algorithm." Operations Research 69, no. 2 (2021): 380–409. http://dx.doi.org/10.1287/opre.2020.2033.

Full text

Abstract:

In “Asymmetric Multidepot Vehicle Routing Problems: Valid Inequalities and a Branch-and-Cut Algorithm,” Uit het Broek, Schrotenboer, Jargalsaikhan, Roodbergen, and Coelho present a generic branch-and-cut framework to solve routing problems with multiple depots on directed graphs. They present new valid inequalities that eliminate subtours, enforce tours to be linked to the same depot, and enforce bounds on the number of customers in a vehicle tour. This is embedded in a branch-and-cut scheme that also contains generalized and adapted versions of valid inequalities that are well known for related routing problems. The authors show that the new inequalities tighten root node relaxations considerably. In combination with a simple but effective upper-bound procedure, only requiring a MIP solver and a smart reduction of the problem size, the authors show that the overall framework solves instances of considerably larger size to optimality than have been reported in the literature.

APA, Harvard, Vancouver, ISO, and other styles

27

Elbassioni, Khaled. "A QPTAS for ɛ-Envy-Free Profit-Maximizing Pricing on Line Graphs". ACM Transactions on Economics and Computation 9, № 3 (2021): 1–31. http://dx.doi.org/10.1145/3456762.

Full text

Abstract:

We consider the problem of pricing edges of a line graph so as to maximize the profit made from selling intervals to single-minded customers. An instance is given by a set E of n edges with a limited supply for each edge, and a set of m clients, where each client specifies one interval of E she is interested in and a budget B j which is the maximum price she is willing to pay for that interval. An envy-free pricing is one in which every customer is allocated an (possibly empty) interval maximizing her utility. Grandoni and Rothvoss (SIAM J. Comput. 2016) proposed a polynomial-time approximation scheme ( PTAS ) for the unlimited supply case with running time ( nm ) O ((1/ɛ) 1/ɛ ) , which was extended to the limited supply case by Grandoni and Wiese (ESA 2019). By utilizing the known hierarchical decomposition of doubling metrics , we give a PTAS with running time ( nm ) O (1/ ɛ 2 ) for the unlimited supply case. We then consider the limited supply case, and the notion of ɛ-envy-free pricing in which a customer gets an allocation maximizing her utility within an additive error of ɛ. For this case, we develop an approximation scheme with running time ( nm ) O (log 5/2 max e H e /ɛ 3 ) , where H e = B max ( e )/ B min ( e ) is the maximum ratio of the budgets of any two customers demanding edge e . This yields a PTAS in the uniform budget case, and a quasi-PTAS for the general case. The best approximation known, in both cases, for the exact envy-free pricing version is O (log c max ), where c max is the maximum item supply. Our method is based on the known hierarchical decomposition of doubling metrics, and can be applied to other problems, such as the maximum feasible subsystem problem with interval matrices.

APA, Harvard, Vancouver, ISO, and other styles

28

Zirakashvili, Natela. "Analytical solutions of some internal boundary value problems of elasticity for domains with hyperbolic boundaries." Mathematics and Mechanics of Solids 24, no. 6 (2018): 1726–48. http://dx.doi.org/10.1177/1081286518805269.

Full text

Abstract:

An analytical solution of two-dimensional problems of elasticity in the region bounded by a hyperbola in elliptic coordinates is constructed using the method of separation of variables. The stress–strain state of a homogenous isotropic hyperbolic body and that with a hyperbolic cut is studied when there are non-homogenous (non-zero) boundary conditions given on the hyperbolic boundary. The graphs for the numerical results of some test problems are presented.

APA, Harvard, Vancouver, ISO, and other styles

29

Khan, Najeeb Alam, Oyoon Abdul Razzaq, and Fatima Riaz. "Numerical Simulations for Solving Fuzzy Fractional Differential Equations by Max-Min Improved Euler Methods." Journal of Applied Computer Science Methods 7, no. 1 (2015): 53–83. http://dx.doi.org/10.1515/jacsm-2015-0010.

Full text

Abstract:

Abstract In this paper, an extension is introduced into Max-Min Improved Euler methods for solving initial value problems of fuzzy fractional differential equations (FFDEs). Two modified fractional Euler type methods have been proposed and investigated to obtain numerical solutions of linear and nonlinear FFDEs. The proposed algorithms are tested on various illustrative examples. Exact values are also simulated to compare and discuss the closeness and accuracy of approximations so obtained. Comparatively, tables and graphs results reveal the complete reliability, efficiency and accuracy of the proposed methods.

APA, Harvard, Vancouver, ISO, and other styles

30

Chaibou, Amadou, Ousmane Moussa Tessa, and Oumarou Sié. "Modeling the Parallelization of the Edmonds-Karp Algorithm and Application." Computer and Information Science 12, no. 3 (2019): 81. http://dx.doi.org/10.5539/cis.v12n3p81.

Full text

Abstract:

Many optimization problems can be reduced to the maximum flow problem in a network. However, the maximum flow problem is equivalent to the problem of the minimum cut, as shown by Fulkerson and Ford (Fulkerson &amp; Ford, 1956). There are several algorithms of the graph&rsquo;s cut, such as the Ford-Fulkerson algorithm (Ford &amp; Fulkerson, 1962), the Edmonds-Karp algorithm (Edmonds &amp; Karp, 1972) or the Goldberg-Tarjan algorithm (Goldberg &amp; Tarjan, 1988). In this paper, we study the parallel computation of the Edmonds-Karp algorithm which is an optimized version of the Ford-Fulkerson algorithm. Indeed, this algorithm, when executed on large graphs, can be extremely slow, with a complexity of the order of O|V|.|E|2 (where |V| designates the number of vertices and |E| designates the number of the edges of the graph). So why we are studying its implementation on inexpensive parallel platforms such as OpenMp and GP-GPU. Our work also highlights the limits for parallel computing on this algorithm.

APA, Harvard, Vancouver, ISO, and other styles

31

Hochbaum, Dorit S. "An Exact Sublinear Algorithm for the Max-Flow, Vertex Disjoint Paths and Communication Problems on Random Graphs." Operations Research 40, no. 5 (1992): 923–35. http://dx.doi.org/10.1287/opre.40.5.923.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

CORDONE, ROBERTO, and MARCO TRUBIAN. "A RELAX-AND-CUT ALGORITHM FOR THE KNAPSACK NODE WEIGHTED STEINER TREE PROBLEM." Asia-Pacific Journal of Operational Research 25, no. 03 (2008): 373–91. http://dx.doi.org/10.1142/s0217595908001791.

Full text

Abstract:

The Knapsack Node Weighted Steiner Tree Problem (KNWSTP) is a generalization of the Steiner Tree Problem on graphs, which takes into account the classical cost function defined on the edges, as well as a prize function defined on the vertices and a limit on the size of the solution. It has several applications to network design. We propose an exact branch-and-bound algorithm for this problem, based on a relax-and-cut approach: the algorithm relaxes an exponential family of generalized subtour elimination constraints and takes into account only the violated ones as the computation proceeds. The performance of the algorithm has been tested on a wide set of benchmark problems, up to three hundred vertices, whose structure reflects the features of the most likely applications (sparse graphs with Euclidean costs) and covers different cases with respect to the prize function (only positive, or both positive and negative prizes) and the weight threshold.

APA, Harvard, Vancouver, ISO, and other styles

33

Akram, Muhammad, and N. O. Alshehri. "Intuitionistic Fuzzy Cycles and Intuitionistic Fuzzy Trees." Scientific World Journal 2014 (2014): 1–11. http://dx.doi.org/10.1155/2014/305836.

Full text

Abstract:

Connectivity has an important role in neural networks, computer network, and clustering. In the design of a network, it is important to analyze connections by the levels. The structural properties of intuitionistic fuzzy graphs provide a tool that allows for the solution of operations research problems. In this paper, we introduce various types of intuitionistic fuzzy bridges, intuitionistic fuzzy cut vertices, intuitionistic fuzzy cycles, and intuitionistic fuzzy trees in intuitionistic fuzzy graphs and investigate some of their interesting properties. Most of these various types are defined in terms of levels. We also describe comparison of these types.

APA, Harvard, Vancouver, ISO, and other styles

34

Rosyida, Isnaini, and Suryono Suryono. "Coloring picture fuzzy graphs through their cuts and its computation." International Journal of Advances in Intelligent Informatics 7, no. 1 (2021): 63. http://dx.doi.org/10.26555/ijain.v7i1.612.

Full text

Abstract:

In a fuzzy set (FS), there is a concept of alpha-cuts of the FS for alpha in [0,1]. Further, this concept was extended into (alpha,delta)-cuts in an intuitionistic fuzzy set (IFS) for delta in [0,1]. One of the expansions of FS and IFS is the picture fuzzy set (PFS). Hence, the concept of (alpha,delta)-cuts was developed into (alpha,delta,beta)-cuts in a PFS where beta is an element of [0,1]. Since a picture fuzzy graph (PFG) consists of picture fuzzy vertex or edge sets or both of them, we have an idea to construct the notion of the (alpha,delta,beta)-cuts in a PFG. The steps used in this paper are developing theories and algorithms. The objectives in this research are to construct the concept of (alpha,delta,beta)-cuts in picture fuzzy graphs (PFGs), to construct the (alpha,delta,beta)-cuts coloring of PFGs, and to design an algorithm for finding the cut chromatic numbers of PFGs. The first result is a definition of the (alpha,delta,beta)-cut in picture fuzzy graphs (PFGs) where (alpha,delta,beta) are elements of a level set of the PFGs. Further, some properties of the cuts are proved. The second result is a concept of PFG coloring and the chromatic number of PFG based on the cuts. The third result is an algorithm to find the cuts and the chromatic numbers of PFGs. Finally, an evaluation of the algorithm is done through Matlab programming. This research could be used to solve some problems related to theories and applications of PFGs.

APA, Harvard, Vancouver, ISO, and other styles

35

Honari-Latifpour, Mostafa, and Mohammad-Ali Miri. "Optical Potts machine through networks of three-photon down-conversion oscillators." Nanophotonics 9, no. 13 (2020): 4199–205. http://dx.doi.org/10.1515/nanoph-2020-0256.

Full text

Abstract:

AbstractIn recent years, there has been a growing interest in optical simulation of lattice spin models for applications in unconventional computing. Here, we propose optical implementation of a three-state Potts spin model by using networks of coupled parametric oscillators with phase tristability. We first show that the cubic nonlinear process of spontaneous three-photon down-conversion is accompanied by a tristability in the phase of the subharmonic signal between three states with 2π/3 phase contrast. The phase of such a parametric oscillator behaves like a three-state spin system. Next, we show that a network of dissipatively coupled three-photon down-conversion oscillators emulates the three-state planar Potts model. We discuss potential applications of the proposed system for all-optical optimization of combinatorial problems such as graph 3-COL and MAX 3-CUT.

APA, Harvard, Vancouver, ISO, and other styles

36

Dewar, Megan, David Pike, and John Proos. "Connectivity in Hypergraphs." Canadian Mathematical Bulletin 61, no. 2 (2018): 252–71. http://dx.doi.org/10.4153/cmb-2018-005-9.

Full text

Abstract:

AbstractIn this paper we consider two natural notions of connectivity for hypergraphs: weak and strong. We prove that the strong vertex connectivity of a connected hypergraph is bounded by its weak edge connectivity, thereby extending a theorem of Whitney from graphs to hypergraphs. We find that, while determining a minimum weak vertex cut can be done in polynomial time and is equivalent to finding a minimum vertex cut in the 2-section of the hypergraph in question, determining a minimum strong vertex cut is NP-hard for general hypergraphs. Moreover, the problem of finding minimum strong vertex cuts remains NP-hard when restricted to hypergraphs with maximum edge size at most 3. We also discuss the relationship between strong vertex connectivity and the minimum transversal problem for hypergraphs, showing that there are classes of hypergraphs for which one of the problems is NP-hard, while the other can be solved in polynomial time.

APA, Harvard, Vancouver, ISO, and other styles

37

Friedrich, Tobias, Andreas Göbel, Frank Neumann, Francesco Quinzan, and Ralf Rothenberger. "Greedy Maximization of Functions with Bounded Curvature under Partition Matroid Constraints." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 2272–79. http://dx.doi.org/10.1609/aaai.v33i01.33012272.

Full text

Abstract:

We investigate the performance of a deterministic GREEDY algorithm for the problem of maximizing functions under a partition matroid constraint. We consider non-monotone submodular functions and monotone subadditive functions. Even though constrained maximization problems of monotone submodular functions have been extensively studied, little is known about greedy maximization of non-monotone submodular functions or monotone subadditive functions. We give approximation guarantees for GREEDY on these problems, in terms of the curvature. We find that this simple heuristic yields a strong approximation guarantee on a broad class of functions. We discuss the applicability of our results to three real-world problems: Maximizing the determinant function of a positive semidefinite matrix, and related problems such as the maximum entropy sampling problem, the constrained maximum cut problem on directed graphs, and combinatorial auction games. We conclude that GREEDY is well-suited to approach these problems. Overall, we present evidence to support the idea that, when dealing with constrained maximization problems with bounded curvature, one needs not search for (approximate) monotonicity to get good approximate solutions.

APA, Harvard, Vancouver, ISO, and other styles

38

Hope, Wayne. "REVIEW: Inequality should be worrying Key." Pacific Journalism Review 20, no. 1 (2014): 256. http://dx.doi.org/10.24135/pjr.v20i1.202.

Full text

Abstract:

Book review of: Inequality: A New Zealand Crisis, by Max Rushbrooke (ed), Wellington: Bridget Williams, 2013, 279pp. ISBN 9781927131510.This book follows international publications, such as Richard Wilkinson and Kate Pickets’ Spirit Level (2009) and Joseph Stiglitz’s The Price of Inequality (2012). After 30 plus years of neo-liberal ideology mainstream social scientists and non-doctrinaire economists had reached a consensus; increasing inequality had worsened social problems without improving economic growth or development. Some well-off people were even prepared to support progressive taxes and increased social provision for the purposes of social cohesion. It was thus hard to sustain an ethical defence of neo-liberal policy programmes. Max Rashbrooke’s introduction to this edited collection notes that New Zealand is a special case. From the mid-1980s to the mid-2000s the rich-poor gap widened faster than in any other developed country (p. 1). Various authors consider the nature, causes and consequences of this development over 15 chapters. Interspersed between them are 14 unique viewpoints on wealth and poverty in New Zealand. A range of graphs, figures and tables give empirical weight to the view that inequality is structurally entrenched and socially damaging

APA, Harvard, Vancouver, ISO, and other styles

39

Egger, Daniel J., Jakub Mareček, and Stefan Woerner. "Warm-starting quantum optimization." Quantum 5 (June 17, 2021): 479. http://dx.doi.org/10.22331/q-2021-06-17-479.

Full text

Abstract:

There is an increasing interest in quantum algorithms for problems of integer programming and combinatorial optimization. Classical solvers for such problems employ relaxations, which replace binary variables with continuous ones, for instance in the form of higher-dimensional matrix-valued problems (semidefinite programming). Under the Unique Games Conjecture, these relaxations often provide the best performance ratios available classically in polynomial time. Here, we discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of a combinatorial optimization problem and how to analyze properties of the associated quantum algorithms. In particular, this allows the quantum algorithm to inherit the performance guarantees of the classical algorithm. We illustrate this in the context of portfolio optimization, where our results indicate that warm-starting the Quantum Approximate Optimization Algorithm (QAOA) is particularly beneficial at low depth. Likewise, Recursive QAOA for MAXCUT problems shows a systematic increase in the size of the obtained cut for fully connected graphs with random weights, when Goemans-Williamson randomized rounding is utilized in a warm start. It is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.

APA, Harvard, Vancouver, ISO, and other styles

40

Poljak, Svatopluk, and Daniel Turzík. "Max-cut in circulant graphs." Discrete Mathematics 108, no. 1-3 (1992): 379–92. http://dx.doi.org/10.1016/0012-365x(92)90690-h.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Halperin, Eran, Dror Livnat, and Uri Zwick. "MAX CUT in cubic graphs." Journal of Algorithms 53, no. 2 (2004): 169–85. http://dx.doi.org/10.1016/j.jalgor.2004.06.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

LUAT, SELINA, and EMMY HOSSAIN. "Complaint Management System for Sarawak Rural Area Water Supply Department." Trends in Undergraduate Research 4, no. 1 (2021): c35–40. http://dx.doi.org/10.33736/tur.2852.2021.

Full text

Abstract:

This Complaint Management System is developed to manage the complaints received by the Corporate Communication Unit of the Sarawak Rural Area Water Supply Department. This system was developed to solve the current problems faced in managing, retrieving and updating data using the manual method by the Department. Users of the system are the administrative staff and division water engineers. Users are able to add, update and delete complaint records, as well as view information in graphical format such as pie charts and graphs. Rapid Application Development (RAD) was used to develop this system, consisting of four phases: analysing user requirement, develop a prototype, construction and cut over. The feedback received from the Department’s staff is positive and showed that the users are satisfied with the system developed.

APA, Harvard, Vancouver, ISO, and other styles

43

Damaschke, Peter. "Dividing Splittable Goods Evenly and With Limited Fragmentation." Algorithmica 82, no. 5 (2019): 1298–328. http://dx.doi.org/10.1007/s00453-019-00643-z.

Full text

Abstract:

Abstract A splittable good provided in n pieces shall be divided as evenly as possible among m agents, where every agent can take shares from at most F pieces. We call F the fragmentation and mainly restrict attention to the cases $$F=1$$F=1 and $$F=2$$F=2. For $$F=1$$F=1, the max–min and min–max problems are solvable in linear time. The case $$F=2$$F=2 has neat formulations and structural characterizations in terms of weighted graphs. First we focus on perfectly balanced solutions. While the problem is strongly NP-hard in general, it can be solved in linear time if $$m\ge n-1$$m≥n-1, and a solution always exists in this case, in contrast to $$F=1$$F=1. Moreover, the problem is fixed-parameter tractable in the parameter $$2m-n$$2m-n. (Note that this parameter measures the number of agents above the trivial threshold $$m=n/2$$m=n/2.) The structural results suggest another related problem where unsplittable items shall be assigned to subsets so as to balance the average sizes (rather than the total sizes) in these subsets. We give an approximation-preserving reduction from our original splitting problem with fragmentation $$F=2$$F=2 to this averaging problem, and some approximation results in cases when m is close to either n or n / 2.

APA, Harvard, Vancouver, ISO, and other styles

44

CALAMONERI, TIZIANA, IRENE FINOCCHI, YANNIS MANOUSSAKIS, and ROSSELLA PETRESCHl. "ON MAX CUT IN CUBIC GRAPHS." Parallel Algorithms and Applications 17, no. 3 (2002): 165–83. http://dx.doi.org/10.1080/01495730108941439.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Kamiński, Marcin. "max-cut and containment relations in graphs." Theoretical Computer Science 438 (June 2012): 89–95. http://dx.doi.org/10.1016/j.tcs.2012.02.036.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

BECKWITH, A. W. "A NEW S-S′ PAIR CREATION RATE EXPRESSION IMPROVING UPON ZENER CURVES FOR I-E PLOTS." Modern Physics Letters B 20, no. 14 (2006): 849–61. http://dx.doi.org/10.1142/s0217984906011219.

Full text

Abstract:

To simplify phenomenology modeling used for charge density wave (CDW) transport, we apply a wavefunctional formulation of tunneling Hamiltonians to a physical transport problem characterized by a perturbed washboard potential. To do so, we consider tunneling between states that are wavefunctionals of a scalar quantum field ϕ. I-E curves that match Zener curves — used to fit data experimentally with wavefunctionals congruent with the false vacuum hypothesis. This has a very strong convergence with the slope of graphs of electron-positron pair production representations. The newly derived results include a threshold electric field explicitly as a starting point without an arbitrary cut off value for the start of the graphed results, thereby improving on both the Zener plots and Lin's generalization of Schwingers 1950 electron-positron nucleation values results for low dimensional systems. The similarities in plot behavior of the current values after the threshold electric field values argue in favor of the Bardeen pinning gap paradigm proposed for quasi-one-dimensional metallic transport problems.

APA, Harvard, Vancouver, ISO, and other styles

47

Shioura, Akiyoshi, and Shunya Suzuki. "OPTIMAL ALLOCATION PROBLEM WITH QUADRATIC UTILITY FUNCTIONS AND ITS RELATIONSHIP WITH GRAPH CUT PROBLEM." Journal of the Operations Research Society of Japan 55, no. 1 (2012): 92–105. http://dx.doi.org/10.15807/jorsj.55.92.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Grove, William M., and Paul E. Meehl. "Simple Regression-Based Procedures for Taxometric Investigations,2." Psychological Reports 73, no. 3_part_1 (1993): 709–37. http://dx.doi.org/10.1177/00332941930733pt149.

Full text

Abstract:

Certain theories of psychopathology postulate the existence of distinct latent populations of individuals. By analogy with biology, we call such latent populations “taxa” and we call the statistical testing of such theories “taxometrics.” Taxometric procedures are robust; they do not make restrictive distributional assumptions. However, they have two disadvantages for nonstatistician users: (1) they are developed via algebra hard for many nonstatistician users intuitively to accept; and (2) computational software is not widely available. We address these problems by presenting a simple taxometric procedure, MAXSLOPE, based on regression plots for pairs of variables. This procedure is easily implemented using commonly available software and is intuitively rather easy to understand. We apply it to two artificial datasets. One data-set, used to explain the graphs, shows clear-cut evidence of taxa. The other example shows less clear grouping structure and is used to show that the proposed graphical procedure works even in nonideal cases. Comparisons are made with currently used procedures of cluster analysis and multivariate normal mixture analysis.

APA, Harvard, Vancouver, ISO, and other styles

49

Gamarnik, David, and Quan Li. "On the max-cut of sparse random graphs." Random Structures & Algorithms 52, no. 2 (2017): 219–62. http://dx.doi.org/10.1002/rsa.20738.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Díaz, Josep, and Marcin Kamiński. "MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs." Theoretical Computer Science 377, no. 1-3 (2007): 271–76. http://dx.doi.org/10.1016/j.tcs.2007.02.013.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Max-cut problems on graphs'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles