Search

ABSTRACTLC3 lipidation plays an important role in the regulation of macroautophagy and LC3-associated microautophagy. The E1-like enzyme ATG7 is one of the core components that are directly involved in LC3 lipidation reaction. Here, we provide evidence showing that acetylation of ATG7 tightly controls its enzyme activity to regulate the induction of macroautophagy and LC3-associated microautophagy. Mechanistically, acetylation of ATG7 disrupts its interaction with the E2-like enzyme ATG3, leading to an inhibition of LC3 lipidation in vitroand in vivo. Functionally, in response to various different stimuli, cellular ATG7 undergoes deacetylation to induce macroautophagy and LC3-associated microautophagy, which are necessary for cells to eliminate cytoplasmic DNA and degrade lysosome membrane proteins, respectively. Taken together, these findings reveal that ATG7 acetylation acts as a critical rheostat in controlling LC3 lipidation and related cellular processes.Abbreviations:AMPK: AMP-activated protein kinase; ATG: autophagy-related; cGAMP: cyclic GMP-AMP; CGAS: cyclic GMP-AMP synthase; CREBBP/CBP: CREB binding protein; EGF: epidermal growth factor; EGFR: epidermal growth factor receptor; EP300/p300: E1A binding protein p300; IFNB1: interferon beta 1; ISD: interferon stimulatory DNA; MAP1LC3/LC3: microtubule associated protein 1 light chain 3; MCOLN1/TRPML1: mucolipin TRP cation channel 1; MEF: mouse embryonic fibroblast; MTOR: mechanistic target of rapamycin kinase; NAM: nicotinamide; PE: phosphatidylethanolamine; PTM: post-translational modification; RB1CC1/FIP200: RB1 inducible coiled-coil 1; SIRT: sirtuin; SQSTM1/p62: sequestosome 1; STING1: stimulator of interferon response cGAMP interactor 1; TSA: trichostatin A; ULK1: unc-51 like autophagy activating kinase 1; WIPI2: WD repeat domain, phosphoinositide interacting 2; WT: wild-type.

ABSTRACTPost-translational modifications, such as phosphorylation, ubiquitination and acetylation, play crucial roles in the regulation of autophagy. Acetylation has emerged as an important regulatory mechanism for autophagy. Acetylation regulates autophagy initiation and autophagosome formation by targeting core components of the ULK1 complex, the BECN1-PIK3C3 complex, and the LC3 lipidation system. Recent studies have shown that acetylation occurs on the key proteins participating in autophagic cargo assembly and autophagosome-lysosome fusion, such as SQSTM1/p62 and STX17. In addition, acetylation controls autophagy at the transcriptional level by targeting histones and the transcription factor TFEB. Here, we review the current knowledge on acetylation of autophagy proteins and their regulations and functions in the autophagy pathway with focus on recent findings.Abbreviations :ACAT1: acetyl-CoA acetyltransferase 1; ACSS2: acyl-CoA synthetase short chain family member 2; AMPK: AMP-activated protein kinase; ATG: autophagy-related; CALCOCO2/NDP52: calcium binding and coiled-coil domain 2; CCAR2/DBC1: cell cycle and apoptosis regulator 2; BECN1: beclin 1; CMA: chaperone-mediated autophagy; CREBBP/CBP: CREB binding protein; EP300/p300: E1A binding protein p300; GAPDH: glyceraldehyde-3-phosphate dehydrogenase; GSK3: glycogen synthase kinase 3; HDAC6: histone deacetylase 6; HSPA8/HSC70: heat shock protein family A (Hsp70) member 8; KAT2A/GCN5: lysine acetyltransferase 2A; KAT2B/PCAF: lysine acetyltransferase 2B; KAT5/TIP60: lysine acetyltransferase 5; KAT8/MOF: lysine acetyltransferase 8; LAMP2A: lysosomal associated membrane protein 2A; MAP1LC3/LC3: microtubule associated protein 1 light chain 3; MTOR: mechanistic target of rapamycin kinase; NBR1: NBR1 autophagy cargo receptor; OPTN: optineurin; PD: Parkinson disease; PE: phosphatidylethanolamine; PIK3C3/VPS34: phosphatidylinositol 3-kinase catalytic subunit type 3; PKM2: pyruvate kinase M1/2; PtdIns3P: phosphatidylinositol-3-phosphate; PTM: post-translational modification; RB1CC1/FIP200: RB1 inducible coiled-coil 1; RUBCN/Rubicon: rubicon autophagy regulator; RUBCNL/Pacer: rubicon like autophagy enhancer; SIRT1: sirtuin 1; SNAP29: synaptosome associated protein 29; SNARE: soluble N-ethylamide-sensitive factor attachment protein receptor; SQSTM1/p62: sequestosome 1; STX17: syntaxin 17; TFEB: transcription factor EB; TP53/p53: tumor protein p53; TP53INP2/DOR: tumor protein p53 inducible nuclear protein 2; UBA: ubiquitin-associated; ULK1: unc-51 like autophagy activating kinase 1; VAMP8: vesicle associated membrane protein 8; WIPI2: WD repeat domain, phosphoinositide interacting 2.

In recent years, advanced information communication technology (such as beyond 5G and 6G) will enable convenient end-to-end communication. This would allow collections of individual preferences as predictions of travellers’ perceptions, and thus support data analysis and traffic control in a dynamic circumstance. Therefore, analysis of nonlinearly modelled perceptions and perception-based user equilibrium are the necessary problem we encounter. This research explores the existence characteristics of perception-based stochastic user equilibrium (P-SUE), a type of stochastic user equilibrium where travelers make route choices according to their perceptive traffic circumstances instead of actual ones. A nonlinear perception model with stochasticity is developed and the traffic arrivals are approximately transformed from Poisson-distributed to Normal-distributed. From a static perspective, we develop a P-SUE model with a heterogeneous traveler community and discuss the interaction among travelers’ attitude, grouping and static perception-based stochastic user equilibrium (P-SSUE). After embedding a day-to-day learning process into the P-SSUE model, we further explore evolutionary dynamics of the equilibrium. Several scenarios are provided to investigate effects and sensitivity of traveler-related and road-related factors. It is found that learning produces perturbation and makes the existence condition of P-SSUE more complicated; the convergence processes of P-SSUEs are significantly shortened as the learning rate increases to higher than 0.1.

ABSTRACTAutophagy has emerged as a key regulator of cell metabolism. Recently, we have demonstrated that autophagy is involved in RNA metabolism by regulating ribosomal RNA (rRNA) synthesis. We found that autophagy-deficient cells display much higher 47S precursor rRNA level, which is caused by the accumulation of SQSTM1/p62 (sequestosome 1) but not other autophagy receptors. Mechanistically, SQSTM1 accumulation potentiates the activation of MTOR (mechanistic target of rapamycin kinase) complex 1 (MTORC1) signaling, which facilitates the assembly of RNA polymerase I pre-initiation complex at ribosomal DNA (rDNA) promoter regions and leads to the activation of rDNA transcription. Finally, we showed that SQSTM1 accumulation is responsible for the increase in protein synthesis, cell growth and cell proliferation in autophagy-deficient cells. Taken together, our findings reveal a regulatory role of autophagy and autophagy receptor SQSTM1 in rRNA synthesis and may provide novel mechanisms for the hyperactivated rDNA transcription in autophagy-related human diseases.Abbreviations:5-FUrd: 5-fluorouridine; LAP: MAP1LC3/LC3-associated phagocytosis; MAP1LC3/LC3: microtubule associated protein 1 light chain 3; MTOR: mechanistic target of rapamycin kinase; PIC: pre-initiation complex; POLR1: RNA polymerase I; POLR1A: RNA polymerase I subunit A; rDNA: ribosomal DNA; RRN3: RRN3 homolog, RNA polymerase I transcription factor; rRNA: ribosomal RNA; SQSTM1/p62: sequestosome 1; TP53INP2: tumor protein p53 inducible nuclear protein 2; UBTF: upstream binding transcription factor.

We study multitasking scheduling and due-window assignment problems in a single machine, which can be found in various application domains. In multitasking environment, unfinished job always interrupts in-processing job. In common due window assignment, the aim is to find optimal due window to minimise the value of the earliness and tardiness penalty. In this paper, we study two problems, where the objective of the first problem is minimise the earliness, tardiness, due-window starting time, and due-window size costs, the objective of the second problem is minmax common due-date with completion time penalty, then we obtain some analytical properties and provide polynomial time solutions. Finally, the experimental results show that the proposed methods are effective.

ABSTRACTMacroautophagy/autophagy, a highly conserved lysosome-dependent degradation pathway, has been intensively studied in regulating cell metabolism by degradation of intracellular components. In this study, we link autophagy to RNA metabolism by uncovering a regulatory role of autophagy in ribosomal RNA (rRNA) synthesis. Autophagy-deficient cells exhibit much higher 47Sprecursor rRNA level, which is caused by the accumulation of SQSTM1/p62 (sequestosome 1) but not other autophagy receptors. Mechanistically, SQSTM1 accumulation potentiates the activation of MTOR (mechanistic target of rapamycin kinase) complex 1 (MTORC1) signaling and promotes the assembly of RNA polymerase I pre-initiation complex at ribosomal DNA (rDNA) promoters, which leads to an increase of 47SrRNA transcribed from rDNA. Functionally, autophagy deficiency promotes protein synthesis, cell growth and cell proliferation, both of which are dependent on SQSTM1 accumulation. Taken together, our findings suggest that autophagy deficiency is involved in RNA metabolism by activating rDNA transcription and provide novel mechanisms for the reprogramming of cell metabolism in autophagy-related diseases including multiple types of cancers.Abbreviations:5-FUrd: 5-fluorouridine; AMPK: AMP-activated protein kinase; ATG: autophagy related; CALCOCO2/NDP52: calcium binding and coiled-coil domain 2; ChIP: chromatin immunoprecipitation; MAP1LC3/LC3: microtubule associated protein 1 light chain 3; MAPK/ERK: mitogen-activated protein kinase; MTOR: mechanistic target of rapamycin kinase; NBR1: NBR1 autophagy cargo receptor; NFKB/NF-κB: nuclear factor kappa B; NFE2L2/NRF2: nuclear factor, erythroid 2 like 2; OPTN: optineurin; PIC: pre-initiation complex; POLR1: RNA polymerase I; POLR1A/RPA194: RNA polymerase I subunit A; POLR2A: RNA polymerase II subunit A; rDNA: ribosomal DNA; RPS6KB1/S6K1: ribosomal protein S6 kinase B1; rRNA: ribosomal RNA; RUBCN/Rubicon: rubicon autophagy regulator; SQSTM1/p62: sequestosome 1; STX17: syntaxin 17; SUnSET: surface sensing of translation; TAX1BP1: Tax1 binding protein 1; UBTF/UBF1: upstream binding transcription factor; WIPI2: WD repeat domain, phosphoinositide interacting 2; WT: wild-type.

A transportation hub is the key link in the construction of the comprehensive three-dimensional transportation corridor of the Yangtze River Economic Belt, and is the basic factor responsible for the promotion of this belt. A high-speed railway hub has the “last kilometer of time-space compression” effect and is the key to building an efficient, convenient, modern, and comprehensive transportation system. This study constructed a model for measuring the connection-distribution performance of the high-speed railway hub, determined the connection-distribution performance of the urban high-speed railway hub in the Yangtze River Economic Belt, and analyzed its spatial differentiation characteristics, further revealed the influencing mechanism of the connection-distribution performance of the high-speed railway hub. The main results are as follows: (1) The connection-distribution performance of the high-speed railway hub in the Yangtze River Economic Belt presented an “olive-shaped pattern” grade structure with two small ends and a large middle section, that is, the number of high-speed railway stations with high performance and average performance was small, and the number of high-speed railway stations with good performance and medium performance was large. (2) The connection-distribution performance of the high-speed railway hub in the Yangtze River Economic Belt showed a regional differentiation pattern of “high in the east and low in the west” and “high in the north and low in the south”, and showed an urban agglomeration differentiation pattern of “high in the core areas but low in the marginal areas”; moreover, spatial differences were prominent in the distribution of nine evaluation indexes of the connection-distribution performance of the high-speed railway hub. (3) GDP, urbanization rate, city level, station passenger flow and frequency of shuttle bus were key driving factors affecting the connection-distribution performance of the high-speed railway hub. At the same time, there were significant differences in the key driving factors for the connection-distribution performance grades of high-quality, good, medium and average.

Paclitaxel-induced peripheral neuropathic pain (PIPNP) is a major therapy- and dose-limiting side effect that is extremely laborious to treat. Resveratrol (Res), with a structure name of 3,5,40-trihydroxystilbene, is a kind of natural polyphenolic chemical with plenty of useful characteristics such as anti-inflammatory, and anti-oxidative stress. However, the impact of Res on PIPNP remains unclear. Therefore, the current study intends to examine the analgesic effect of Res on PIPNP. In the present study, the results revealed that Res could effectively prevent the development of paclitaxel-induced PIPNP in a dose-dependent manner when repeated doses of Res were given during PIPNP induction. This prophylactic effect of Res was involved in inhibited paclitaxel-induced up-regulation of TRPV1 instead of TRPA1 in the dorsal root ganglia. Furthermore, the inhibition of TRPV1 up-regulation by Res may be involved in a phosphorylation of ERK mechanism. In summary, we conclude that Res plays an intriguing role in the prevention of PIPNP and thus may work as a therapeutic compound for treating and preventing PIPNP.

ABSTRACTRibosomal DNA (rDNA) transcription drives cell growth and cell proliferation via the product ribosomal RNA (rRNA), the essential component of ribosome. Given the fundamental role of rRNA in ribosome biogenesis, rDNA transcription has emerged as one of the effective targets for a number of human diseases including various types of cancers. In this study, we identify curcumin, an ancient drug, as a novel natural inhibitor of rDNA transcription. Curcumin treatment impairs the assembly of the RNA polymerase I preinitiation complex at rDNA promoters and represses rDNA promoter activity, which leads to the decrease of rRNA synthesis. In addition, curcumin treatment stimulates autophagosome formation and promotes autophagic degradation in cells. Mechanistically, curcumin inactivates the mechanistic target of rapamycin complex 1 (mTORC1), the upstream regulator of rDNA transcription and autophagy induction, by inhibiting mTOR lysosomal localization. Functionally, curcumin treatment inhibits protein synthesis, cell growth and cell proliferation. Taken together, these findings identify curcumin as an effective inhibitor of rDNA transcription and provide novel mechanisms for the anticancer properties of curcumin.Abbreviations:Atg: autophagy-related; GFP: green fluorescent protein; LAMP2: lysosomal associated membrane protein 2; LC3: microtubule-associated protein 1 light chain 3; MEF: mouse embryonic fibroblast; mTORC1: mechanistic target of rapamycin complex 1; rDNA: ribosomal DNA; rRNA: ribosomal RNA; TP53INP2: tumor protein p53 inducible nuclear protein 2.

ABSTRACTTP53INP2/DOR (tumor protein p53-inducible nuclear protein 2) contributes to mammalian macroautophagy/autophagy by carrying nuclear deacetylated MAP1LC3/LC3 to the cytoplasm. Here, we report that in the cytoplasm, TP53INP2 further functions in autophagosome biogenesis by promoting LC3B-ATG7 interaction. Cytoplasmic expression of the N-terminal region of TP53INP2, which includes the LC3-interacting region, effectively triggered LC3B–PE production and autophagosome formation. In the cytoplasm, TP53INP2 colocalized to early autophagic membrane structures containing ATG14, ZFYVE1/DFCP1 or WIPI2. While knockdown of TP53INP2did not affect the formation of these autophagic structures, deletion of BECN1or Atg5, or mutations preventing TP53INP2 from LC3 interaction, disrupted the membrane binding of TP53INP2. TP53INP2 interacted directly with ATG7 to form a LC3B-TP53INP2-ATG7 complex in the cytoplasm. Loss of TP53INP2-LC3 or TP53INP2-ATG7 interaction significantly reduced LC3B-ATG7 binding. Together, these results suggest that after shifting from the nucleus, cytoplasmic TP53INP2 is targeted to early autophagic membranes accompanied by LC3, where it contributes to autophagosome biogenesis by mediating LC3-ATG7 interaction.Abbreviations3-MA, 3-methyladenine; 3NES, 3 repeated nuclear export signal; 3NLS, 3 repeated nuclear localization signal; ACTB, actin beta; ATG, autophagy related; BECN1, Beclin 1; mCherry, monomeric red fluorescent protein mCherry; GFP, green fluorescent protein; GST, glutathione S-transferase; KO, knockout; LC3B/MAP1LC3B, microtubule-associated protein 1 light chain 3 beta; LC3B[G120], LC3B mutant lacking amino acids after glycine 120; LDH, lactate dehydrogenase; LMNB1, lamin B1; LIR, LC3-interacting region; MTORC1, mechanistic target of rapamycin complex 1; PE, phosphatidylethanolamine; PtdIns3K, phosphatidylinositol 3-kinase; PtdIns3P, phosphatidylinositol 3-phosphate; rDNA, ribosomal DNA; RFP, red fluorescent protein; RNAi, RNA interference; SQSTM1, sequestosome 1; TP53INP2, tumor protein p53-inducible nuclear protein 2; TP53INP2[1-28], TP53INP2 mutant containing amino acids 1 to 28; TP53INP2[28-45], TP53INP2 mutant containing amino acids 28 to 45; TP53INP2[LIRΔ], TP53INP2 mutant lacking amino acids 1 to 144; TP53INP2[NLSΔ], TP53INP2 mutant lacking amino acids 145 to 221; TP53INP2W35,I38A, TP53INP2 mutant in which tryptophan 35 and isoleucine 38 are replaced with alanine; TP53INP2W35,I38A[NLSΔ], TP53INP2 mutant lacking amino acids 145 to 221, and tryptophan 35 and isoleucine 38 are replaced with alanine; TP53INP2W35,I38A[Δ1-28],[NLSΔ], TP53INP2 mutant lacking amino acids 1 to 28 and amino acids 145 to 221, and tryptophan 35 and isoleucine 38 are replaced with alanine; TP53INP2[Δ1-28],[NLSΔ], TP53INP2 mutant lacking amino acids 1 to 28 and amino acids 145 to 221; TP53INP2[Δ67-111],[NLSΔ], TP53INP2 mutant lacking amino acids 67 to 111 and amino acids 145 to 221; TP53INP2[Δ112-144],[NLSΔ], TP53INP2 mutant lacking amino acids 112 to 144 and amino acids 145 to 221; TUBB, tubulin beta class I; ULK1, unc-51 like autophagy activating kinase 1; VMP1, vacuole membrane protein 1; WIPI2, WD repeat domain phosphoinositide-interacting 2; WT, wild-type; ZFYVE1/DFCP1, zinc finger FYVE-type containing 1.

Under the background of Industry 4.0, this paper studies the single machine scheduling problem by taking into account the time value of money and tardiness penalty. We establish a mixed integer nonlinear programming model for the considered problem, and then convert the above model into a novel integer linear programming model. Regarding the factor of time value of money, we mainly aim to find an optimal or near optimal processing sequence of the jobs such that the total future value of profits is maximized. We employ CPLEX to output optimal solutions for small-size instances. For large-size instances, we propose the genetic algorithm to produce near optimal solutions.

ABSTRACTCells integrate intracellular and extracellular cues to precisely control the balance of anabolic and catabolic processes, which is essential for cells to maintain homeostasis. The nuclear protein TP53INP2 (tumor protein p53 inducible nuclear protein 2) has emerged as one of the key players participating in both anabolic and catabolic processes. In the nucleus including the nucleolus, TP53INP2 binds to multiple transcription-related factors to modulate transcription, such as the transcription of thyroid hormone-related genes and ribosomal DNA. Interestingly, upon nutrient deprivation, TP53INP2 rapidly moves from the nucleus to the cytoplasm and participates in the regulation of macroautophagy/autophagy. By acting as a nutrient status sensor, TP53INP2 switches its role between transcription and autophagy by changing its subcellular localization and helps the cell to cope with environmental changes.AbbreviationsAtg: autophagy related; LIR: LC3-interacting region; MAP1LC3/LC3: microtubule-associated protein 1 light chain 3; MTORC1: mechanistic target of rapamycin kinase complex 1; rDNA: ribosomal DNA; TP53INP2: tumor protein p53 inducible nuclear protein 2; UIM: ubiquitin-interacting motif

ABSTRACTCells control their metabolism through modulating the anabolic and catabolic pathways. TP53INP2/DOR (tumor protein p53 inducible nuclear protein 2), participates in cell catabolism by serving as a promoter of autophagy. Here we uncover a novel function of TP53INP2 in protein synthesis, a major biosynthetic and energy-consuming anabolic process. TP53INP2 localizes to the nucleolus through its nucleolar localization signal (NoLS) located at the C-terminal domain. Chromatin immunoprecipitation (ChIP) assays detected an association of TP53INP2 with the ribosomal DNA (rDNA), when exclusion of TP53INP2 from the nucleolus repressed rDNA promoter activity and the production of ribosomal RNA (rRNA) and proteins. The removal of TP53INP2 also impaired the association of the POLR1/RNA polymerase I preinitiation complex (PIC) with rDNA. Further, TP53INP2 interacts directly with POLR1 PIC, and is required for the assembly of the complex. These data indicate that TP53INP2 promotes ribosome biogenesis through facilitating rRNA synthesis at the nucleolus, suggesting a dual role of TP53INP2 in cell metabolism, assisting anabolism on the nucleolus, and stimulating catabolism off the nucleolus.

Recently, the single-period, single-item newsboy problem for the case where demand distribution is limited (e.g., range, mean, mode, variance, symmetry) has been widely studied. However, the existing newsboy models with partial information are fit to risk-neutral inventory managers, and there are few studies about the risk analysis of the newsboy problems with partial information. This paper considers the newsboy problem with range information. Our approach employs the competitive ratio analysis which guarantees a certain performance level under all possible input sequences, and constructs a framework to manage risk and reward of newsboy problems under different forecasts (i.e., certain forecast, probability forecast and probability distribution). Comparing with the existing studies, this approach can help the newsboy choosing the optimal reward/risk order strategies with great flexibility, according to his/her own risk/reward tolerance levels and different forecasts.

We study the problem of online scheduling parallel jobs with bounded processing times on 2 machines, and the objective is to minimize makespan. A parallel job requires simultaneous processing on a pre-specified, job-dependent number of machines. The problem is online in the sense that jobs are presented one by one. Once a job is presented, we must irrevocably assign it to some time slot before the next one shows up. We investigate the case where the processing times of jobs are bounded within interval [a, αa]where a > 0and α > 1. We first prove a lower bound of competitive ratios for online algorithms equal $\min\left\{1+\frac{1}{\alpha}, \frac{2+3\alpha}{2(1+\alpha)}\right\}$when α ≥ 2 and $\min\left\{\frac{1+\alpha}{2}, \frac{2+\alpha}{1+\alpha}\right\}$when 1 < α < 2, respectively. We further prove that the Greedy algorithm proposed in Chan et al.(2008) is $\left(1+\frac{\alpha}{2}\right)$-competitive in the case but it cannot be better than $\left(1+\frac{1+\alpha}{5+\alpha}\right)$-competitive. The results imply that when 1 < α < 2 Greedy has a competitive ratio better than 2, which is the competitive ratio of Greedy in the case without processing time bound.

We consider two semi-online scheduling problems on a single batch (processing) machine with jobs' nondecreasing processing times and jobs' nonincreasing processing times, respectively. Our objective is to minimize the makespan. A batch processing machine can handle up to Bjobs simultaneously. We study an unbounded model where B = ∞. The jobs that are processed together construct a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time of any job in the batch. Jobs arrive over time. Let pjdenote the processing time of job Jj. Given job Jjand its following job Jj + 1, we assume that pj + 1≥ α pj, where α ≥ 1 is a constant number, for the first problem with jobs' nondecreasing processing times. For the second problem, we assume that pj + 1≤ α pj, where 0 < α < 1 is a constant number. We propose an optimal algorithm for both problems with a competitive ratio $\frac{\sqrt{\alpha^2+4}-\alpha}{2}+1$for the first problem and $\frac{\sqrt{4\alpha+1}+1}{2}$for the second problem.

We study the following linear classification problem in signal processing: Given a set Bof n black point and a set Wof mwhite points in the plane (m= O(n)), compute a minimum number of lines Lsuch that in the arrangement of Leach face contain points with the same color (i.e., either all black points or all white points). We call this the Minimum Linear Classification (MLC) problem. We prove that MLC is NP-complete by a reduction from the Minimum Line Fitting (MLF) problem; moreover, a C-approximation to MLC implies a C-approximation to the MLF problem. Nevertheless, we obtain an O(log n)-factor algorithm for MLC and we also obtain an O(log Z)-factor algorithm for MLC where Z is the minimum number of disjoint axis-parallel black/white rectangles covering Band W.We study the following linear classification problem in signal processing: Given a set Bof n black point and a set Wof mwhite points in the plane (m= O(n)), compute a minimum number of lines Lsuch that in the arrangement of Leach face contain points with the same color (i.e., either all black points or all white points). We call this the Minimum Linear Classification (MLC) problem. We prove that MLC is NP-complete by a reduction from the Minimum Line Fitting (MLF) problem; moreover, a C-approximation to MLC implies a C-approximation to the MLF problem. Nevertheless, we obtain an O(log n)-factor algorithm for MLC and we also obtain an O(log Z)-factor algorithm for MLC where Z is the minimum number of disjoint axis-parallel black/white rectangles covering Band W.

We study the following linear classification problem in signal processing: Given a set Bof nblack point and a set Wof mwhite points in the plane (m=O(n)), compute a minimum number of lines Lsuch that in the arrangement of Leach face contain points with the same color (i.e., either all black points or all white points). We call this the Minimum Linear Classification (MLC) problem. We prove that MLC is NP-complete by a reduction from the Minimum Line Fitting (MLF) problem; moreover, a C-approximation to Minimum Linear Classification implies a C-approximation to the Minimum Line Fitting problem. Nevertheless, we obtain an O(log n)-factor algorithm for MLC and we also obtain an O(log Z)-factor algorithm for MLC where Zis the minimum number of disjoint axis-parallel black/white rectangles covering Band W.

In the number of snacks problem(NSP), which was originally proposed by our team, an on-line player is given the task of deciding how many shares of snacks his noshery should prepare each day. The on-line player must make his decision and then finish the preparation before the customers come to his noshery for the snacks; in other words, he must make decision in an on-line fashion. His goal is to minimize the competitive ratio, defined as ∈σ:CA(σ)/COPT(σ), where σ denotes a sequence of numbers of customers, COPT(σ) is the cost of satisfying σ by an optimal off-line algorithm, and CA(σ) is the cost of satisfying σ by an on-line algorithm. In this paper we give a competitive algorithm for on-line number of snacks problem P1, the Extreme Numbers Harmonic Algorithm(ENHA), with competitive ratio 1+pċ(M-m)/(M+m), where Mand mare two extreme numbers of customers over the total period of the game, and pis a ratio concerning the cost of the two types of situations, and then prove that this competitive ratio is the best one if an on-line player chooses a fixed number of shares of snacks for any sequence of numbers of customers. We also discuss several variants of the NSPand give some results for it. Finally, we propose a conjecture for the on-line NSP.

We consider the problem of triangulating a convex polygon using n Steiner points under the following optimality criteria: (1) minimizing the overall edge length ratio; (2) minimizing the maximum edge length; and (3) minimizing the maximum triangle perimeter. We establish a relation of these problems to a certain extreme packing problem. Based on this relationship, we develop a heuristic producing constant approximations for all the optimality criteria above (provided n is chosen sufficiently large). That is, the produced triangular mesh is uniform in these respects. The method is easy to implement and runs in O (n log n) time and O (n) space. The observed runtime is much less. Moreover, for criterion (1) the method works--within the same complexity and approximation bounds--for arbitrary polygons with possible holes, and for criteria (2) and (3) it does so for a large subclass.

In this paper, based on the Position Maintaining Strategy(PMS for short), on-line scheduling of k-truck problem, which is a generalization of the famous k-server problem, is originally presented by our team. We proposed several competitive algorithms applicable under different conditions for solving the on-line k-truck problem. First, a competitive algorithm with competitive ratio 2k+1/θ is given for any θ≥1. Following that, if θ≥(c+1)/(c-1) holds, then there must exist a (2k-1)-competitive algorithm for k-truck problem, where cis the competitive ratio of the on-line algorithm about the relevant k-server problem. And then a greedy algorithm with competitive ratio 1+λ/θ, where lambda is a parameter related to the structure property of a given graph, is given. Finally, competitive algorithms with ratios 1+1/θ are given for two special families of graphs.

LetT denote a finite set of points in a unit isoscele right triangle (i.e., the right sides are both one),f(T) the minimum distance between pairs of points ofT, and $$f\vartriangle (n) = \mathop {\max }\limits_{||T|| = n} f(T).$$ In this paper, the exact values offΔ (n) for 2≤n≤7 and the corresponding configurations are given.

Given a planar point setS, a triangulation ofS is a maximal set of non-intersecting line segments connecting the points. The minimum weight triangulation problem is to find a triangulation ofS such that the sum of the lengths of the line segments in it is the smallest. No polynomial time algorithm is known to produce the optimal or even a constant approximation of the optimal solution, and it is also unknown whether the problem is NP-hard. In this paper, we propose two improved heuristics, which triangulate a set ofn points in a plane inO(n3) time and never do worse than the minimum spanning tree triangulation algorithm given by Lingas and the greedy spanning tree triangulation algorithm given by Heath and Pemmaraju. These two algorithms both produce an optimal triangulation if the points are the vertices of a convex polygon, and also do the same in some special cases.