Page
%P
146 Result(s)
within
Weili **
Optimization
-
Article
Improved approximation algorithm for the parallel-machine customer order scheduling with delivery time and submodular rejection penalties
In this paper, we design a 2-approximation algorithm for the parallel-machine customer order scheduling with delivery time and submodular rejection penalties based on Lovász rounding technique, which improves ...
-
Article
Minimum total coloring of planar graphs with maximum degree 8
We define G to be a planar graph with maximum degree \(\varDelta \) Δ . Supp...
-
Article
Distance magic labeling of the halved folded n-cube
Hypercube is an important structure for computer networks. The distance plays an important role in its applications. In this paper, we study a magic labeling of the halved folded n-cube which is a variation of th...
-
Chapter
Machine Learning-Based Rumor Controlling
In the management of business or political battle, the rumor or disinformation is an important issue to be dealt with. Especially, with the rise of Web 2.0, online social networks (OSN) have been an important ...
-
Article
An optimal streaming algorithm for non-submodular functions maximization on the integer lattice
Submodular optimization problem has been concerned in recent years. The problem of maximizing submodular and non-submodular functions on the integer lattice has received a lot of recent attention. In this pape...
-
Article
Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties
In this paper, we consider the parallel-machine scheduling problem with release dates and submodular rejection penalties. In this problem, we are given m identical parallel machines and n jobs. Each job has a pro...
-
Article
Adaptive seeding for profit maximization in social networks
Social networks are becoming important dissemination platforms, and a large body of works have been performed on viral marketing, but most are to maximize the benefits associated with the number of active node...
-
Chapter
Introduction
Let us start this textbook from a fundamental question and tell you what will constitute this book.
-
Chapter
Dynamic Programming and Shortest Path
A divide-and-conquer algorithm consists of many iterations. Usually, each iteration contains three steps. In the first step (called the divide step), divide the problem into smaller subproblems. In the second ...
-
Chapter
Primal-Dual Methods and Minimum Cost Flow
There are three types of incremental methods, primal, dual, and primal-dual. In Chap. 6, we touched all of them for linear programming (LP). This chapter is contributed specially to primal-dual methods for fur...
-
Chapter
Restriction and Steiner Tree
Restriction is a major technique in design of approximation algorithms. The Steiner minimum tree is a classic NP-hard combinatorial optimization problem. In the study of the Steiner minimum tree and its variat...
-
Chapter
Divide-and-Conquer
The divide-and-conquer is an important technique for design of algorithms. In this chapter, we will employ several examples to introduce this technique, including the rectilinear minimum spanning tree, the Fib...
-
Chapter
Greedy Approximation and Submodular Optimization
Greedy is an important strategy to design approximation algorithms, especially in the study of submodular optimization problems. In this chapter, we will explore this strategy together with important results i...
-
Chapter
Greedy Algorithm and Spanning Tree
Self-reducibility is the backbone of each greedy algorithm in which self-reducibility structure is a tree of special kind, i.e., its internal nodes lie on a path. In this chapter, we study algorithms with such...
-
Chapter
Nonsubmodular Optimization
In the real world, there are many set function optimization problems with objective function and/or constraint which is neither submodular nor supermodular. Usually, it is hard to study their approximation sol...
-
Chapter
Linear Programming
Linear programming (LP) is an important combinatorial optimization problem, and in addition, it is an important tool to design and to understand algorithms for other problems. In this chapter, we introduce LP ...
-
Chapter
NP-Hard Problems and Approximation Algorithms
The class P consists of all polynomial-time solvable decision problems. What is the class NP? There are two popular misunderstandings:
-
NP is ...
-
-
Chapter
Relaxation and Rounding
The relaxation is a powerful technique to design approximation algorithms. It is similar to restriction, in terms of making a change on feasible domain; however, in an opposite direction, i.e., instead of shri...
-
Chapter
Incremental Method and Maximum Network Flow
In this chapter, we study the incremental method which is very different from those methods in the previous chapters. This method does not use the self-reducibility. It starts from a feasible solution, and in ...
-
Book
